/*****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;
  }
 printf("There are %d objects in the graph\n",Nobj);
 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;
}