/* TreeORConnected.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 GetDEGLOC(int*,int*,int*,int*);
void EDITAB(int*,int*,char*);
void ABtoFile(int*,int*,char*);
int Connected(int*,int*,int*);

void main(void)
{
 int  K,Npairs,Nnodes,      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);

 Npairs=A[0]; Nnodes=B[0];
 printf("Ufile %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:
*/
 GetDEGLOC(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);
*/

 K= Connected(A,B,LOC);
 if (K==2) puts("Graph is connected and is a tree");
 if (K==1) puts("Graph is connected but not a tree");
 if (!K) puts("Graph is not connected");

 FIN:
 getchar();
}

/************************* Is graph connected, tree ? ************************/

int Connected(int *A, int *B, int *LOC)
{
 /*
 H=path index, I=(node), J=index of neighbors, NCNT = count of unvisited nodes,
  VisNod[I] (Boolean) 0 iff node I has not been visited,
  CNTUVN[I] count of UnVisited Neighbors of node I,
 */
 
 int H=0,I,J,K,Nnodes,   PATH[MM],VisNod[MM];

 Nnodes=B[0];    PATH[0]=0;
 for (I=1; I<=Nnodes; I++) VisNod[I]=0;

  I=1;                          /* start path at node 1 */

LP1:                           /* add node I to end of path */
  ++H; PATH[H]=I;              /* Node I becomes the latest node in the path */
  VisNod[I]=1;                 /* mark node I as visited */
  J=H;
LP2:
                  /* printf("H=%d I=%d\n",H,I); getchar(); */
  K=LOC[I];
  while ((A[K]==I) && (VisNod[B[K]])) K++;
  if (A[K]==I) {I=B[K]; goto LP1;}     /* found an unvisited nhbd B[K] of I */

           /* to reach here node I must be a dead end, all neighbors visited */
          /* therefore, backtrack to find node in path with unvisited nhbr*/
  J--; I=PATH[J];    /*  printf("I=%d\n",I); */
  if (I) goto LP2;

 J=0; if (2*Nnodes - A[0] == 2) J=1;
 if (H==Nnodes)
  {
   printf("Path connecting all %d nodes:\n",Nnodes);
   H=1;
   for (K=1; K<=Nnodes; K++) {printf("%d ",PATH[H]); H++;}; puts("");
   J++;
   return J;
  }
 return 0;
}


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

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 and print three arrays *************/

void GetDEGLOC(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;
 /*
  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 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);    getchar();

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

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

 return;
}