/* CoupletsToGraph.c */
/* Convert pairs of linked objects in file INPUTXY (XY = 01, 02, 03, ...
    into Graph-Array form (single array) */

#include <stdio.h>
#define NN 1000
int TOARRAY(int*,int*);
int SUPERSORT(int*,int*,int);
void TOGRAPH(int*,int*,int*,int);

void main(void)
{
 int I,K=0,N,A[NN],B[NN],C[NN];

 N = TOARRAY(A,B);     /* convert data array in file to two arrays, length N */
 if (N)
  {
   for (I=0; I<N; I++)
    if (B[I])  {printf("%d-%d ",A[I],B[I]); K++;} else printf("%d ",A[I]);
   printf("\n%d linked pairs of objects,  %d isolated objects\n",K,N-K);
   puts("Press Enter key to continue");
   getchar();
  }
 else
  {
   puts("Press enter key to terminate program");
   getchar(); return;   
  } 

 N = SUPERSORT(A,B,N);   /* super sort arrays A,B */

 for (I=0; I<N; I++) printf("%d-%d ",A[I],B[I]);
 printf("\n%d sorted linked pairs of objects\n",N);
 puts("duplicate linked pairs and isolated objects have been removed");

 TOGRAPH(A,B,C,N);  /* convert sorted pairs in A,B into C, Graph-Array. */

 printf("\nGraph: %d linked couples in single array form\n",N);
 K=C[0];
 for (I=0; I<=K; I++)
  if (C[I]>0) printf("%d,",C[I]); else printf(" %d,",C[I]); puts("");

  getchar();
}

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

 /* This subprogram accepts two array names (pointers *P,*Q) for two arrays
  that will contain linked pairs of integer-names of objects, and a third array
  name (pointer *R) locating the char array containing the complete name of the
  data file (*.txt) of linked pairs;
    The subprogram converts the integer-names in ASCII digits into binary
  integers and stores the results in arrays located by *P,*Q, left integer in
  array *P, right integer in array *Q;
    Also the subprogram returns the integer N of linked pairs */

 int TOARRAY(int* P, int* Q)
 {
  int N=0,TEMPP,TEMPQ;
  FILE *F; char CH, CHX,CHY, TITLF[]="INPUTXY.txt";

 puts("Input file number: 01,02,... (include the zero)");
 scanf("%c%c",&CHX,&CHY); getchar();
 TITLF[5] = CHX; TITLF[6] = CHY;

 if ((F=fopen(TITLF,"r"))==NULL)
  {printf("cannot open file %s\n",TITLF); return 0;}
 printf("Data for graph from file %s:\n",TITLF);

 CH=(char)fgetc(F);
LP:
 /* locate left number of couple */
 while ((CH<'0') || (CH>'9')) CH = (char)fgetc(F);

  /* read ASCII digits from file and convert to binary integer in TEMPP */
 TEMPP=0;
 while ((CH>='0') && (CH<='9'))
  {
   TEMPP = 10*TEMPP + (int)CH - 48;
   CH=(char)fgetc(F);
  }

 /* Locate right number of couple */
 while ((CH<'0') || (CH>'9')) CH = (char)fgetc(F);

 /* read ASCII digits from file and convert to binary integer in TEMPQ */
 TEMPQ=0;
 while ((CH>='0') && (CH<='9'))
  {
   TEMPQ = 10*TEMPQ + (int)CH - 48;
   CH=(char)fgetc(F);
  }
 /* if couple is 0-0 then end of data */
 if ((!TEMPP) && (!TEMPQ)) {fclose(F); return N;}   /* N = number of couples */


 *P=TEMPP; P++; *Q=TEMPQ; Q++; N++; /* store left,right int-names in P,Q */
  goto LP;                          /* continue getting more data */
}

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

 /* Sorting linked objects in arrays pointed to by *P,*Q;
    Isolated objects are deleted;


 */

 int SUPERSORT(int *P, int *Q, int N)
 {
  int I,J,K,MA,MB,TEMP,   *PSAV, *QSAV,   A[NN],B[NN],FLAG[NN];

  PSAV=P; QSAV=Q;  J=0;
  for (K=0; K<N; K++) FLAG[K]=1;

  for (I=0; I<N; I++)
   {
    if (*Q)                                   /* delete isolated objects */
     if (*P != *Q) {A[J]=*P; B[J]=*Q; J++;}
    P++; Q++;
   }

   N=J;           /* possibly new N (smaller) */

  for (I=0; I<N; I++) if (A[I]>B[I]) {TEMP=A[I]; A[I]=B[I]; B[I]=TEMP;}

  for (I=0; I<N; I++)
   {
    MA=A[I]; MB=B[I]; K=I;

    for (J=I+1; J<N; J++)
     {
      if (A[J]<MA) {K=J; MA=A[K]; MB=B[K];} else
      {if (A[J] == MA) if (B[J]<MB) {K=J; MA=A[K]; MB=B[K];}}
     }

    if (K!=I)
     {
      TEMP=A[I]; A[I]=A[K]; A[K]=TEMP;
      TEMP=B[I]; B[I]=B[K]; B[K]=TEMP;
     }
   } /* end I */

 if (A[0]==B[0]) FLAG[0]=0;
 for (K=1; K<N; K++)
  {
   if (A[K]==B[K]) FLAG[K]=0;                        /* Double link */
   if ((A[K]==A[K-1]) & (B[K]==B[K-1])) FLAG[K]=0;   /* Duplicate pair */
  }

 P=PSAV; Q=QSAV;  J=0;
 for (K=0; K<N; K++) if (FLAG[K]) {*P=A[K]; *Q=B[K]; P++; Q++; J++;}
 return J;
}

/******************** Graph in single array form *************************/

void TOGRAPH(int *P, int *Q, int *R, int N)
 {
  int I,K,X,*RSAV;

 RSAV=R;
 for (I=0; I<NN; I++) {*R=0; R++;} R=RSAV;

 P[N]=Q[N]=K=0;

 X=*P; R++;
 while (X)
  {
   *R=-X; R++; K++;
   while (X==*P) {*R=*Q; K++; R++; Q++; P++;}
   X=*P;
  }
                                           
 R++; *R=0;  *RSAV=K;
 return;
}