/* TestNewAssign.c */

#include <stdio.h>
void EDITABW(int*,int*,int*,char*);
void PrintDAdj(int*,int*,int*);
void KBDtoABW(int*,int*,int*,char*);
int FiletoABW(int*,int*,int*,char*);
void SORTW(int*,int*,int*);
void SavetoFile(int*,int*,int*,char*);
void ASGN(int*,int*,int*);
void GETLOCODEG(int*,int*,int*,int*);

#define DataFile "GraphDataFile3.txt"
#define NN 1301    /* maximum number of links = NN-1,  NN = (MM-1)(MM-1)/2 +1 */
#define MM 51      /* maximum number of nodes = MM-1 */
#define INF 0XFFFFFF

void main(void)
{
 int Nlinks,Nnodes,   LOC[MM],ODEG[MM],          A[NN],B[NN],W[NN];
 char CH, NAME[16];


 puts("Where is the 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')) {KBDtoABW(A,B,W,NAME); goto NXT;}
 if ((CH=='F') || (CH=='f')) {if (FiletoABW(A,B,W,NAME)) goto NXT; else goto FIN;}
 puts("Error: enter either K or F");  goto INX;

NXT:
 Nnodes=B[0]; Nlinks=A[0];
 printf("Name of Digraph = %s    Number of nodes = %d    Number of links = %d\n",
      NAME,Nnodes, Nlinks);

/*
 for (K=0; K<=Nlinks+1; K++) printf("%2d,",A[K]); puts("");
 for (K=0; K<=Nlinks+1; K++) printf("%2d,",B[K]); puts("");
 for (K=0; K<=Nlinks+1; K++) printf("%2d,",W[K]); puts("\n");
*/

EDLP:
 PrintDAdj(A,B,W);
 printf("\nNeed to make changes? Y/N  "); CH=(char)getchar(); getchar();
  if ((CH=='Y') || (CH=='y')) {EDITABW(A,B,W,NAME); goto EDLP;}

 printf("Save array to file? Y/N  "); CH=(char)getchar(); getchar();
  if ((CH=='Y') || (CH=='y')) SavetoFile(A,B,W,NAME);

 GETLOCODEG(A,B,LOC,ODEG);

 ASGN(B,LOC,ODEG);

FIN:
 getchar();
}

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

void ASGN(int *B, int *LOC, int *ODEG)
{
 int J,L,N,Nnodes,CNT,   *P,*Q,*Ptr0,
    Nstate[MM],PREV[MM],  BUF1[MM],BUF2[MM];

 Nnodes=B[0];
 for (N=0; N<=Nnodes; N++) Nstate[N]=0;

 BUF1[1]=1; PREV[1]=0;  /*Start with single entry node 1 in BUF1 */
 BUF1[2]=0;   Ptr0=BUF2;

MAINLP:
 if (Ptr0==BUF2) {P=Ptr0=BUF1; Q=BUF2;} else {P=Ptr0=BUF2; Q=BUF1;}
 P++;
 while (*P)
  {
   /* I=*P; */ L=LOC[*P]; CNT=ODEG[*P];      /* printf("\n(%d),",I); */
   while (CNT)
    {
     J=B[L];                          /*   printf("%d,",J); */
     if (!Nstate[J]) {Q++; *Q=J; PREV[J]=*P; Nstate[J]=1;}     /* *Q=J */
     if (J==Nnodes) goto ExitLab;
     L++;
    }
   Nstate[*P]=2; P++;
  }
 Q++; *Q=0;
 goto MAINLP;

ExitLab:
 puts("\nExit node received a label");

 for (N=1; N<=Nnodes; N++) printf("(%d)%d ",N,Nstate[N]); puts("\n");
 N=PREV[Nnodes];  printf("%d",Nnodes);
 while (N>0) {printf(" <- %d",N); N=PREV[N];}

 return;
}


/****************** editing weighted adjacency arrays **********************/

void EDITABW(int *A, int *B, int *W, char *NAME)
{
 int H,I,J,K,Nnodes,Nlinks,  *P,*Q,*R,      C[MM][MM],D[MM][MM];
 char *S,Str[NN];

 Nnodes=B[0]; K=1;
 for (I=1; I<=Nnodes; I++)               /* copy A,B,W into C */
  {
   J=0;
   while (A[K]==I) {J++; if (B[K]>I) {C[I][J]=B[K]; D[I][J]=W[K];} K++;}
   D[I][0]=C[I][0]=J; /* Use C,D equivalent of weighted short adjacency array */
  }

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

 scanf("%d",&I); getchar();
 if (!I) goto ToABW;                      /* no more editing; send it to ABW */
 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<16; K++) NAME[K]=Str[K];
   goto LP;
  }

 printf("all the given as neighbors#weights of (%d) are:  ",I);
 K=C[I][0];
 for (J=1; J<=K; J++) if (C[I][J]>I) printf("%d,",C[I][J]);
 printf("#");
 for (J=1; J<=K; J++) if (C[I][J]>I) printf("%d,",D[I][J]);
 printf("\ntype in ENTIRE correct line of neighbors#weights of(%d):  ",(I));
  gets(Str);

 J=0; S=Str;
LPLine1:          /* Convert ASCII digits to integers = neighbors of I */
 if (*S=='\0') {C[I][0]=D[I][0]=J; goto LP;}
 if (*S=='#') goto Weights;
 if ((*S<'0') || (*S>'9')) {S++; goto LPLine1;}

 H=0;
 while ((*S>='0') && (*S<='9')) {H = 10*H + (int)*S - 48;  S++;}
 if ((H>I)&&(H<=Nnodes)) {J++; C[I][J] = H;} /* (Node)I has neighbor H in J-th place */

Weights: J=0;                 /* S = '#' */
LPLine2:        /* Convert ASCII digits to integers - weights on links */
 while ((*S<'0') || (*S>'9')) S++;
 H=0;
 while ((*S>='0') && (*S<='9')) {H = 10*H + (int)*S - 48;  S++;}
 if ((H>I)&&(H<=Nnodes)) {J++; D[I][J] = H;} /* link I-C[I][J] has weight H */
 if (*S=='\0') {C[I][0]=D[I][0]=J; goto LP;}
 goto LPLine2;

ToABW:
         /* return data in C[ ][ ] and D[ ][ ]  to A,B,W */
 P=A; Q=B; R=W; P++; Q++; R++;   Nlinks=0;
 for (I=1; I<=Nnodes; I++)
  {
   K=C[I][0];
   for (J=1; J<=K; J++) {*P=I; *Q=C[I][J]; *R=D[I][J]; P++; Q++; R++;}
   Nlinks+=K;
  }
  A[0]=Nlinks;
  SORTW(A,B,W);

 return;
}

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

void KBDtoABW(int *A, int *B, int *W, char *NAME)
{
 int H,I,K,Nnodes,Nlinks;
 char *S,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);
 S=Str; for (K=0; K<10; K++) {NAME[K]=*S; S++;} *S='\0';

 printf("Input number of nodes in the graph:  "); scanf("%d",&Nnodes);getchar();
 B[0]=Nnodes;
 puts("Input EVERY neighbor after each (node):");

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

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

         /*********** input weights ***********/

 printf("Input weights for each of the following %d links:\n",Nlinks);
 for (K=1; K<=Nlinks; K++)
  {printf("%d->%d  ",A[K],B[K]); scanf("%d",&W[K]); getchar();}

/*

 for (K=0; K<Nlinks+1; K++) printf("%2d,",A[K]); puts("");
 for (K=0; K<Nlinks+1; K++) printf("%2d,",B[K]); puts("");
 for (K=0; K<Nlinks+1; K++) printf("%2d,",W[K]); puts("");
             getchar();
*/


 SORTW(A,B,W);

 return;
}

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

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

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

  CH = (char)fgetc(F);  S=GrStr;
  while (CH != '[') CH = (char)fgetc(F);   /* pass over everything before [ */
  *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 Ugraph"); return 0;}
  *S=CH; S++;

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

          /********** GrStr to AB **********/

 P=A; Q=B;  P++; Q++; S=GrStr;  R=W;  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:
 while (*S!='(') S++;    /* here *S=( */
 S++; H=0;
 while (*S!=')') {H = 10*H + *S-48; S++;}   /* (H) storage */
 if (H>Nnodes) Nnodes=H;
 S++;

 CNT=0;
LP:               /* neighbors of H */
  if (*S==',') S++;
  while (*S==' ') S++;
  if (*S==']') {*P=*Q=0; A[0]=Nlinks; B[0]=Nnodes; return Nnodes;}
  if (*S=='#') goto WEIGHTS;
  K=0; while ((*S>='0') && (*S<='9')) {K = 10*K + *S-48; S++;}
  if (!K) goto NEWCLUSTER;
  if (K>Nnodes) Nnodes=K;              
  *Q=K; *P=H; P++; Q++;  Nlinks++; CNT++; /* H stored in A[], K stored in B[] */
 goto LP;

WEIGHTS:
  S++;
  while (CNT>0)
   {
    if (*S==',') S++;
    K=0; while ((*S>='0') && (*S<='9')) {K = 10*K + *S-48; S++;}
    R++; *R=K;        
    CNT--;
   }
  if (*S==',') S++;      
 if (*S!=']') goto NEWCLUSTER;


 B[0]=Nnodes;  A[0]=Nlinks;
 SORTW(A,B,W);

 return 1;    /* dummy non-zero return */
}

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

void SORTW(int *A, int *B, int *W)
{
 int I,J,K,M,N,TEMP,  D[NN];

  N=A[0];
 for (K=1; K<=N; K++) D[K]=A[K]*1000000 + B[K]*10000 + W[K];
 for (I=1; I<N; I++)
  {
   M=D[I]; K=I;
   for (J=I+1; J<=N; J++) if (D[J]<M) {M=D[J]; K=J;}
   if (K!=I) {TEMP=D[I]; D[I]=D[K]; D[K]=TEMP;}
  }
       /****** Removal of duplicates in D[ ] *******/

  J=1;
  for (K=2; K<=N; K++) if (D[K-1] != D[K]) {J++; D[J]=D[K];}
  N=J;  /* possibly different number of links */

       /******** place results back in A,B,W *********/
       
 for (K=1; K<=N; K++)
  {A[K]=D[K]/1000000; TEMP=D[K]%1000000; B[K]=TEMP/10000; W[K]=TEMP%10000;}
 A[0]=N;  A[N+1]=0; B[N+1]=0; W[N+1]=0;
 return;
} 


/*************** print short adjacency array with weights ********************/

void PrintDAdj(int *A, int *B, int *W)
{
 int I,K=1,KK,Nnodes,FLAG;

 Nnodes=B[0];
 for (I=1; I<=Nnodes; I++)
  {
   printf("(%d)",I); KK=K; FLAG=0;
   while (A[K]==I) {printf(",%d",B[K]); K++;}
   putchar(',');
   if (FLAG)
    {
     putchar('#'); K=KK;
     while (A[K]==I) {printf("%d,",W[K]); K++;}
    }
   printf("   ");
  }
}

/****************** Save weighted Darray to data file *******************/

void SavetoFile(int *A, int *B, int *W, char *NAME)
{
 int H,I,K,KK,T,DIG,Nnodes,CNT;
 char TITLG[]=DataFile,    *S,          GrStr[NN];
 FILE *G;

 S=GrStr;
      /* Construct [UW"NAME" weighted Darray] in GrStr */
 *S='['; S++; *S='D'; S++; *S='W'; S++; *S='"';  S++;
 K=0; while (NAME[K] != '\0') {*S=NAME[K]; K++; S++;}
 *S='"'; S++;
 *S=' '; S++;
 Nnodes=B[0];
 K=1;
 for (I=1; I<=Nnodes; I++)
  {
   *S='('; S++; H=I;
   T=1; while (T<=H) T*=10; T=T/10;
   while (T) {DIG=H/T + 48; *S=(char)DIG; S++;  H=H%T; T=T/10;}
   *S=')'; S++;


   KK=K;   /* Convert all neighbors of (I) to chars */
   CNT=0;
   while (A[K]==I)
   {
    H=B[K]; 
    T=1; while (T<=H) T *= 10; T=T/10;
    while (T) {DIG=H/T + 48; *S=(char)DIG; S++; H=H%T; T=T/10;}
    *S=','; S++;   CNT++;
    K++;
   }
  if (!CNT) goto NXTCluster;
  *S='#'; S++;
  K=KK;  /* convert all weights on links on (I) to neighbors */
   while (A[K]==I)
   {
    H=W[K];
    T=1; while (T<=H) T *= 10; T=T/10;
    while (T) {DIG=H/T + 48; *S=(char)DIG; S++; H=H%T; T=T/10;}
    *S=','; S++;
    K++;
   }

NXTCluster:
  *S=' '; S++; *S=' '; S++;

 } /* end for I */

/* ToFile: */
                           puts(GrStr);   getchar();
 G=fopen(TITLG,"w");

fputs(GrStr,G);
 fclose(G);

}

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

void GETLOCODEG(int *A, int *B, int *LOC, int *ODEG)
{
 int L,N,Nnodes,CNT;

 L = A[0];  Nnodes=B[0];       /* A[0] = Nlinks */

 for (N=Nnodes; N>0; N--)
  {
   CNT=0;
   while (A[L]==N) {CNT++; L--;}
   LOC[N]=L+1; ODEG[N]=CNT;
  }
 return;
}


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