/* MaxFlow.c */
/* algorithm in book by T.C. Hu, Page 47 */

/* Central idea uses breadth-first-search, without using recursion
The two arrays BUF1 and BUF2 will contain nodes, PP,QQ point to their first
    coordinates, P,Q point to their internal coordinates. Inside MAINLP,
    P,Q and PP,QQ swap arrays, but in a second array Q always points to
    neighbors of nodes that P points to in the first array.
    Zero 0 marks the end of nodes in each array.
*/


#include <stdio.h>
void EDITABW(int*,int*,int*,char*);
void PrintDAdj(int*,int*,int*);
void KBDtoABW(int*,int*,int*,char*);
int FiletoABW(int*,int*,int*,char*);
void SORTW(int*,int*,int*);
void SavetoFile(int*,int*,int*,char*);
int MaxFlow(int*,int*,int*,int*,int*,int*, int*,int*,int*,int*);
void GETLOCODEG(int*,int*,int*,int*);
int NodesLNum(int,int,int*,int*,int*,int*);
int MIN(int,int);
void ReverseLinks(int*,int*,int*, int*,int*,int*);

#define DataFile "GraphDataFile3.txt"
#define NN 1301    /* maximum number of links = NN-1,  NN = (MM-1)(MM-1)/2 +1 */
#define MM 51      /* maximum number of nodes = MM-1 */
#define INF 0XFFFFFF

void main(void)
{
 int K,Nlinks,Nnodes,             A[NN],B[NN],W[NN],LOC[MM],ODEG[MM],
                                 A2[NN],B2[NN],W2[NN],LOC2[MM],ODEG2[MM];
 char CH, NAME[16];


 puts("Where is the data for the Digraph?");
 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')) {KBDtoABW(A,B,W,NAME); goto NXT;}
 if ((CH=='F') || (CH=='f')) {if (FiletoABW(A,B,W,NAME)) goto NXT; else goto FIN;}
 puts("Error: enter either K or F");  goto INX;

NXT:
 Nnodes=B[0]; Nlinks=A[0]; 
 printf("Name of Digraph = %s    Number of nodes = %d    Number of links = %d\n",
      NAME,Nnodes, Nlinks);
      
 if (Nnodes < 4)
  {puts("The graph must have more than 3 nodes"); goto FIN;}

  GETLOCODEG(A,B,LOC,ODEG);
/*
 for (K=0; K<=Nlinks+1; K++) printf("%2d,",A[K]); puts("");
 for (K=0; K<=Nlinks+1; K++) printf("%2d,",B[K]); puts("");
 for (K=0; K<=Nlinks+1; K++) printf("%2d,",W[K]); puts("");
 puts("LOC,ODEG");
 for (K=1; K<=Nnodes; K++) printf("(%d)%d ",K,LOC[K]); puts("");
 for (K=1; K<=Nnodes; K++) printf("(%d)%d ",K,ODEG[K]); puts("\n");
*/

EDLP:
 PrintDAdj(A,B,W);
 printf("\nNeed to make changes? Y/N  "); CH=(char)getchar(); getchar();
  if ((CH=='Y') || (CH=='y')) {EDITABW(A,B,W,NAME); goto EDLP;}

 printf("Save array to file? Y/N  "); CH=(char)getchar(); getchar();
  if ((CH=='Y') || (CH=='y')) SavetoFile(A,B,W,NAME);

 Nlinks=A[0]; Nnodes=B[0];

 GETLOCODEG(A,B,LOC,ODEG);
 ReverseLinks(A,B,W,A2,B2,W2);
 GETLOCODEG(A2,B2,LOC2,ODEG2);
/*
 for (K=0; K<=Nlinks+1; K++) printf("%2d,",A2[K]); puts("");
 for (K=0; K<=Nlinks+1; K++) printf("%2d,",B2[K]); puts("");
 for (K=0; K<=Nlinks+1; K++) printf("%2d,",W2[K]); puts("\n");
 puts("LOC2,ODEG2");
 for (K=1; K<=Nnodes; K++) printf("(%d)%d ",K,LOC2[K]); puts("");
 for (K=1; K<=Nnodes; K++) printf("(%d)%d ",K,ODEG2[K]); puts("");
*/


 K = MaxFlow(A,B,W,LOC,ODEG,A2,B2,W2,LOC2,ODEG2);
 if (!K) {puts("Error in sub-program"); goto FIN;}
 printf("Maximum flow from entry node 1 to exit node %d  =  %d\n",Nnodes,K);


FIN:
 getchar();
}

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

int MaxFlow(int *A, int *B, int *CAP, int *LOC1, int *ODEG1, int *A2, int *B2, int *CAP2, int *LOC2, int *ODEG2)
{
 int H,I,J,K,L,N,Nnodes,Nlinks,MFLOW,ENDL,
    *P,*Q,*PP,*QQ,
   PREV[MM],Nstate[MM],E[MM],FBN[MM],
     BUF1[MM],BUF2[MM],
 /* P,Q point internally to BUF1, BUf2, *PP,QQ point to their initial entries */
   FL[NN];

 B2[0]=Nnodes=B[0];  A2[0]=Nlinks=A[0];

 for (L=1; L<=Nlinks; L++) FL[L]=0;   /* start with zero flow thru all links */


RESTART: /* attempt to assign new labels to all nodes in graph including exit */
  /* erase labels on all nodes: */
 for (N=0; N<=Nnodes; N++) {PREV[N]=Nstate[N]=FBN[N]=0; E[N]=INF;}
 BUF2[0]=0; BUF1[0]=1; BUF1[1]=0; /* start with entry node 1 in a BUF1 */
 PP=BUF2; QQ=BUF1;
 FBN[1]=+1;  Nstate[1]=1;  PREV[1]=0; E[1]=INF;

MAINLP:      printf("BUF1[0]=%d BUF1[1]=%d BUF2[0]=%d BUF2[1]=%d\n",
              BUF1[0], BUF1[1], BUF2[0], BUF2[1]);
  /* switch arrays second array becomes first array, first , second */
 P=QQ; Q=PP; PP=P; QQ=Q;   /* swap pointers to BUF arrays */
             printf("@ BUF1[0]=%d BUF1[1]=%d BUF2[0]=%d BUF2[1]=%d\n",
              BUF1[0], BUF1[1], BUF2[0], BUF2[1]);

 /* Note: in what follows, if E[*Q]>0 and Nstate[*Q]=0
       then Nstate[*Q]=1 (node *Q receives a label) */

 while (*P)
  {          /* working with outgoing links from node *P */
    printf("BUF1[0]=%d BUF2[0]=%d\n",BUF1[0],BUF2[0]);
         printf("*P=%d\n",*P);
         printf("LOC1P=%d\n",LOC1[*P]);
         printf("ODEG1P=%d\n",ODEG1[*P]);

   /* I=BUF1[*P] */ ENDL=LOC1[*P]+ODEG1[*P] - 1 ;
   for (L=LOC1[*P]; L<=ENDL; L++)
    {                  /* using L, J runs through all neighbors of node *P */
     J=B[L];   /* pair *P->J has link number L */
     if ((!Nstate[J]) && (FL[L]<CAP[L]))
      {
       *Q=J;  Q++;                printf("J=%d\n",J);
       E[J] = MIN(E[*P], CAP[L]-FL[L]);
        PREV[J]=*P; FBN[J]=+1;  Nstate[J]=1;  /* neighbor J gets a label */
        if (J==Nnodes)  goto STEP2;
      }
    } /* end for L */

/* working with incoming links to node *P */
   ENDL=LOC2[*P] + ODEG2[*P] - 1;
   for (L=LOC2[*P]; L<=ENDL; L++)
    {
     J=B2[L];     /* pair J<-*P has link number L */
     if ((!Nstate[J]) && (FL[L]))    /* flow exists in link */
      {
       E[J] = MIN(E[*P],FL[L]);
       PREV[J]=*P; FBN[J]=-1; Nstate[J]=1;
       BUF2[*Q]=J; Q++;
      }
    }  /* end for L */
   Nstate[*P]=2;          /* all neighbors of node *P have labels */
   P++;
 } /* end for while *P */
 *Q=0;                    /* end of nodes in BUF to which QQ points */


  if (!Nstate[Nnodes]) {puts("XXXXX"); getchar(); goto MAINLP;}

  if (!*Q)
   {      /* labelling was forced to stop before reaching exit node */

   for (L=1; L<=Nlinks; L++) printf("[%d -> %d]%d  ",A[L],B[L],FL[L]); puts("");

    puts("\nMinimum Cut:");
    printf("  Set with entry node 1:  ");
    for (N=1; N<=Nnodes; N++) if (Nstate[N]) printf("%d ",N); puts("");
    printf("  Set with exit node %d:  ",Nnodes);
    for (N=1; N<=Nnodes; N++) if (!Nstate[N]) printf("%d ",N); puts("");
    puts("");

    MFLOW=0;
    for (L=1; L<=Nlinks; L++) if ((Nstate[A[L]]) && (!Nstate[B[L]])) MFLOW+=FL[L];
    printf("Sum of flow across cut toward exit node %d  = %d\n",Nnodes,MFLOW);
    K=0;
    for (L=1; L<=Nlinks; L++) if ((!Nstate[A[L]]) && (Nstate[B[L]])) K+=FL[L];
    printf("Sum of reverse flow across cut toward entry node 1  = %d\n",K);
    MFLOW-=K;
    return MFLOW;
   }

 if (!Nstate[Nnodes]) goto MAINLP;   /* exit node not yet reached */

STEP2:
/* exit node has received a label (E[Nnodes], PREV[Nnodes], FBN[Nnodes]) */
  H=E[Nnodes];      printf("H=%d\n",H);
/* H = max additional flow that can be added to/subtr from every link
         in the backward path from exit node to entry node 1 */

  J=Nnodes; I=PREV[J];        /* J <- I */
 while (I)
  {L=LOC1[I]; while (B[L]!=J) L++; FL[L] = FL[L] + FBN[J]*H; J=I; I=PREV[I];}
 goto RESTART;

}

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

void GETLOCODEG(int *A, int *B, int *LOC, int *ODEG)
{
 int K,L,N,Nnodes,CNT;

 L = A[0];  Nnodes=B[0];      /* A[0] = Nlinks */
 LOC[0]=0; LOC[Nnodes+1]=A[0]+1;
 while (L>0)
  {
   K=L; N=A[L];  CNT=0;
   while (A[K]==N) {CNT++; K--;}
   LOC[N]=K+1; ODEG[N]=CNT;
   L=K;
  }


 return;
}

/********** Given NODES I,J  to find invisible number of link I -> J **********/

int NodesLNum(int I, int J, int *A, int *B, int *LOC, int *ODEG)
{
 int L,CNT;

 if ((I<1)||(I>B[0]) ||  (J<1) || (J>B[0])) return 0;

 L=LOC[I];  CNT=ODEG[I];
 while (CNT) {if (B[L]==J) return L; L++; CNT--;}
 return 0;
}

/****************** editing weighted adjacency arrays **********************/

void EDITABW(int *A, int *B, int *W, char *NAME)
{
 int H,I,J,K,Nnodes,Nlinks,  *P,*Q,*R,      C[MM][MM],D[MM][MM];
 char *S,Str[NN];

 Nnodes=B[0]; K=1;
 for (I=1; I<=Nnodes; I++)               /* copy A,B,W into C */
  {
   J=0;
   while (A[K]==I) {J++; if (B[K]>I) {C[I][J]=B[K]; D[I][J]=W[K];} K++;}
   D[I][0]=C[I][0]=J; /* Use C,D equivalent of weighted short adjacency array */
  }

LP:
 puts("Input integer:");
 printf("(node number) between 1 and %d\n",Nnodes);
 puts("0 (zero) to terminate editing, 1 to edit NAME of graph");

 scanf("%d",&I); getchar();
 if (!I) goto ToABW;                      /* no more editing; send it to ABW */
 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<16; K++) NAME[K]=Str[K];
   goto LP;
  }

 printf("all the given as neighbors#weights of (%d) are:  ",I);
 K=C[I][0];
 for (J=1; J<=K; J++) if (C[I][J]>I) printf("%d,",C[I][J]);
 printf("#");
 for (J=1; J<=K; J++) if (C[I][J]>I) printf("%d,",D[I][J]);
 printf("\ntype in ENTIRE correct line of neighbors#weights of(%d):  ",(I));
  gets(Str);

 J=0; S=Str;
LPLine1:          /* Convert ASCII digits to integers = neighbors of I */
 if (*S=='\0') {C[I][0]=D[I][0]=J; goto LP;}
 if (*S=='#') goto Weights;
 if ((*S<'0') || (*S>'9')) {S++; goto LPLine1;}

 H=0;
 while ((*S>='0') && (*S<='9')) {H = 10*H + (int)*S - 48;  S++;}
 if ((H>I)&&(H<=Nnodes)) {J++; C[I][J] = H;} /* (Node)I has neighbor H in J-th place */

Weights: J=0;                 /* S = '#' */
LPLine2:        /* Convert ASCII digits to integers - weights on links */
 while ((*S<'0') || (*S>'9')) S++;
 H=0;
 while ((*S>='0') && (*S<='9')) {H = 10*H + (int)*S - 48;  S++;}
 if ((H>I)&&(H<=Nnodes)) {J++; D[I][J] = H;} /* link I-C[I][J] has weight H */
 if (*S=='\0') {C[I][0]=D[I][0]=J; goto LP;}
 goto LPLine2;

ToABW:
         /* return data in C[ ][ ] and D[ ][ ]  to A,B,W */
 P=A; Q=B; R=W; P++; Q++; R++;   Nlinks=0;
 for (I=1; I<=Nnodes; I++)
  {
   K=C[I][0];
   for (J=1; J<=K; J++) {*P=I; *Q=C[I][J]; *R=D[I][J]; P++; Q++; R++;}
   Nlinks+=K;
  }
  A[0]=Nlinks;
  SORTW(A,B,W);

 return;
}

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

void KBDtoABW(int *A, int *B, int *W, char *NAME)
{
 int H,I,K,Nnodes,Nlinks;
 char *S,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);
 S=Str; for (K=0; K<10; K++) {NAME[K]=*S; S++;} *S='\0';

 printf("Input number of nodes in the graph:  "); scanf("%d",&Nnodes);getchar();
 B[0]=Nnodes;
 puts("Input EVERY neighbor after each (node):");

               /******** Convert input list to AB **********/
 K=0;
 for (I=1; I<=Nnodes; I++)
  {
   printf("(%d),",I);       /* for (node) I ... */
   gets(Str); S=Str;   /* Str catches all the ASCII digits of neighbors */

 LPLine:          /* Convert ASCII digits to integers = neighbors of I */
   if (*S=='\0') goto NxtI;
   if ((*S<'0') || (*S>'9')) {S++; goto LPLine;}
   H=0;
   while ((*S>='0') && (*S<='9')) {H = 10*H + (int)*S - 48;  S++;}
   if ((I==H) || (H>Nnodes) || (H<=0)) goto LPLine;  /* omit */
    K++; A[K]=I; B[K]=H;         /* For linked pair I->H */
   goto LPLine;
 NxtI:
  }
   A[0]=Nlinks=K; B[0]=Nnodes;
   A[K+1]=B[K+1]=W[K+1]=W[0]=0;

         /*********** input weights ***********/

 printf("Input weights for each of the following %d links:\n",Nlinks);
 for (K=1; K<=Nlinks; K++)
  {printf("%d->%d  ",A[K],B[K]); scanf("%d",&W[K]); getchar();}

/*

 for (K=0; K<Nlinks+1; K++) printf("%2d,",A[K]); puts("");
 for (K=0; K<Nlinks+1; K++) printf("%2d,",B[K]); puts("");
 for (K=0; K<Nlinks+1; K++) printf("%2d,",W[K]); puts("");
             getchar();
*/


 SORTW(A,B,W);

 return;
}

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

int FiletoABW(int *A, int *B, int *W, char *NAME)
{
 int H,I,K,CNT,Nlinks,Nnodes,    *P,*Q,*R;
 char CH,TITLF[]=DataFile,    *S,          GrStr[NN];
 FILE *F;

  if ((F=fopen(TITLF,"r+"))==NULL)
    {printf("Cannot find file %s\n",TITLF); return 0;}

  CH = (char)fgetc(F);  S=GrStr;
  while (CH != '[') CH = (char)fgetc(F);   /* pass over everything before [ */
  *S=CH;         /* CH =  [ */
  S++;

  CH = (char)fgetc(F); if (CH=='d') CH='D';
  if (CH!='D')
   {puts("Data Array in file not marked 'D' (after '[') for Ugraph"); return 0;}
  *S=CH; S++;

 while (CH != ']') {CH = (char)fgetc(F); *S=CH; S++;};
 fclose(F);

          /********** GrStr to AB **********/

 P=A; Q=B;  P++; Q++; S=GrStr;  R=W;  Nlinks=Nnodes=0;
 while (*S!='"') S++;

     /* *S='"';  get name */
 I=0; S++;
 while (*S!='"') {NAME[I]=*S; S++; I++;} NAME[I]='\0';

 while (*S!='(') S++;
                                  

NEWCLUSTER:
 while (*S!='(') S++;    /* here *S=( */
 S++; H=0;
 while (*S!=')') {H = 10*H + *S-48; S++;}   /* (H) storage */
 if (H>Nnodes) Nnodes=H;
 S++;

 CNT=0;
LP:               /* neighbors of H */
  if (*S==',') S++;
  while (*S==' ') S++;
  if (*S==']') {*P=*Q=0; A[0]=Nlinks; B[0]=Nnodes; return Nnodes;}
  if (*S=='#') goto WEIGHTS;
  K=0; while ((*S>='0') && (*S<='9')) {K = 10*K + *S-48; S++;}
  if (!K) goto NEWCLUSTER;
  if (K>Nnodes) Nnodes=K;              
  *Q=K; *P=H; P++; Q++;  Nlinks++; CNT++; /* H stored in A[], K stored in B[] */
 goto LP;

WEIGHTS:
  S++;
  while (CNT>0)
   {
    if (*S==',') S++;
    K=0; while ((*S>='0') && (*S<='9')) {K = 10*K + *S-48; S++;}
    R++; *R=K;        
    CNT--;
   }
  if (*S==',') S++;      
 if (*S!=']') goto NEWCLUSTER;


 B[0]=Nnodes;  A[0]=Nlinks;
 SORTW(A,B,W);

 return 1;    /* dummy non-zero return */
}

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

void SORTW(int *A, int *B, int *W)
{
 int I,J,K,M,N,TEMP,  D[NN];

  N=A[0];
 for (K=1; K<=N; K++) D[K]=A[K]*1000000 + B[K]*10000 + W[K];
 for (I=1; I<N; I++)
  {
   M=D[I]; K=I;
   for (J=I+1; J<=N; J++) if (D[J]<M) {M=D[J]; K=J;}
   if (K!=I) {TEMP=D[I]; D[I]=D[K]; D[K]=TEMP;}
  }
       /****** Removal of duplicates in D[ ] *******/

  J=1;
  for (K=2; K<=N; K++) if (D[K-1] != D[K]) {J++; D[J]=D[K];}
  N=J;  /* possibly different number of links */

       /******** place results back in A,B,W *********/
       
 for (K=1; K<=N; K++)
  {A[K]=D[K]/1000000; TEMP=D[K]%1000000; B[K]=TEMP/10000; W[K]=TEMP%10000;}
 A[0]=N;  A[N+1]=0; B[N+1]=0; W[N+1]=0;
 return;
} 


/*************** print short adjacency array with weights ********************/

void PrintDAdj(int *A, int *B, int *W)
{
 int I,K=1,KK,Nnodes,FLAG;

 Nnodes=B[0];
 for (I=1; I<=Nnodes; I++)
  {
   printf("(%d)",I); KK=K; FLAG=0;
   while (A[K]==I) {printf(",%d",B[K]); K++; FLAG++;}
   putchar(',');
   if (FLAG)
    {
     putchar('#'); K=KK;
     while (A[K]==I) {printf("%d,",W[K]); K++;}
    }
   printf("   ");
  }
}

/****************** Save weighted Darray to data file *******************/

void SavetoFile(int *A, int *B, int *W, char *NAME)
{
 int H,I,K,KK,T,DIG,Nnodes,CNT;
 char TITLG[]=DataFile,    *S,          GrStr[NN];
 FILE *G;

 S=GrStr;
      /* Construct [UW"NAME" weighted Darray] in GrStr */
 *S='['; S++; *S='D'; S++; *S='W'; S++; *S='"';  S++;
 K=0; while (NAME[K] != '\0') {*S=NAME[K]; K++; S++;}
 *S='"'; S++;
 *S=' '; S++;
 Nnodes=B[0];
 K=1;
 for (I=1; I<=Nnodes; I++)
  {
   *S='('; S++; H=I;
   T=1; while (T<=H) T*=10; T=T/10;
   while (T) {DIG=H/T + 48; *S=(char)DIG; S++;  H=H%T; T=T/10;}
   *S=')'; S++;


   KK=K;   /* Convert all neighbors of (I) to chars */
   CNT=0;
   while (A[K]==I)
   {
    H=B[K]; 
    T=1; while (T<=H) T *= 10; T=T/10;
    while (T) {DIG=H/T + 48; *S=(char)DIG; S++; H=H%T; T=T/10;}
    *S=','; S++;   CNT++;
    K++;
   }
  if (!CNT) goto NXTCluster;
  *S='#'; S++;
  K=KK;  /* convert all weights on links on (I) to neighbors */
   while (A[K]==I)
   {
    H=W[K];
    T=1; while (T<=H) T *= 10; T=T/10;
    while (T) {DIG=H/T + 48; *S=(char)DIG; S++; H=H%T; T=T/10;}
    *S=','; S++;
    K++;
   }

NXTCluster:
  *S=' '; S++; *S=' '; S++;

 } /* end for I */

/* ToFile: */
                           puts(GrStr);   getchar();
 G=fopen(TITLG,"w");

fputs(GrStr,G);
 fclose(G);

}

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

 int MIN(int X, int Y) {if (X<Y) return X; else return Y;}

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

void ReverseLinks(int *A, int *B, int *W, int *A2, int *B2, int *W2)
{  /* reverse all directed links in A -> B into A2 -> B2  =   B <- A */
 int L, Nlinks;

 Nlinks = A2[0] = A[0];  B2[0] = B[0];

 for (L=1; L<=Nlinks; L++) {A2[L] = B[L]; B2[L] = A[L]; W2[L]=W[L];};
 SORTW(A2,B2,W2);
 return;
}

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