About Me

Interest

Favorites

Photo Gallery

Programs

• fordalgo.cpp

fordalgo.cpp

This is a program that solves network flow problem using Ford-Fulkerson method. You need to know about "Flow Networks" to understand the problem. Flow networks are well explained in the book "Introduction to algorithms" by Thomas H. Coremen. Look into chapter 26 of this book. An introduction to flow network will be linked to this page shortly.

The program is tested and compiled using Borland c++ 5.02. It can also be compiled under Linux using "c++" compiler. For this you need to do some little change in the start of the program. The program takes input from file. Some test input file is provided below. See the pattern of the input data before making your own input file.

Lastly this program is originally a c program but I need to compile it using c++ compiler as the code contains cin and cout in some places. Actually I liked to take the advantage of cin and cout while coding. The using printf() requires lot of typing.

#include <iostream.h> // <-- if using Linux comment this line
#include <string.h>
#include <stdlib.h>
#include <stdio.h>
//#include <iostream> // <-- and uncomment these two lines
//using namespace std;// <-/

const int MAX = 10;
const int len_= 15;

typedef struct network
{  int no_node;
  char node[MAX][len_];
  int s;
  int t;
  int *c;
  int *f;
  int *cf;
  int path[MAX];
} network;

int find(char *nam, network *g, int i)
{  for(int l=0;l<i;l++)
    if(strcmp(g->node[l],nam)==0) return l;
  return -1;
}

void showMatrix(char *msg,char *node,int *mat,int n,int s,int t)
{   printf("%s\n",msg);
   for(int k=0;k<n;k++)
     printf("\t%s",node+k*len_);
   printf("\n");
  for(int k=0;k<n;k++)
  {  if(k==t) printf(">%s",node+k*len_);
     else printf(" %s",node+k*len_);
      if(k==s) printf(">");
    for(int l=0;l<n;l++)
      cout<<"\t"<<*(mat+k*n+l);
    printf("\n");
  }
}

void showFbyC(char *msg,char *node,int *f,int *c,int n,int s,int t)
{   printf("%s\n",msg);
   for(int k=0;k<n;k++)
     printf("\t%s",node+k*len_);
   printf("\n");
  for(int k=0;k<n;k++)
  {  if(k==t) printf(">%s",node+k*len_);
     else printf(" %s",node+k*len_);
      if(k==s) printf(">");
    for(int l=0;l<n;l++)
      cout<<"\t"<<*(f+k*n+l)<<"/"<<*(c+k*n+l);
    printf("\n");
  }
}

void shoNetMat(network *g)
{  static int y=0;
   if(y==0) printf("Name of nodes :\n");
  for(int i=0;y==0 && i<g->no_node;i++)
    printf("%d. %s\n",i+1,g->node[i]);
   y=1;
  showFbyC("Flow/Capacity :",g->node[0],g->f,g->c,
           g->no_node,g->s,g->t);
  showMatrix("Residual capacity :",g->node[0],
           g->cf,g->no_node,g->s,g->t);
   getchar();
}

void input_network(char *ip_file,network *g)
{  int n;
  FILE *f;
   if((f=fopen(ip_file,"r"))==NULL) {printf("file not found.\n");
     getchar();exit(0);
   }
  printf("-------------------------------------------\n");
  printf("enter number of nodes : ");fscanf(f," %d",&n);
   cout<<" "<<n;
  if(n>MAX) {
    printf("maximum node allowed is %d\n",MAX);
    printf("program terminated.");
    exit(0);
  }
  g->no_node=n;
  g->c=new int[n*n];
  g->f=new int[n*n];
  g->cf=new int[n*n];
  for(int i=0;i<n*n;i++)
  {  *(g->c+i)=*(g->f+i)=*(g->cf+i)=0;  }
  printf("\nEnter network data in format: node1  node2  capacity\n");
  printf("type \"exit\" to end\n");
  char nm1[10], nm2[10];  int c,k,l,  i=0;
  do{
    printf(">");fscanf(f," %s",nm1);cout<<" "<<nm1;
    if(strcmp(nm1,"end")==0) break;
    fscanf(f," %s %d",nm2, &c);cout<<" "<<nm2<<" "<<c<<endl;
    if(strcmp(nm1,nm2)==0) { printf("Skipping data...\n");continue; }
    if(i==0) { i=2;strcpy(g->node[0],nm1);strcpy(g->node[1],nm2);
           *(g->c+0*n+1)=c;continue;
         }
    if( (k=find(nm1,g,i))==-1 )
    {   if(i<n)
        {  strcpy(g->node[i],nm1);k=i;i++;  }
      else if(i==n)
        { printf("There can only be %d nodes..[%s]??\n",n,nm1);
          continue;
        }
    }
    if( (l=find(nm2,g,i))==-1 )
    {   if(i<n)
        {  strcpy(g->node[i],nm2);l=i;i++;  }
      else if(i==n)
        { printf("There can only be %d nodes..[%s]??\n",n,nm2);
          continue;
        }
    }
    *(g->c+k*n+l)=c;
  }while(1);
  if(i<n) printf("Enter the remaining node's name :\n");
  for(;i<n;i++)
  {  printf(">");
    fscanf(f," %s",nm1);cout<<" "<<nm1<<endl;
    if(find(nm1,g,i)==-1)
    {  strcpy(g->node[i],nm1);    }
    else { i--; printf("Same name entered twice...\n");  }
  }
   char messg[2][10]={ "source","sink" },ip[2][len_];
   int t[2];
   cout<<endl;
  for(int z=0;z<2;z++)
     do
     {  printf("Enter the %s node : ",messg[z]);
        fscanf(f," %s",ip[z]);cout<<ip[z]<<endl;
         if(z==1 && strcmp(ip[0],ip[1])==0)
         {  printf("source and sink cannot be same.\n");
           continue;
         }
        if((t[z]=find(ip[z],g,i))==-1)
          printf(" %s is not in list.\n",ip[z]);
      }while(t[z]==-1);
   g->s=t[0];g->t=t[1];
  shoNetMat(g);
}

void getResidual(network *g)
{  for(int i=0;i<g->no_node;i++)
    for(int j=0;j<g->no_node;j++)
        if(*(g->c+i*g->no_node+j))
        {*(g->cf+i*g->no_node+j)=    *(g->c+i*g->no_node+j)
                          -  *(g->f+i*g->no_node+j);
          *(g->cf+j*g->no_node+i)=   *(g->c+j*g->no_node+i)
                           -  *(g->f+j*g->no_node+i);
         }
}

bool linPath(int *path,int l,int n)
{  for(int i=0;i<n;i++)
    if( *(path+i)==l) return 1;
  return 0;
}

int getPath(int *path,int t,int *cf,int n,int i)
{  if(*(path+i)==t) return 1;
  for(int l=0;l<n;l++)
   {  if(*(cf+*(path+i)*n+l)!=0)
     {  if(!linPath(path,l,i))
        {  i++;
           *(path+i)=l;
            if((getPath(path,t,cf,n,i)))
              return 1;
            else
            {  *(path+i)=-1;
              i--;
            }
         }
      }
   }
   return 0;
}

int augmentPath(network *g)
{  int i;
   for(i=0;i<MAX;i++) g->path[i]=-1;
   g->path[0]=g->s;
   return getPath(&(g->path[0]),g->t,g->cf,g->no_node,0);
}

void showPath(int *path,char *node)
{  int i=1;
  printf("\nPath:\n%s",node+*(path)*len_);
    while(*(path+i)!=-1)
   {  printf("->%s",node+*(path+i)*len_);
      i++;
  };
  printf("\n");
}

int minPathCapacity(int *path,int *cf,int n)
{  int k=*(path),l=*(path+1),i=2,c=*(cf+k*n+l);
  while(*(path+i)!=-1)
   {  k=l;
     l=*(path+i);
      c=(c>*(cf+k*n+l))?*(cf+k*n+l):c;
     i++;
   }
   return c;
}

void applyFFA(network *g)
{  int min,i,j,k;
  getResidual(g);
  while(augmentPath(g))
   {  showPath(&(g->path[0]),g->node[0]);
      min=minPathCapacity(&(g->path[0]),g->cf,g->no_node);
      cout<<"min="<<min<<endl;

      i=g->path[0];j=g->path[1];k=2;
      *(g->f+i*g->no_node+j)= *(g->f+i*g->no_node+j) +  min;
      *(g->f+j*g->no_node+i)= - *(g->f+i*g->no_node+j);
      while(g->path[k]!=-1)
      {  i=j; j=g->path[k];
        *(g->f+i*g->no_node+j)= *(g->f+i*g->no_node+j) +  min;
         *(g->f+j*g->no_node+i)= - *(g->f+i*g->no_node+j);
         k++;
      }
      getResidual(g);
      shoNetMat(g);
   }
   cout<<"\n\n\n-------------------DONE-------------------\n\n";
   cout<<"The Result is in the residual capacity matrix\n\n";
   shoNetMat(g);getchar();
}

main()
{  network G;
  char fname[20];
  cout<<"\nEnter input file name : ";
   cin>>fname;
  input_network(fname,&G);
  applyFFA(&G);
  return 0;
}



Note: The number at the beginning denotes the total number of vertices in the graph. The last two symbols denotes the source and the sink respectively.