/* Head of main program */
/* add or remove names of subprograms, symmetric graph-array GRAPH */


#include <stdio.h>
#define NN 1000        /* for larger general arrays */
#define MM 100         /* for smaller arrays */


int MAKEPATH(int*, int*);

void main(void)
{
 int Nints, Nobj, Npairs;
 int I,J,K,N,Nisoobj,Ncomp,CNT,CNTx,ERR,  *P,
  NEGOBJ[MM],  /* locations in GROUP array of objects with neg int-names */
  NUMPOS[MM],  /* NUMPOS[K]=number neighbors (pos nums) of object K */
  VISITED[MM], /* Used in sorting and listing objects in components */
  PATH[NN],

 /* Place zero before and after integer data for the graph, no zero inside */
  GRAPH[]={0,
  -1,11,20,34,  -2,6,30,  -3,5,7,12,   -4,23,  -5,3,18,32,  -6,2,10,19,27,
  -7,3,9,  -8,11,17,23,  -9,7,24,31,  -10,6,  -11,1,8,34,  -12,3,21,  -13,22,30,
  -14,34,  -15,24,25,32,   -16,  -17,8,  -18,5,32,  -19,6,  -20,1,26,
  -21,12,31,  -22,13,27,  -23,4,8,   -24,9,15,  -25,15,  -26,20,  -27,6,22,30,
  -28,31,  -29,  -30,2,13,27,  -31,9,21,28,  -32,5,15,18,  -33,  -34,1,11,14,
  -35,
       0};

 /************************ Get numbers *******************************/

 Nints=Nobj=Npairs=0;  

 P=&GRAPH[1];

 while (*P)
  {
   Nints++;
   if (*P<0) Nobj++;
   if (*P>0) Npairs++;
   P++;
  }


 printf("Number of objects in Graph = %d\n",Nobj);

 Nisoobj=0; puts("Isolated objects are:");
 for (K=1; K<=Nints; K++)
  if ((GRAPH[K]<0) && (GRAPH[K+1]<=0)) {printf("%d,",-GRAPH[K]); Nisoobj++;}
 puts("");
 printf("Number of isolated objects = %d\n",Nisoobj);
 printf("Number of links in the graph = %d\n",Npairs/2);
 printf("Number of linked pairs in the array = %d\n",Npairs);

 puts("");
 GRAPH[0]=Nints;
 printf("Number %d (length of array) inserted at beginning of array ",Nints);
 puts("for computer use");
 puts("Number 0 (end of array marker) after array for computer use");

 /*
 printf("Graph-Array = %d (first number in array, for computer use\n",GRAPH[0]);
 for (K=1; K<=Nints; K++)
  {if (GRAPH[K]<0) printf("  "); printf("%d,",GRAPH[K]);}
 printf("\n             %d    end of array marker\n",GRAPH[Nints+1]);
*/

  puts("\n");
 for (K=1; K<MM; K++) NUMPOS[K]=0;
 P=GRAPH;  P++;
 while (*P)
  {
   /* assume *P<0 here */   /* printf("%d ",*P); */

    K=-*P; CNT=0; P++;
    while (*P>0) {CNT++; P++;}
    NUMPOS[K]=CNT;
  }
/*
  puts("after -object x,y is the number of neighbors:");
  for (K=1; K<=Nobj; K++)
   printf("-%d,%d ",K,NUMPOS[K]);
  puts("\n");
*/
  for (K=1; K<MM; K++) NEGOBJ[K]=0;
  for (K=1; K<=Nints; K++) if (GRAPH[K]<0) NEGOBJ[-GRAPH[K]]=K;
/*
  puts("after -object x,y is the index of the object in the GRAPH array");
  for (K=1; K<=Nobj; K++) printf("%-d,%d  ",K,NEGOBJ[K]);
  puts("\n");
*/  

 /*********** Check graph for links bidirectional (symmetry) ***********/
  ERR=0;
  for (K=1; K<Nobj; K++)
   {
    CNT=NUMPOS[K];
    while (CNT)
     {
      J = GRAPH[NEGOBJ[K]+CNT];
      CNTx=NUMPOS[J];
      while (CNTx)
       {
        I=GRAPH[NEGOBJ[J]+ CNTx];
        if (I==K) goto NXT2;            /* link K-J is bidirectional */
        CNTx--;
       }
      printf("ERROR:  link %d <-- %d NOT bidirectional\n",J,K); ERR++;
 NXT2:
      CNT--;
     }
   }
 if (ERR) printf("Repair Graph array by addition or removal of ");
 if (ERR==1) puts("some natural number (= neighbor)");
 if (ERR>1) printf("%d natural numbers (= neighbors",ERR);
 if (ERR)
  {puts("Use one of the numbers in each pair in the directed links"); goto FIN;}
  else puts("All links bidirectional, Graph-array is symmetric\n");

 N=MAKEPATH(GRAPH,PATH);

 puts("\nComponents of connected objects:");

 CNT=0;
 Ncomp=0;
 for (K=0; K<N; K++)
  if (PATH[K])
   {printf(" %d",PATH[K]); CNT++;}
      else
   {Ncomp++; printf("\nA simple path covering component #%d:\n",Ncomp);}
 printf("\n%d = length of the combined %d paths, covering the entire graph\n",
     CNT,Ncomp);

 printf("\n\nThere are %d components. In nontrivial components:\n",Ncomp);
 P=PATH;
 for (J=1; J<=Ncomp; J++)
  {
   P++;
   for (K=0; K<=Nobj; K++) VISITED[K]=0;  CNT=0;
   while (*P) {VISITED[*P]=1; CNT++; P++;}
   if (CNT==1) continue;
   CNT=0; for (K=0; K<=Nobj; K++) if (VISITED[K]) CNT++;
   printf("%d object(s) in component #%d:\n",CNT,J);
   for (K=0; K<=Nobj; K++) if (VISITED[K]) printf(" %d",K); puts("");
  }

FIN:
 getchar();
}

/*********************** End of main program *********************************/


/*****subPROGRAM to make simple paths covering all components ************/

/* receive pointer FA to a FULL graph array, ignoring first integer (count) and
   terminating by a final zero, and a pointer PATH to an array to
    contain the entire sequence of objects that form SIMPLE paths, each path
    covering a component, paths separated by 0; every object in the graph
    appears at least once in exactly one of the paths */
#define NN 1000
int MAKEPATH(int *FA, int *PATH)
{
 int I,J,K,CNT,Nobj,STARTOBJ,  *P,   NEGOBJ[NN],NUMPOS[NN],VISITED[NN],PREV[NN];

 /********** Preparation: Activate Nobj, NEGOBJ, NUMPOS, VISITED ***********/



 P=FA; I=Nobj=0;
 while (*P>=0) {P++; I++;}

 while (*P)
  {                                /*  printf("*P=%d I=%d  ",*P,I); */
   K=-*P; NEGOBJ[K]=I; Nobj++;  CNT=0; I++; P++;
   while (*P>0) {CNT++; P++; I++;} NUMPOS[K]=CNT;
  }
 for (K=Nobj; K>0; K--) VISITED[K]=PREV[K]=0;
 /* start with all objects unvisited, no previous objects */


  /**************  Actual construction of path(s) *******************/


 *FA=I;     /* number of neg and pos int-names in FA */
  I=0;    /* I = index for PATH; K = object at location I */
  PATH[0]=0;


/* Start with an object in a new component */
LP1:
  /*  0 before and after all objects in a path covering a component */
 K=0;
 for (J=Nobj; J>0; J--) if (!VISITED[J]) K=J;
      /* try to get a startobj in a new component */
 if (!K) {I++; PATH[I]=0; return I-1;}    /* All objects visited, end program */
 STARTOBJ=K;  I++; PATH[I]=STARTOBJ; PREV[K]=0;        VISITED[STARTOBJ]=K;
          /* first object in both path an new component */

LP2:
  while (NUMPOS[K])      /* Increase path forward with new objects */
  {
   J = FA[NEGOBJ[K] + NUMPOS[K]];   NUMPOS[K]--;   if (VISITED[J]) goto LP2;
   PREV[J]=K;
   I++; PATH[I]=K=J;  VISITED[K]=K;
  }

  /* Path reached a dead-end (object has no unvisited neighbors */
        /* Start backtracking in path;  J = index during backtracking */

 while (!NUMPOS[K])
  {
   K=PREV[K];
   I++; PATH[I]=K;
   if (!K) goto LP1;
  }
 goto LP2;
}