/*InputData.c */
/*  */

#include <stdio.h>
#include <string.h>

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

void KBToAB(int*,int*,char*);
int FileToAB(int*,int*,char*);
void SORTAB(int*,int*);
void DisplayArys(int*,int*,int*,int*);
void EDITAB(int*,int*,char*);
void ABtoFile(int*,int*,char*);



void main(void)
{
 int  Npairs,Nnodes,      A[NN],B[NN], LOC[MM],DEG[MM];   char CH,NAME[15];

 puts("Where is the input-data for the Digraph?");
 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')) {KBToAB(A,B,NAME); goto NXT;}
 if ((CH=='F') || (CH=='f')) {if (FileToAB(A,B,NAME)) goto NXT; else goto FIN;}
 puts("Error: enter either K or F");  goto INX;

NXT: 
 SORTAB(A,B);


 Npairs=A[0]; Nnodes=B[0];
 printf("\nUfile %s     %d Nodes   %d Links\n",NAME,Nnodes,Npairs/2);
 /*
 for (K=0; K<=Npairs+1; K++) printf("%2d",A[K]); puts("");
 for (K=0; K<=Npairs+1; K++) printf("%2d",B[K]); puts("");
 puts("");
 */
EDT:
 DisplayArys(A,B,DEG,LOC);

 puts("\nChange data?");
 printf(" if YES then press Y key. Pressing any other letter key means NO  ");
 CH = (char)getchar(); getchar();
 if (CH=='y') CH='Y';
 if (CH=='Y') {EDITAB(A,B,NAME); SORTAB(A,B);  goto EDT;}

 ABtoFile(A,B,NAME);




FIN:
 getchar();
}

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

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

  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=='d') CH='D';
  if (CH!='D')
   {puts("Data Array in file not marked 'D' (after '[') for Digraph"); return 0;}

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

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

  puts(GrStr);   /* getchar();   /* check data file */

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

 P=A; Q=B; R=W; P++; Q++; R++; S=GrStr;   Npairs=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 */
  if (*S==',') S++;
  while (*S==' ') S++;
  if (*S=='#') goto Weights;        /* no more neighbors of H */

  CNT=0;
  K=0; while ((*S>='0') && (*S<='9')) {K = 10*K + *S-48; S++; CNT++;}
  if (K>Nnodes) {printf("neighbor %d of node (%d) too large"); return 0;}
  *Q=K; *P=H; P++; Q++;  Npairs++;     /* H stored in A[], K stored in B[] */
 goto LP;

Weights:
  S++;
  while (CNT)
   {
    if (*S==',') S++;
    K=0; while ((*S>='0') && (*S<='9')) {K = 10*K + *S-48; S++; CNT--;}
    *W=K; W++;
   }
  if (*S==',') S++;
  while (*S==' ') S++;
  if (*S=='(') goto NEWCLUSTER;
  *P=*Q=*R=0; A[0]=Npairs; B[0]=Nnodes; return 1;    /* *S = ']' */
 }

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

void KBToAB(int *A,int *B, char *NAME)
{
 int H,I,K,Nnodes;
 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;
 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; /* For linked pair I-H, (Node)I has valid neighbor H */
   goto LPLine;
 NxtI:
  }
   A[0]=K; B[0]=Nnodes;
   A[K+1]=B[K+1]=0;
 return;
}

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

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

  Npairs=A[0];   P=A; Q=B; R=DBL;

  P++; Q++; R++;
  while (*P)     /* assume *Q is a valid neighbor of *P */
   {*R = *P*10000 + *Q;  R++;     *R = *Q*10000 + *P;  P++; Q++; R++;}
  *R=0;      /* end of DBL data marker */

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

 Npairs = 2*Npairs;       /* new value for Npairs (double) */
                                
 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;
 }

/********** Give values to DEG and LOC arrays and print three arrays *************/

void DisplayArys(int *A, int *B, int *DEG, int *LOC)
 {
  int I,J,K,CNT,Nnodes,Npairs,   *P,*Q;

  Nnodes=B[0]; Npairs=A[0]; DEG[0]=0; LOC[0]=0; LOC[Nnodes+1]=Npairs+1;
     P=A; P++;

  for (K=1; K<=Nnodes; K++)
   {
    CNT=0;
    while (*P==K) {CNT++; P++;}
    DEG[K]=CNT;
   }

  LOC[1]=1;
  for (K=1; K<Nnodes; K++) LOC[K+1] = LOC[K] + DEG[K];

/*  for (K=1; K<=Nnodes; K++) printf(" (%d)%d",K,LOC[K]); puts(""); */
  puts("The array of degrees:");
  for (K=1; K<=Nnodes; K++) printf(" (%d)%d",K,DEG[K]); puts("\n");

  puts("The long adjacency array is:");
  Q=B;
  for (I=1; I<=Nnodes; I++)
    {
     K=DEG[I];  printf("(%d),",I);
     for (J=1; J<=K; J++) {Q++; printf("%d,",*Q);}
     printf("  ");
    }
  puts("\n");

  puts("The short adjacency array is:");
  Q=B;
  for (I=1; I<=Nnodes; I++)
    {
     K=DEG[I];  printf("(%d),",I);
     for (J=1; J<=K; J++) {Q++; if (*Q>I) {printf("%d,",*Q);}} printf("  ");
    }
   puts("");

  return;
 }

/********************** editing long adjacency array *************************/

void EDITAB(int *A, int *B, char *NAME)
{
 int H,I,J,K,L,N,CNT,Nnodes,Npairs,    Loc[MM],Deg[MM];

 Nnodes=B[0];    

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

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

 puts("\n\nThe long adjacency array:");
 L=N=1;
 while (N<=Nnodes)
  {
   printf("  (%d),",N);
   while (A[L]==N)
    {
     /* if(B[L]>N) */ printf("%d,",B[L]);
     L++;
    }
   N++;
  }

         /****** actual editing *****/
 puts("\n\nInput integer:");
 printf("(node number) between 1 and %d\n",Nnodes);
 puts("0 (zero) to terminate editing");
 puts("-1 to edit NAME of graph");

 scanf("%d",&I); getchar();
 if (!I) return;                  /* no more editing; return to main prog */
 if (I<0)
  {
   printf("Input full NAME of input-data or graph (less than 15 characters):");
   gets(NAME);
   goto LP;
  }

  printf("ALL the neighbors of (%d) are:\n",I);
  L=Loc[I]; CNT=Deg[I];
  if (!CNT) goto AddDelete;
  while ((CNT) && (B[L]<I)) {printf("%d,",B[L]); CNT--; L++;}
  printf("    ");
  while (CNT) {printf("%d,",B[L]); CNT--; L++;}

  if (I<Nnodes) K=Nnodes; else K=Nnodes-1;
  printf("\n\nInput integer between 0 and %d (not %d)\n",K,I);

   puts(" as a neighbor to be added or deleted   or zero for no change: ");
   scanf("%d",&H); getchar();
   if (!H) {puts("No change of neighbors"); goto LP;}
  if (H<0) {puts("Integer cannot be negative"); goto LP;}
  if (H==I) {printf("Integer cannot be same as %d\n",I); goto LP;}
  if (H>K) {printf("Integer cannot be greater than %d\n",K); goto LP;}

AddDelete:

  if (H<I) {J=H; H=I; I=J;}       /* interchange H,I;   I < H necessary */

 L=Loc[I]; CNT=Deg[I];
 while ((B[L] != H) && (CNT)) {L++; CNT--;}
    /* CNT=0 add H (H not found,  CNT>0 delete H (H found) */

 if (CNT)
  { /* delete both representations of link I-H, H-I from A,B */
   L=1;
   while (A[L]<I) L++;   while(B[L]<H) L++;
   L++;
   while (A[L]<H) {A[L-1]=A[L]; B[L-1]=B[L]; L++;}
   while (B[L]<I) {A[L-1]=A[L]; B[L-1]=B[L]; L++;}
     L++;
   Npairs=A[0];
   while (L<=Npairs) {A[L-2]=A[L]; B[L-2]=B[L]; L++;}
   A[0]=Npairs-=2;  A[Npairs+1]=0;
 }

  else
   {  /* insert backwards both representations of link H-I and I-H into A,B */
    L=Npairs=A[0]; ;
    while (A[L]>H){A[L+2]=A[L]; B[L+2]=B[L]; L--;}
    while (B[L]>I) {A[L+2]=A[L]; B[L+2]=B[L]; L--;}
    A[L+2]=H; B[L+2]=I;

    while (A[L]>I) {A[L+1]=A[L]; B[L+1]=B[L]; L--;}
    while (B[L]>H) {A[L+1]=A[L]; B[L+1]=B[L]; L--;}
    A[L+1]=I; B[L+1]=H;

    Npairs=Npairs+2;
    A[0]=Npairs;              
  }

  goto LP;
}

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

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

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

          /***** First build character array in GrStr ********/
 R=GrStr;
 *R='['; R++;  *R='U'; R++;  *R=' ';  R++;  *R='"'; R++;
 K=0;
 while (NAME[K]!='\0') {*R=NAME[K]; R++; K++;}
 *R='"'; R++;       /* 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 ****/
  *R=','; R++; *R=' '; R++; *R='('; R++;
  H=I;
  T=1; while (T<=H) T=T*10;  T=T/10;
  while (T) {K=H/T; *R=DigChar[K]; R++; H=H%T; T=T/10;}
  *R=')'; R++;

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

  while (*P==I)
   {
    H=*Q;
    if (H>I)
     {
      *R=','; R++;
      T=1; while (T<=H) T=T*10;  T=T/10;
      while (T) {K=H/T; *R=DigChar[K]; R++; H=H%T; T=T/10;}
     }
    P++; Q++;
   }  /* end while *P */
  }   /* end for I */

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

 puts(GrStr);    getchar();

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

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

 return;
}