/* GraphDatatoComponentsAB.c */
/*  */

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

#define DataFile "GraphDataFile2.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 ValDecLoc(int*,int*,int*,int*);
void DisplayAdjArys(int*,int*);
void EDITAB(int*,int*,char*);
void ABtoFile(int*,int*,char*);


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

 puts("Where is the data for the Ugraph?");
 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);
 ValDecLoc(A,B,DEG,LOC);

 Npairs=A[0]; Nnodes=B[0];
 printf("Ufile %s     %d Nodes   %d Links\n",NAME,Nnodes,Npairs/2);
/*
 for (K=1; K<=Nnodes; K++) printf("(%d)%d ",K,DEG[K]);puts("");
 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:
 ValDecLoc(A,B,DEG,LOC);
 for (K=1; K<=Nnodes; K++) printf("(%d)%d ",K,DEG[K]);puts("\n");
 DisplayAdjArys(B,DEG);

 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 FileToAB(int *A, int *B, char *NAME)
{
 FILE *F;   char TITLF[]=DataFile;
 char CH,*R,GrStr[NN];  int I,K;  int H,Nnodes,Npairs,   *P,*Q;

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

  CH = (char)fgetc(F);  R=GrStr;
  while (CH != '[') CH = (char)fgetc(F);   /* pass over everything before [ */
  *R=CH;         /* CH =  [ */
  R++;

  CH = (char)fgetc(F); if (CH=='u') CH='U';
  if (CH!='U')
   {puts("Data Array in file not marked 'U' (after '[') for Ugraph"); return 0;}

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

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

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

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

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

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

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


NEWCLUSTER:       /* here *R=( */

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

LP:               /* neighbors of H */
  if (*R==',') R++;
  while (*R==' ') R++;
  if (*R==']') {*P=*Q=0; A[0]=Npairs; B[0]=Nnodes; return 1;}
  if (*R=='(') goto NEWCLUSTER;        /* no more neighbors of H */

  K=0; while ((*R>='0') && (*R<='9')) {K = 10*K + *R-48; R++;}
  if (K>Nnodes) Nnodes=K;              
  *Q=K; *P=H; P++; Q++;  Npairs++;     /* H stored in A[], K stored in B[] */
 goto LP;
}

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

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 non-isolated 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 *************/

void ValDecLoc(int *A, int *B, int *DEG, int *LOC)
 {
  int K,CNT,Nnodes,Npairs,   *P;

  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];

 return;
}

/********************** Display Adjacency Arrays ****************************/

void DisplayAdjArys(int *B, int *DEG)
 {
/*  for (K=1; K<=Nnodes; K++) printf(" (%d)%d",K,LOC[K]); puts(""); */
  int I,J,K,Nnodes,    *Q;

  Nnodes=B[0];
  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 adjacency arrays ***************************/

void EDITAB(int *A, int *B, char *NAME)
{
 int H,I,J,K,Nnodes,Npairs,  *P,*Q,      C[MM][MM];   char *R,Str[NN];

 Nnodes=B[0]; K=1;
 for (I=1; I<=Nnodes; I++)               /* copy A,B into C */
  {
   J=0;
   while (A[K]==I) {J++; C[I][J]=B[K]; K++;}
   C[I][0]=J;
  }

LP:
 puts("Input 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) goto ToAB;                      /* no more editing; send it to AB */
 if (I<0)
  {
   printf("Input full NAME of file (less than 15 characters):");
   gets(Str); Str[15]='\0';
   printf("New NAME = "); puts(Str);
   for (K=0; K<15; K++) NAME[K]=Str[K];
   goto LP;
  }

 printf("all the given as neighbors of (%d) are:  ",I);
 K=C[I][0];
 for (J=1; J<=K; J++) printf("%d,",C[I][J]);
 printf("\ntype in entire correct line of ALL neighbors of node (%d):  ",(I));
  gets(Str);

 J=0; R=Str;
LPLine2:          /* Convert ASCII digits to integers = neighbors of I */
 if (*R=='\0') {C[I][0]=J; goto LP;}
 if ((*R<'0') || (*R>'9')) {R++; goto LPLine2;}
 H=0;
 while ((*R>='0') && (*R<='9')) {H = 10*H + (int)*R - 48;  R++;}
 if ((H>I)&&(H<=Nnodes)) {J++; C[I][J] = H;} /* (Node)I has neighbor H in J-th place */
 goto LPLine2;

ToAB:        /* return data in C[ ][ ] to A,B */
 P=A; Q=B; P++; Q++;   Npairs=0;
 for (I=1; I<=Nnodes; I++)
  {
   K=C[I][0];
   for (J=1; J<=K; J++) {*P=I; *Q=C[I][J]; P++; Q++;}
   Npairs+=K;
  }
 A[0]=Npairs; *P=*Q=0;
 return;
}

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

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); */  

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

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

 return;
}