/* DWtoABW.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 DReachable(int*,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 K,Nlinks,Nnodes,             A[NN],B[NN],W[NN], LOC[MM],ODEG[MM];
 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);

 DReachable(A,B,LOC,ODEG);

FIN:
 getchar();
}

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

/* For a transport network, list all nodes that are reachable from the entry
    node  and list all nodes that are not reachable from that node.
    Then list all nodes from which the exit node (Nnodes) is reachable and
     those from which the exit node is not reachable */

void DReachable(int *A, int *B, int *LOC, int *DEG)
{
 int K,L,N,Nnodes,CNT,
       *P,*Q,*PP,*QQ,      BUF1[MM],BUF2[MM],Nstate[MM];

 Nnodes=B[0];

/********* Part 1: nodes reachable from entry node 1 ***********/

 for (N=0; N<=Nnodes; N++)  Nstate[N]=0;
 BUF1[0]=1; BUF1[1]=0; PP=BUF2; QQ=BUF1;

MAINLP:
 P=QQ; Q=PP; PP=P; QQ=Q;     /* switch pointers to buffers */

 K=0;
 if (!*P)
  {       /* no more unlabeled nodes available */
   puts("\nThe following nodes have been reached from node 1:");
   for (N=1; N<=Nnodes; N++) if (Nstate[N]) {printf("%d ",N); K++;}   puts("");
   if (K<Nnodes)
    {     puts("The following nodes have NOT been reached:\n");
     for (N=1; N<=Nnodes; N++) if (!Nstate[N]) {printf("%d ",N);} puts("");
     puts("DiGraph is not a transport network.");
    }
   else puts("From entry node 1 all nodes have been reached.");
   return;
  }

 while (*P)
  {               /* run through all nodes in buffer to which P points */
   Nstate[*P]=2;
   L=LOC[*P]; CNT=DEG[*P];
   while (CNT)
    {
     if (!Nstate[B[L]]) {*Q=B[L]; Nstate[*Q]=1; Q++;}
     L++; CNT--;
    }
   P++;
  }
 *Q=0;     /* mark end of nodes in other buffer containing neighbors */
 goto MAINLP;
}


/****************** 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++; FLAG++;}
   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;
}

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