/* InputDataU.c */

#include <stdio.h>

#define DataFile "GraphDataFile3.txt"
#define NN 2501    /* maximum number of linked pairs = NN-1 */
#define MM 51      /* maximum number of nodes = MM-1 */


int FileToABU(int*,int*,char*);
void SORTABU(int*,int*);
int KBToABU(int*,int*,char*);
void ABUtoFile(int*,int*,char*);
void EDITABU(int*,int*,char*);
void DisplayArrayU(int*,int*,char);

void main(void)
{
 int  Npairs,Nnodes,   A[NN],B[NN];     char CH,NAME[16];


 puts("Where is the input-data for the Ugraph with weights?");
 puts("If it will be typed in on the (K)eyboard, type K");
 puts("If it is already in the GraphData (F)ile, type F");
INX:
 CH=(char)getchar(); getchar();
 if ((CH=='K') || (CH=='k')) {KBToABU(A,B,NAME); goto NXT;}
 if ((CH=='F') || (CH=='f')) {if (FileToABU(A,B,NAME)) goto NXT; else goto FIN;}
 puts("Error: enter either K or F");  goto INX;

NXT:
 SORTABU(A,B);

/*
 puts("input type of array(s) to be displayed:");
 puts(" (S) Short Adj Ary,  (L) Long Adj Ary,  (B) Both,  (A) A,B");
 scanf("%c",&CH);
 DisplayArrayU(A,B,CH);
*/
Npairs=A[0]; Nnodes=B[0];
 printf("\nUfile  ''%s''   %d Nodes   %d Links\n",NAME,Nnodes,Npairs/2);

 EDITABU(A,B,NAME);

/* DisplayArrayU(A,B,'B'); */

 ABUtoFile(A,B,NAME);

FIN:
 getchar();
}

/*****************************************************************************/


int FileToABU(int *A, int *B, char *NAME)
{
 FILE *F;   char TITLF[]=DataFile;
 char CH,*S,GrStr[NN];  int H,I,K,N=0,Nnodes,Nlinks,   *P,*Q;

  if ((F=fopen(TITLF,"r"))==NULL)
    {printf("Cannot find file %s\n",TITLF); return 0;}

     /************* list input-datas already in file ***********/

CH=(char)fgetc(F);

LP2:
 while ((!feof(F)) && (CH != '[')) CH=(char)fgetc(F);     /* find next [ */

 if (!feof(F))
  {
   N++; printf("%d  ",N);
   while (CH != ']') {putchar(CH); CH=(char)fgetc(F);}
   puts("]\n");
   goto LP2;
  }

 INX:
  puts("Input number before the selected data-input (zero to abort):");
  scanf("%d",&K); getchar();
  if (!K) {fclose(F); return 0;}
  if ((K<0) || (K>N)) {printf("Number must be between 1 and %d\n",N); goto INX;}

  rewind(F);

  CH = (char)fgetc(F);
  for (I=1; I<K; I++)
   {
    while (CH != ']') CH = (char)fgetc(F);
   CH = (char)fgetc(F);
  }

  while (CH != '[') CH = (char)fgetc(F);
  S=GrStr;    *S=CH;         /* CH =  [ */
  S++;

  CH = (char)fgetc(F); if ((CH=='u') || (CH=='U')) {*S='U'; S++;}
  else
   {puts("Input-array in file not marked 'U' (after '[') for Ugraph"); return 0;}



    /**** Copy character array in file to GrStr ********/

  CH = (char)fgetc(F);
  while (CH!=']') {*S=CH; S++; CH = (char)fgetc(F);}
  *S = CH;
  fclose(F);
  S++; *S='\0';

  puts("Input-data from file is:");
  puts(GrStr);   /* getchar();   /* check data file */

           /*********GrStr to A,B ******************/

 P=A; Q=B; P++; Q++; S=GrStr;   Nlinks=Nnodes=0;
 while (*S!='"') S++;

     /* *S='"';  get name */
 I=0; S++;
 while (*S!='"') {NAME[I]=*S; S++; I++;} NAME[I]='\0';

 while (*S!='(') S++;
                         

NEWCLUSTER:       /* here *S=( */

 S++; H=0;
 while (*S!=')') {H = 10*H + *S-48; S++;}   /* (H) storage */
 if (H>Nnodes) Nnodes=H;             
 S++;

LP:               /* neighbors of H */      /* puts("LP"); */
  if (*S==',') S++;
  while (*S==' ') S++;
  if (*S=='(') goto NEWCLUSTER;        /* no more neighbors of H */
  if (*S==']') goto DBL;
  if (*S=='#') goto LP;

  K=0; while ((*S>='0') && (*S<='9')) {K = 10*K + *S-48; S++;}
  if (!K)
   {                                    /* H is isolated, no neighbors */
    while ((*S==' ') || (*S==',')) S++;
    if (*S==']') goto DBL;             /* H is last node */
    if (*S=='(') goto NEWCLUSTER;      /* H not last node */
   }
  if (K>Nnodes) Nnodes=K;
  *Q=K; *P=H; P++; Q++;  Nlinks++;     /* H stored in A[], K stored in B[] */
 /* printf("Nlinks=%d *S=%c CNT=%d\n",Nlinks,*S,CNT); */  /* puts("EndLP"); */
 goto LP;

DBL:                                /* *S = ']' */
  for (K=1; K<=Nlinks; K++)
   {*P = B[K]; *Q = A[K]; P++; Q++;}
                            
  *P=*Q=0; A[0]=2*Nlinks; B[0]=Nnodes;
   SORTABU(A,B);
   return A[0];
}

/*****************************************************************************/

int KBToABU(int *A,int *B, char *NAME)
{
 int H,I,K,L,Nnodes,Nlinks;
 char *R,Str[NN];
 /* C[I][J] = J-th neighbor of (node)I;
    DBL to contain combined A[],B[] for sort */

 printf("Not exceeding 10 characters, input name of graph   "); gets(Str);
 R=Str; for (K=0; K<10; K++) {NAME[K]=*R; R++;} *R='\0';

 printf("Input number of nodes:  "); scanf("%d",&Nnodes); getchar();
 B[0]=Nnodes;
 puts("Input every neighbor with higher natural number after each (node):");

               /******** Convert input list to AB **********/
 K=0;   Nlinks=0;
 for (I=1; I<=Nnodes; I++)
  {
   printf("(%d),",I);       /* for (node) I ... */
   gets(Str); R=Str;   /* Str catches all the ASCII digits of neighbors */


 LPLine:          /* Convert ASCII digits to integers = neighbors of I */
   if (*R=='\0') goto NxtI;
   if ((*R<'0') || (*R>'9')) {R++; goto LPLine;}
   H=0;
   while ((*R>='0') && (*R<='9')) {H = 10*H + (int)*R - 48;  R++;}
   if ((I==H) || (I>Nnodes) || (H<=0) || (I<0)) goto LPLine;  /* omit */
    K++; A[K]=I; B[K]=H; Nlinks++; /* For linked pair I-H, (Node)I has valid neighbor H */
   goto LPLine;
NxtI:
 }

  puts("\nResulting short adjacency array:");  L=1;
  for (I=1; I<=Nnodes; I++)
   {
    printf("  (%d),",I); while (A[L]==I) {printf("%d,",B[L]); L++;}
   }
  puts("");

  L=Nlinks;
  for (K=1; K<=Nlinks; K++) {L++; B[L]=A[K]; A[L]=B[K];}
  L++; A[L]=B[L]=0;   A[0]=2*Nlinks; B[0]=Nnodes;;     
  SORTABU(A,B);
  return A[0];
}

/*****************************************************************************/

void SORTABU(int *A, int *B)
 {
  int I,J,K,M,CNT,Npairs,   *P,*Q,*D,   DBL[NN];

  Npairs=A[0];   P=A; Q=B; D=DBL;
  P++; Q++; D++;
  while (*P)     /* assume *Q is a valid neighbor of *P */
   {*D = *P*10000 + *Q; D++; P++; Q++;}
  *D=0;      /* end of DBL data marker */

           /********* Sort what is in DBL[] **********/

  for (I=1; I<=Npairs; I++)
  {
   K=I; M=DBL[K];
   for (J=I+1; J<=Npairs; J++) if (DBL[J]<M) {K=J; M=DBL[K];}
   if (K!=I) {DBL[K]=DBL[I]; DBL[I]=M;}
  }

  /***** Copy sorted DBL[] to A[], B[] without copying adjacent duplicates ****/
  P=A; Q=B; CNT=0;
  for (K=1; K<=Npairs; K++)  if (DBL[K] != DBL[K+1])
    {P++; Q++; CNT++; *P = DBL[K]/10000; *Q = DBL[K]%10000;}
  A[0]=CNT;   /* A[0] = new Npairs <= old Npairs above */     
  P++; Q++; *P=*Q=0;

  return;
}


/***************************************************************************/

void ABUtoFile(int *A, int *B, char *NAME)
{
 FILE *G;   char TITLG[]=DataFile;
 char *S,GrStr[NN], DigChar[]="0123456789";
 int H,I,K,T,Nnodes,CNT,    *P,*Q;

          /***** First build character array in GrStr ********/
 S=GrStr;
 *S='\n'; S++; *S='['; S++;  *S='U'; S++;  *S='W';  S++;  *S='"'; S++;
 K=0;
 while (NAME[K]!='\0') {*S=NAME[K]; S++; K++;}
 *S='"'; S++;       /* end of NAME in GrStr */

 P=A; Q=B; P++; Q++;  Nnodes=B[0];

 for (I=1; I<=Nnodes; I++)
  {
      /****  make ASCII integer (I) in parentheses ****/
  *S=','; S++; *S=' '; S++; *S=' '; S++; *S='('; S++;
  H=I;
  T=1; while (T<=H) T=T*10;  T=T/10;
  while (T) {K=H/T; *S=DigChar[K]; S++; H=H%T; T=T/10;}
  *S=')'; S++;

      /****  make ASCII neighbors ****/

  CNT=0;      
  while (*P==I)
   {
    H=*Q;
    if (H>I)
     {                            /* H = valid neighbor of I */
      *S=','; S++;
      T=1; while (T<=H) T=T*10;  T=T/10;
      while (T) {K=H/T; *S=DigChar[K]; S++; H=H%T; T=T/10;}
      CNT++;
     }
    P++; Q++;
   }  /* end while *P */


   if (!CNT) goto NxtI;
       /* for (K=1; K<=CNT; K++) printf("  I=%d BufW[%d]=%d\n",I,K,BufW[K]); */
  while (CNT)
   {
                    /* printf("H=%d J=%d CNT=%d\n",H,J,CNT); */
    T=1; while (T<=H) T=T*10;  T=T/10;
    while (T)
    {K=H/T; *S=DigChar[K]; S++; H=H%T; T=T/10;}
    CNT--;  
   }
NxtI:
  }   /* end for I */

 *S=']'; S++; *S='\0';

 puts(GrStr);  puts("Data-array stored in file");

      /*** Copy string GrStr to File ***/

 G=fopen(TITLG,"a");  fputs(GrStr,G); fclose(G);

 return;
}

/*****************************************************************************/

void DisplayArrayU(int *A, int *B, char CH)
{
 int I,L,Nnodes,Npairs,CNT,      Loc[MM],Deg[MM];

 L=1;   Nnodes=B[0];   Npairs=A[0];
 for (I=1; I<=Nnodes; I++)
  {CNT=0;  Loc[I]=L;  while (A[L]==I) {CNT++; L++;}  Deg[I]=CNT;}

/* puts("Loc,Deg");
 for (I=1; I<=Nnodes; I++) printf("  (%d)%d,%d",I,Loc[I],Deg[I]);  puts("");
*/

 if ((CH=='S') || (CH=='s') || (CH=='B') || (CH=='b'))
  {
   puts("\n\nThe SHORT adjacency array:");
  L=1;
  for (I=1; I<=Nnodes; I++)
   {
    printf("  (%d),",I);    CNT=Deg[I];
    while (CNT)
     {
      if (B[L]>I) printf("%d,",B[L]); L++;  /* print lrg neighbors I = A[L] */
      CNT--;
     }
   }
  }

 if ((CH=='L') || (CH=='l') || (CH=='B') || (CH=='b'))
  {
   puts("\n\nThe LONG adjacency array:");
  L=1;
  for (I=1; I<=Nnodes; I++)
   {
    printf("  (%d),",I);    CNT=Deg[I];
    while (CNT)
     {
      printf("%d,",B[L]); L++;  /* print neighbors I = A[L] */
      CNT--;
     }
   }
  }

 if((CH=='A') || (CH=='a'))
  {
   for (L=0; L<=Npairs+1; L++) printf("%3d",A[L]); puts("");
   for (L=0; L<=Npairs+1; L++) printf("%3d",B[L]); puts("");
   puts("");
  }

 getchar();
 return;
}



/********************** editing AB *************************/

void EDITABU(int *A, int *B, char *NAME)
{
 int I,J,L,M,N,CNT,Npairs,Nnodes,FoundLink,  Loc[MM],Deg[MM];
 char *P,*Q,Buf[1000];



LP:          /* for each input value of I */     
     /**************** Get and show degrees, long adjacency array *************/

  Npairs=A[0]; Nnodes=B[0];
  puts("The array of (nodes) and their (full) degrees:");
  L=1;
  for (I=1; I<=Nnodes; I++)
   {
    CNT=0;  Loc[I]=L;
    while (A[L]==I) {CNT++; L++;}
    printf("(%d)%d  ",I,CNT); Deg[I]=CNT;
   }

  DisplayArrayU(A,B,'L');

               /****** actual editing *****/
 INX:
 puts("\n");
 puts("input two positive integers for (node),neighbor,");
  puts("  or -1,0 to edit/change name of input-data,");
  puts("  or 0,0 to terminate editing");

 scanf("%d,%d",&I,&N); getchar();

 if (!I) return;

 if (I<0)
  {
   printf("Input full NAME of input-data or graph (less than 15 characters): ");
   gets(Buf);  puts(Buf);    Buf[15]='\0';
   P=Buf; Q=NAME;  while (*P!='\0') {*Q=*P; P++; Q++;};   *Q= '\0';
   goto LP;
  }

 if (I==N)
  {
   printf("ERROR: (node) %d and neighbor %d must be different\n",I,N);
   goto INX;
  }

 if (I>Nnodes)
  {
   printf("ERROR: (node) %d is larger than number of nodes %d\n",I,Nnodes);
   if ((N>0) && (N<=Nnodes))
     printf("Note: a new neighbor of node (%d) may equal %d\n",N,Nnodes+1);
   goto INX;
  }

 if (I==-N)
  {printf("ERROR: Cannot use %d to remove (node) %d\n",N,I); goto INX;}

  if (N>0) M=N; else M=-N;         /* M = absvalue of N */
 L=Loc[I]; CNT=Deg[I];  /* Try to find link number L of link I-N */
 while ((B[L]<M) && (CNT)) {L++; CNT--;}
 if ((!CNT) || (B[L]!=M)) FoundLink=0;         /* Link (neighbor N) not found */
  else FoundLink=1;

  if (N>0)
  { /* Test to see if insert given Link is possible */
   if (FoundLink)
    {                   printf("A[%d]=%d B[%d]=%d\n",L,A[L],L,B[L]);
     printf("Cannot insert link %d-%d; (node) %d has a neighbor %d\n",I,N,I,N);
     goto INX;
    }
  }


 if (N<0)
  { /* Test to see if Delete Link is possible */
   if (N>0) N=-N;
   if (!L)
   {
    printf("Cannot delete link %d-%d; (node) %d has no neighbor %d\n",I,N,I,N);
    goto INX;
   }
  }
                  /* delete/insert pairs of linkks */

                /* printf("I=%d N=%d FoundLink=%d\n",I,N,FoundLink); */
                
 if ((FoundLink) && (N<0))
  {                                       /* Delete */
   N=-N;  if (N<I) {J=N; N=I; I=J;}
   L=Loc[I]; while (B[L]<N) L++;  A[L]=10000;  B[L]=0;
   L=Loc[N]; while (B[L]<I) L++;  A[L]=10000;  B[L]=0;
   SORTABU(A,B);

   Npairs-=2; A[0]=Npairs;
   A[Npairs+1]=B[Npairs+1]=0;
   if ((N==B[0]) && (Deg[N]==1)) B[0]--;
   goto LP;
  }

 if ((!FoundLink) && (N>0))
  {                                       /* Insert */
   if (N<I) {J=N; N=I; I=J;}
   L=Npairs+1;
   A[L]=I; B[L]=N;
   L++;
   A[L]=N; B[L]=I;
   L++;
   A[L]=B[L]=0;
   A[0]=Npairs+=2; if (N==Nnodes+1) B[0]=Nnodes+1;
   SORTABU(A,B);
   goto LP;
  }
}



/*****************************************************************************/