/* MaxFlow.c  T.C. Hu Page 47 */

#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*);
void GETLOCODEG(int*,int*,int*,int*);
int NodesLNum(int,int,int*,int*,int*,int*);
int MIN(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];
 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;}

 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("\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);
/*
 for (N=1; N<=Nnodes; N++) printf("(%d)%d ",N,LOC[N]); puts("");
 for (N=1; N<=Nnodes; N++) printf("(%d)%d ",N,ODEG[N]); puts("\n");
 getchar();

DUMMYLP:
 puts("input I,J"); scanf("%d,%d",&K,&N); getchar();
 printf("%d\n",NodesLNum(K,N,A,B,LOC,ODEG));
 goto DUMMYLP;
*/

 K = MaxFlow(A,B,W,LOC,ODEG);
 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 *ODEG)
{
 int H,I,J,K,L,N,N1,N2,Nnodes,Nlinks,MFLOW,END1,END2,ENDL,
   PREV[MM],Nstate[MM],E[MM],FBN[MM],   LOC2[MM],IDEG[MM],
     BUF1[MM],BUF2[MM],   /* nodes in BUF1 will have their neighbors in BUF2 */
   FL[NN],A2[NN],B2[NN],CAP2[NN];

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

 for (N=1; N<=Nlinks; N++) {A2[N]=B[N]; B2[N]=A[N]; CAP2[N]=CAP[N];}
 SORTW(A2,B2,CAP2);   
/*
  puts("A2,B2,W2");
 for (N=1; N<=Nlinks; N++) printf("%2d ",A2[N]); puts("");
 for (N=1; N<=Nlinks; N++) printf("%2d ",B2[N]); puts("");
 for (N=1; N<=Nlinks; N++) printf("%2d ",CAP2[N]); puts("\n");
*/

 GETLOCODEG(A2,B2,LOC2,IDEG);
/*
 puts("Data for incoming links   LOC2,IDEG");
 LOC2[1]=0;  /* 1 has no location (no incoming link in the graph)
 for (N=1; N<=Nnodes; N++) printf("(%d)%d ",N,LOC2[N]); puts("");
 for (N=1; N<=Nnodes; N++) printf("(%d)%d ",N,IDEG[N]); puts("");
*/


 for (L=0; L<=Nlinks; L++) FL[L]=0;

  /* BUF1[0] and BUF2[0]=N2 contain the number of nodes in them */
  /* Start with BUF1 and get entry node 1 from it */
  /* Previous Node to entry node is (Pseudonode) 0 PREV[1]=0; FBN[1]=+1; */
  /* Exists pseudo-link 0 -> 1 pointing to entry node and has link number 0 */
  /* unlimited amount of flow allowed through pseudolink into 1,  E[1]=INF; */
  /* Entry node 1 has a label   Nstate[1]=1;  */


 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 */
  /* erase labels on all nodes: */
 for (N=0; N<=Nnodes; N++) {PREV[N]=Nstate[N]=FBN[N]=0; E[N]=INF;}

 FBN[1]=+1;  Nstate[1]=1;
 BUF1[0]=BUF1[1]=1; /* (re)start with one node, the entry node, in BUF1 */

MAINLP:  /* BUF1 has a collection of BUF1[0] nodes, BUF2 is essentially empty */
  /* (index) N2 = total number of neighbor nodes in BUF2 at any time */
 END1=BUF1[0];  /* END1 = index of last node = number of nodes in BUF1 */
 /* in BUF1 are labeled nodes I, in BUF2 all their neighbors J, some to be labeled */
 /* Note: if E[J]>0 and Nstate[J]=0 then Nstate[J]=1 (J receives a label) */

 N2=0;
 for (N1=1; N1<=END1; N1++)
  {
   I=BUF1[N1]; ENDL=LOC1[I]+ODEG[I] - 1 ;
   /* working with outgoing links from node I */
   for (L=LOC1[I]; L<=ENDL; L++)
    {                  /* J runs through all neighbors of I */
     J=B[L];   /* pair I->J has link number L */
     if ((!Nstate[J]) && (FL[L]<CAP[L]))
      {
       E[J] = MIN(E[I], CAP[L]-FL[L]);
        PREV[J]=I; FBN[J]=+1;  Nstate[J]=1;
       N2++; BUF2[N2]=J;   if (J==Nnodes) goto STEP2;
      }
    } /* end for L */


   ENDL=LOC2[I] + IDEG[I] - 1;    /* working with incoming links to node I */
   for (L=LOC2[I]; L<=ENDL; L++)
    {
     J=B2[L];     /* pair J<-I has link number L */
     if ((!Nstate[J]) && (FL[L]))    /* flow exists in link */
      {
       E[J] = MIN(E[I],FL[L]);
        PREV[J]=I; FBN[J]=-1; Nstate[J]=1;
       N2++; BUF2[N2]=J;
      }
    }  /* end for L */
   Nstate[I]=2;
 } /* end for N1 */
   END2=BUF2[0]=N2;


  if (!N2)
   {      /* labelling was forced to stop before reaching exit node */
    puts("\nFlow through all links to produce a maximum flow");
     printf(" from entry node 1 to exit node %d:\n",Nnodes);
    for (L=1; L<=Nlinks; L++) printf("[%d-%d] %d,  ",A[L],B[L],FL[L]);
    puts("");

    puts("\nA minimum 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;
    puts("Links across cut and flow through them:");                     
    for (L=1; L<=Nlinks; L++)
     {
      if (Nstate[A[L]]>0) H=1; else H=0;
      if (Nstate[B[L]]>0) K=1; else K=0;
      J = H - K;
      if (J)
       {
        MFLOW = MFLOW + J*FL[L];
        printf("[%d-%d] %d,  ",A[L],B[L],J*FL[L]);
       }
     }
    puts(""); 
    return MFLOW;
   }


  if (!Nstate[Nnodes])
   {/* labelling of exit node not yet achieved. Copy BUf2 into BUF1 then
      get all the new neighbors of nodes in BUF1 into BUF2 */
    for (N=0; N<=END2; N++) BUF1[N]=BUF2[N];  /* BUF2 --> BUF1 */
    goto MAINLP;
   }

STEP2:
/* exit node received a label (E[Nnodes], PREV[Nnodes], FBN[Nnodes]) */
  H=E[Nnodes];
/* 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];
 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 L,N,Nnodes,CNT;

 L = A[0];  Nnodes=B[0];       /* A[0] = Nlinks */

 for (N=Nnodes; N>0; N--)
  {
   CNT=0;
   while (A[L]==N) {CNT++; L--;}
   LOC[N]=L+1; ODEG[N]=CNT;
  }
 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;}

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