/* TestMAKEPATH.c */
/* Make simple paths covering all components */

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

int MAKEPATH(int*,int*);

int Nints, Nobj, Npairs, Nisol;


void main(void)
{

 int I,K,N,CNT, *P,         PATH[NN],
  FA[]={0,
  -1,11,14,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,  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,7,22,30,
  -28,31,  -29,  -30,2,13,27,  -31,9,21,28,  -32,5,15,18,  -33,  -34,1,11,14,
       0};










   N=MAKEPATH(FA,PATH);

 printf("N=%d\n",N);
 for (K=0; K<=N; K++) printf("%d ",PATH[K]);  puts("\n");

 P=PATH; CNT=0;
 for (I=0; I<N; I++) {if (!*P) CNT++; P++;}

 P=PATH;
 for (K=1; K<=CNT; K++)
  {
   printf("Travel Covering component #%d\n",K);
   P++;
   while (*P) {printf("%d ",*P); P++;} puts("\n");
  }



 getchar();
}

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

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, no more additions to path */
 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;

}