/* MaxFlow.c  (MaxFlow4.c) */

#include <stdio.h>

#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

#include "..\\SubProgs\\SORTW.c"
#include "..\\SubProgs\\EDITABW.c"
#include "..\\SubProgs\\PrintDAdj.c"
#include "..\\SubProgs\\KBDtoABW.c"
#include "..\\SubProgs\\FiletoABW.c"
#include "..\\SubProgs\\SavetoFile.c"
#include "..\\SubProgs\\GetLocOdeg.c"
#include "..\\SubProgs\\MIN.c"

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*);
void GetLocOdeg(int*,int*,int*,int*);
int MaxFlow5(int*,int*,int*);
int MIN(int,int);

void main(void)
{
 int K,Nlinks,Nnodes,             A[NN],B[NN],W[NN];
 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); SORTW(A,B,W); goto NXT;}
 if ((CH=='F') || (CH=='f'))
  {if (FiletoABW(A,B,W,NAME)) {SORTW(A,B,W); 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);

/*
 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); SORTW(A,B,W); goto EDLP;}

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

 K=MaxFlow5(A,B,W);
 printf("MaxFlow=%d\n",K);

FIN:
 getchar();
}

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


int MaxFlow5(int *A,int *B,int *Cap1)
{
 int H,I,J,K,L,N,Nnodes,Nlinks,ExitNode,CNT,SUM=0,
  *P,*Q, *PP,*QQ,*Dummy,
  Loc1[MM],Odeg1[MM],
  A2[NN],B2[NN],Cap2[NN],Loc2[MM],Odeg2[MM],  /* reversed links */
  Flow[NN],                           /* flow in links */
  Buf1[MM],Buf2[MM],  /* contain nodes, PP points to one of these, QQ to other */
  E[MM],Prev[MM],FBN[NN],            /* together form a label assigned to nodes */
  Nstate[MM];  /* state of node: 0 unlabeled, 1 labeled, 2 all neighbrs labeled */



  GetLocOdeg(A,B,Loc1,Odeg1);

 B2[0]=ExitNode=Nnodes=B[0]; A2[0]=Nlinks=A[0];    Cap2[0]=0;
 for (L=1; L<=Nlinks; L++) {A2[L]=B[L]; B2[L]=A[L]; Cap2[L]=Cap1[L];}
 SORTW(A2,B2,Cap2);

 L=Nlinks;
LPX:
   CNT=0; N=A2[L];
   while (A2[L]==N) {CNT++; L--;}
   Loc2[N]=L+1; Odeg2[N]=CNT;
   if (L) goto LPX;
  /*################################*/
   Flow[0]=INF;
  for (L=1; L<=Nlinks; L++) Flow[L]=0;
RESTART:                       /* Keep only any flows in each link */
 for (N=0; N<=Nnodes; N++)
  {E[N]=INF; Prev[N]=0; FBN[N]=0; Nstate[N]=0;}  /* erase all labels on nodes */
 E[1]=INF;                    /* any amount of flow allowed to enter entry node */
 Prev[1]=0; FBN[1]=+1;        /* Pseudo-node 0 previous to entry node 1 */
 Nstate[1]=1;                 /* entry node has a label */
 Buf1[0]=1; Buf1[1]=0;        /* Buf1 starts with single node, entry node 1 */
 Buf2[0]=0;                   /* Buf2 starts empty */
 PP=Buf1; QQ=Buf2;            /* Start with PP -> Buf1, QQ -> Buf2 */

MAINLP:
 P=PP; Q=QQ; *Q=0;

 while (*P)
  {
   I=*P;
   L=Loc1[I]; CNT=Odeg1[I];   /* working with outgoing links of I */
   while (CNT)
    {
     J=B[L];                 /* J = outgoing neighbor of I */
     if ((!Nstate[J]) && (Flow[L]<Cap1[L]))   /* J unlabeled and room for more flow */
      {
       E[J]=MIN(E[I],Cap1[L]-Flow[L]);
       Prev[J]=I; FBN[J]=+1;  Nstate[J]=1;
       *Q=J; Q++; *Q=0;
       if (J==ExitNode) goto STEP2;
      }

     L++; CNT--;
    }

   L=Loc2[I]; CNT=Odeg2[I];   /* working with incoming links of I */
   while (CNT)
    {
     J=B2[L];                 /* J = incoming neighbor of I */
     if  ((!Nstate[J]) && (Flow[L]))   /*  flow can be deminished */
      {
       E[J]=MIN(E[I],Flow[L]);
       Prev[J]=I; FBN[J]=-1;  Nstate[J]=1;
       *Q=J; Q++; *Q=0;
      }
     L++; CNT--;
    }
   Nstate[I]=2;
   P++;
  } /* end *P>0 */


 if (!*QQ)    /* No labels could be assigned to nodes in QQ -> Buf */
  {
   puts("\nLinks with flow material in them:");
   for (L=1; L<=Nlinks; L++)
    if (B[L]!=ExitNode) printf("[%d-%d]%d, ",A[L],B[L],Flow[L]); else
     {printf("*[%d-%d]%d, ",A[L],B[L],Flow[L]); SUM+=Flow[L];}
    puts("\n");

   printf("Sum of the flows in all incoming *links to exit node %d:\n",ExitNode);
   return SUM;
  }

 if (!Nstate[ExitNode])
  {                     /* ExitNode not yet with label */
   Dummy=PP; PP=QQ; QQ=Dummy;  /* Swap Bufs */
   goto MAINLP;
  }

STEP2: /* exit node received a label */
  H=E[ExitNode];
/* 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++; Flow[L] = Flow[L] + FBN[J]*H; J=I; I=Prev[I];}

 goto RESTART;

}