/* ReachablefD.c */        /* This program IGNORES WEIGHTS */

#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 FileToABD(int*,int*,char*);
void SORTAB(int*,int*);
int KBToABD(int*,int*,char*);
void ABDtoFile(int*,int*,char*);
void EDITABD(int*,int*,char*);
int DisplayArrayD(int*,int*,char);

int Reachable(int*, int*);

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


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

NXT:
 SORTAB(A,B);


Nlinks=A[0]; Nnodes=B[0];
 printf("\nDigraph  ''%s''  %d Nodes   %d directed Links\n",NAME,Nnodes,Nlinks);

/* CH: S=Successor Array; L=Long (Predecessor-Successor) Array;
        D=Full (Indegree+Outdegree array;  A= A,B arrays */
 DisplayArrayD(A,B,'A'); 

 puts("\nMake changes to input-data? Y/N");
 CH=(char)getchar();  getchar();
 if ((CH=='y') || (CH=='Y')) EDITABD(A,B,NAME);

 if (!Reachable(A,B)) {puts("program aborted"); goto FIN;}


FIN:
 getchar();
}

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

int Reachable(int *A, int *B)
{
 int I,J,L,N,Nnodes,Nlinks,CNT,    *P,*Q,         /* P --> head node in Path  */
     Loc[MM],Snhbr[MM],Visited[MM],Path[MM];
                          /* Snhbr = number of unvisited successor neighbors */
                          /* originally, Snhbr = Outdegree */
 Nnodes=B[0]; Nlinks=A[0];

 for (I=0; I<=Nnodes; I++) Visited[I]=Loc[I]=Snhbr[I]=0;

 Loc[Nnodes+1]=Nlinks+1; L=1;
 while (L<=Nlinks)
  {
   while (L<=Nlinks)
    {
     CNT=0;
     while (A[L]==I) {L++; CNT++;}
     Snhbr[I]=CNT;
     I=A[L]; Loc[I]=L;
   }
  }
/*
 for (I=0; I<=Nnodes+1; I++)
  printf("Loc[%d]=%d Snhbr[%d]=%d ",I,Loc[I],I,Snhbr[I]); puts("\n");
*/
 printf("Input a node number between 1 and %d  ",Nnodes); scanf("%d",&N); getchar();
 if (!N) return 0;

 P=Path; *P=0;   /* Path[0]=0  to be used as a marker "no previous backup node */
 P++; *P=I=N;   Visited[N]=1;      /* Start node N = Path[1] */

NextNode:                  /* get unvisited neighbor of I */
 if (Snhbr[I])
  {
   L = Loc[I] + Snhbr[I] - 1;       /* locate successor neighbor */
   Snhbr[I]--;
   J=B[L];
   if (Visited[J]) goto NextNode;
   I=J;
   P++; *P = I;                     /* Copy I onto head of Path */
   Visited[I]=1;
   goto NextNode;
  }

/* On path, backup to a previous node with successor neighbors */
   Q=P;                             /* P must always point to head of path */
Back1:
 Q--;                 /*  printf("I=%d *P=%d *Q=%d\n",I,*P,*Q);   getchar(); */
 if (! *Q) goto FIN;
 if (!Snhbr[*Q]) goto Back1;
 I = *Q;
 goto NextNode;

FIN:
 printf("Collection all nodes reachable from node %d\n",N);
 CNT=0;
 for (I=1; I<=Nnodes; I++) {if (Visited[I]) printf("%d ",I); CNT++;}
 return CNT;
}


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

/* Note: This subprogram IGNORES WEIGHTS */

int FileToABD(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=='d') || (CH=='D')) {*S='D'; S++;}
  else
   {puts("Input-array in file not marked 'D' (after '[') for Digraph"); 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 FIN;
  if (*S=='#')
   {
    while ((*S!='(') && (*S!=']')) S++;
    if (*S==']') goto FIN;
    goto NEWCLUSTER;
   }

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

FIN:   /* *S=']' */
  *P=*Q=0; A[0]=Nlinks; B[0]=Nnodes;
   SORTAB(A,B);
   return A[0];
}

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

int KBToABD(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 successor neighbor 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 successor array:");  L=1;
  for (I=1; I<=Nnodes; I++)
   {
    printf("  (%d),",I); while (A[L]==I) {printf("%d,",B[L]); L++;}
   }
  puts("");

  L=Nlinks;

  L++; A[L]=B[L]=0;   A[0]=Nlinks; B[0]=Nnodes;;

  SORTAB(A,B);
  ABDtoFile(A,B,NAME);
  return A[0];
}

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

void SORTAB(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 ABDtoFile(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='D'; 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;
      *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;
}

/*****************************************************************************/
/* CH: S=Successor Array; L=Long (Predecessor-Successor) Array;
        D=Full (Indegree+Outdegree array;  A= A,B arrays */

int DisplayArrayD(int *A, int *B, char CH)
{
 int H,I,J,K,L,M,T,Nnodes,Nlinks,CNT,   *P,*Q, *PP,*QQ;
 char *S,PredC[MM],DigChar[]="0123456789";
 int Indent=34;         /* place where ( in (node) is located in printed line */

 Nnodes=B[0];   Nlinks=A[0];

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

 if ((CH=='S') || (CH=='s'))
  {
   puts("\n\nThe successor array:");
   P=A; Q=B; P++; Q++;
   for (I=1; I<=Nnodes; I++)
   {
     printf("  (%d),",I);
     while (*P==I) {printf("%d,",*Q); P++; Q++;}
   }
  puts("");
  return 1;
 } 

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

/*****************/
  PP=A; PP++; QQ=B; QQ++;
 if ((CH=='L') || (CH=='l'))
  {
   puts("\nlist of   predecessor neighbors  (node)  successor neighbors");
   for (I=1; I<=Nnodes; I++)
    {
     /* print predecessor neighbors of I */
     P=A; P++; Q=B; Q++;   S=PredC;   CNT=0;
     while (*P)
      {
       if (*Q==I)
         {
          H=*P;
          T=1; while (T<=H) T*=10;   T/=10;
          while (T) {K=H/T; *S=DigChar[K]; S++; CNT++; H=H%T; T=T/10;}
          *S=','; S++;  CNT++;
         }
       P++; Q++;
      }
                        /* print all precedessor neighbors before (node) */
   M=Indent-CNT;
   for (J=1; J<=M; J++) putchar(' ');
   S=PredC; while (CNT) {putchar(*S); S++; CNT--;}

   printf("(%d),",I);
                          /* print successor neighbors */
   while (*PP==I) {printf("%d,",*QQ); PP++; QQ++;}
   puts("");
  }
  return 1;
 }

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

 if ((CH=='D') || (CH=='d'))
  {
   puts("\n(nodes) number of ALL links touching that node");
   for (I=1; I<=Nnodes; I++)
    {
     P=A; Q=B; P++; Q++;  CNT=0;
     while (*P) {if ((*P==I) || (*Q==I)) CNT++;   P++; Q++;}
     printf("(%d)%d  ",I,CNT);
    }
    puts("");
   return 1;
  }

  puts("ERROR: parameter for CH is not S,L,D, or A");
  return 0;

}



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

void EDITABD(int *A, int *B, char *NAME)
{
 int I,J,L,M,N,CNT,Nlinks,Nnodes,FoundLink,    *P,*Q,
  Loc[MM],InDeg[MM],OutDeg[MM];
 char *S1,*S2,Buf[1000];

 Nlinks=A[0]; Nnodes=B[0];


     /**************** Get and show indegrees and outdegrees  *************/


  puts("The array of indegrees, (nodes), outdegrees:");
  L=1;
  for (I=1; I<=Nnodes; I++)
   {
    P=&A[1]; Q=&B[1]; CNT=0;
    while (*P) {if (*Q==I) CNT++;   P++; Q++;}
    printf("%d",CNT); InDeg[I]=CNT;
         printf("(%d),",I);
    CNT=0;  Loc[I]=L;
    while (A[L]==I) {CNT++; L++;}
    printf("%d",CNT); OutDeg[I]=CNT;
   }
  puts("\n");

  getchar();

  DisplayArrayD(A,B,'D');

               /****** 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';
   S1=Buf; S2=NAME;  while (*S1!='\0') {*S2=*S1; S1++; S2++;};   *S2='\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=OutDeg[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 links */

                /* 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;
   SORTAB(A,B);

   A[0]=Nlinks;
   A[Nlinks+1]=B[Nlinks+1]=0;
   if ((N==B[0]) && (OutDeg[N]==1)) B[0]--;
 /*  goto LP; */
  }

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



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