#TJHSST ~ Maximizing Flow in a Network

network.c

/* Maximizing Flow in a Network */
#include <stdio.h>
#include <ctype.h>
#include <conio.h>
#include <stdlib.h>

/* These are small for no real reason. */
#define MAXVERTEXCNT 6
#define MAXFLOW 15
#define BIGMAXFLOW (MAXFLOW*MAXFLOW)

/* To increase clarity. */
#define TRUE 1
#define FALSE 0

#define NOBODY 0

struct edge_type {
  int capacity,flow;
};

struct vertex_type {
  int labeled,examined,label_flow,label_from,label;
};

struct network_type {
  int vertexcnt;
  struct vertex_type vertices[MAXVERTEXCNT];
  struct edge_type edges[MAXVERTEXCNT][MAXVERTEXCNT];
};

char nil;

int main()
{
  struct network_type network;
  int quit=0,choice;

  network.vertexcnt=(-1);
  while(!quit)  {
    clrscr();
    puts("");
    puts("#     #");
    puts("##    #  ######   #####  #    #   ####   #####   #    #");
    puts("# #   #  #          #    #    #  #    #  #    #  #   #");
    puts("#  #  #  #####      #    #    #  #    #  #    #  ####");
    puts("#   # #  #          #    # ## #  #    #  #####   #  #");
    puts("#    ##  #          #    ##  ##  #    #  #   #   #   #");
    puts("#     #  ######     #    #    #   ####   #    #  #    #");
    puts("");
    puts("+----------------------------------+");
    puts("|                                  |");
    puts("|  Network Stuff                   |");
    puts("|                                  |");
    puts("|  1. Edit Network                 |");
    puts("|  2. Compute Maximum Flow         |");
    puts("|  3. Display Network              |");
    puts("|  4. Finis                        |");
    puts("|                                  |");
    puts("+----------------------------------+");
    printf("Enter your choice : ");
    scanf("%d",&choice);
    switch(choice)  {
      case 1 :
        edit_network(&network);
        break;
      case 2 :
	maximize_flow(&network);
        break;
      case 3 :
	view_matrix(&network);
	pause();
        break;
      case 4 :
        quit=1;
        break;
      default :
        printf("\aThat is not one of your choices.\n");
        break;
    }
  }
}

int edit_network(network)
struct network_type *network;
{
  int quit=0,cnt,choice,newlabel,newcapacity,newflow,
      originator,terminator;

  if(network->vertexcnt==(-1))  {
    puts("Initialising Network");
    puts("Initialising Vertex Set");
    for(cnt=0;cnt<MAXVERTEXCNT;cnt++)  {
      network->vertices[cnt].label=cnt;
      network->vertices[cnt].labeled=FALSE;
      network->vertices[cnt].examined=FALSE;
      network->vertices[cnt].label_from=NOBODY;
      network->vertices[cnt].label_flow=(-1);
    }
    puts("Initialising Edge Set");
    for(terminator=0;terminator<MAXVERTEXCNT;terminator++)  {
      for(originator=0;originator<MAXVERTEXCNT;originator++)  {
	network->edges[terminator][originator].capacity=(-1);
	network->edges[terminator][originator].flow=(-1);
      }
    }
    network->vertexcnt=MAXVERTEXCNT;
  }
  while(!quit)  {
    clrscr();
    puts("");
    puts("#######");
    puts("#        #####      #     #####");
    puts("#        #    #     #       #");
    puts("#####    #    #     #       #");
    puts("#        #    #     #       #");
    puts("#        #    #     #       #");
    puts("#######  #####      #       #");
    puts("");
    puts("+----------------------------------+");
    puts("|                                  |");
    puts("|  Network Editting Menu           |");
    puts("|                                  |");
    puts("|  1. View Adjacency Matrix        |");
    puts("|  2. Add Edge                     |");
    puts("|  3. Leave Editting Menu          |");
    puts("|                                  |");
    puts("+----------------------------------+");
    printf("Enter your choice : ");
    scanf("%d",&choice);
    switch(choice)  {
      case 1 :
	view_matrix(network);
	pause();
	break;
      case 2 :
	view_matrix(network);
	originator=terminator=(-1);
	do  {
	  if((terminator==originator)&&(terminator!=(-1)))
	    puts("\aThis is not a loop graph network.");
	  do  {
	    printf("Enter vertex to originate edge [0..%d] : ",MAXVERTEXCNT-1);
	    scanf("%d",&originator);
	    if(originator<0||originator>=MAXVERTEXCNT)  {
	      puts("\aThat is not one of your choices.");
	      originator=(-1);
	    }
	  } while(originator==(-1));
	  do  {
	    printf("Enter vertex to terminate edge [0..%d] : ",MAXVERTEXCNT-1);
	    scanf("%d",&terminator);
	    if(terminator<0||terminator>=MAXVERTEXCNT)  {
	      puts("\aThat is not one of your choices.");
	      terminator=(-1);
	    }
	  } while(terminator==(-1));
	} while(terminator==originator);
        if(network->edges[terminator][originator].flow==(-1))
	  puts("This is a new edge.");
	newcapacity=(-2);
	newflow=(-1);
	do  {
	  if((newflow>newcapacity)&&(newflow!=(-1)))
	    puts("\aThe flow cannot be greater than the capacity.");
	  do  {
	    printf("Enter capacity of edge [0..%d] : ",MAXFLOW-1);
	    scanf("%d",&newcapacity);
	    if(newcapacity<0||newcapacity>=MAXFLOW)  {
	      puts("\aThat is not one of your choices.");
	      newcapacity=(-2);
	    }
	  } while(newcapacity==(-2));
	  do  {
	    printf("Enter flow of edge [0..%d] : ",MAXFLOW-1);
	    scanf("%d",&newflow);
	    if(newflow<0||newflow>=MAXFLOW)  {
	      puts("\aThat is not one of your choices.");
	      newflow=(-1);
	    }
	  } while(newflow==(-1));
	} while(newflow>newcapacity);
        network->edges[terminator][originator].capacity=newcapacity;
	network->edges[terminator][originator].flow=newflow;
        break;
      case 3 :
        quit=1;
        break;
      default :
        printf("\aThat is not one of your choices.\n");
        break;
    }
  }
  return 0;
}

int maximize_flow(network)
struct network_type *network;
{
  int originator,terminator,maxflow=0,sinklabeled,vertex,okay;

/* Step 1 : Initialize all flows to zero. */
  for(terminator=0;terminator<MAXVERTEXCNT;terminator++)
    for(originator=0;originator<MAXVERTEXCNT;originator++)
      if(network->edges[terminator][originator].capacity!=(-1))
	network->edges[terminator][originator].flow=0;
  do {
/* Step 2 : Label vertex a as (,infinity). */
    network->vertices[0].labeled=TRUE;
    network->vertices[0].label_from=NOBODY;
    network->vertices[0].label_flow=BIGMAXFLOW;
    sinklabeled=FALSE;
/* Step 3 : If sink is labeled, goto to Step 6. */
    while(!sinklabeled&&!maxflow)  {
/* Step 4 : Choose the next un-examined labeled vertex. If none
	    then stop, (flow is maximal), otherwise set v=v sub i. */
      originator=0;
      okay=0;
      while(originator<MAXVERTEXCNT&&!okay)  {
	if(network->vertices[originator].labeled==TRUE)  {
	  if(network->vertices[originator].examined==FALSE)
	    okay=1;
	  else
	    originator++;
	}
	else
	  originator++;
      }
      if(originator==MAXVERTEXCNT)  {
/* The flow is maximal if sink has been examined. */
	if(network->vertices[originator].examined==TRUE)  {
	  maxflow=1;
	  continue;
	}
	sinklabeled=1;
	continue;
      }
      vertex=originator;
      network->vertices[vertex].examined=TRUE;
/* Step 5 : Label adjacent vertices. */
      for(terminator=vertex+1;terminator<MAXVERTEXCNT;terminator++)  {
	if(network->edges[terminator][vertex].flow!=(-1))
	  if(network->edges[terminator][vertex].flow<
	     network->edges[terminator][vertex].capacity)  {
	    network->vertices[terminator].labeled=TRUE;
	    network->vertices[terminator].label_from=
	      network->vertices[vertex].label;
	    network->vertices[terminator].label_flow=
	      min(network->vertices[vertex].label_flow,
		  (network->edges[terminator][vertex].capacity-
		   network->edges[terminator][vertex].flow));
	  }
	if(network->edges[vertex][terminator].flow!=(-1))
	  if(network->edges[vertex][terminator].flow>0)  {
	    network->vertices[terminator].labeled=TRUE;
	    network->vertices[terminator].label_from=
	      network->vertices[vertex].label;
	    network->vertices[terminator].label_flow=
	      min(network->vertices[vertex].label_flow,
		  network->edges[vertex][terminator].flow);
	  }
      }
    }
/* Step 6 : Revise network's flow. */
    while(vertex!=0&&!maxflow)  {
      if(vertex>network->vertices[vertex].label_from)
	network->edges[vertex][network->vertices[vertex].label_from].flow+=
	  network->vertices[vertex].label_flow;
      else
	network->edges[vertex][network->vertices[vertex].label_from].flow-=
	  network->vertices[vertex].label_flow;
      vertex=network->vertices[vertex].label_from;
    }
    for(vertex=0;vertex<MAXVERTEXCNT;vertex++)  {
      network->vertices[vertex].labeled=FALSE;
      network->vertices[vertex].examined=FALSE;
      network->vertices[vertex].label_from=NOBODY;
    }
  } while(!maxflow);
}

int view_matrix(network)
struct network_type *network;
{
  int terminator,originator;

  clrscr();
  puts("Adjacency Matrix");
  printf("     ");
  for(terminator=0;terminator<MAXVERTEXCNT;terminator++)
    printf("  %2d    ",terminator);
  puts("");
  for(originator=0;originator<MAXVERTEXCNT;originator++)  {
    printf("%3d  ",originator);
    for(terminator=0;terminator<MAXVERTEXCNT;terminator++)  {
      if(terminator==originator)
	printf("( X,X ) ");
      else  {
	if(network->edges[terminator][originator].capacity>(-1))
	  printf("(%2d,%-2d) ",network->edges[terminator][originator].capacity,
			      network->edges[terminator][originator].flow);
	else
	  printf("        ");
      }
    }
    puts("");
  }
}

int pause(void)
{
  char enter;

  puts("Press Enter to continue...");
  scanf("%c%c",&enter,&enter);
}

Maximizing flow in a network code found on an old 5.25 floppy disk from when I was a nerd at Thomas Jefferson High School for Science and Technology between 1988 and 1992.

http://en.wikipedia.org/wiki/Maximum_flow_problem

Anyone can do whatever they'd like to with this program--if anything.

I remain a single-source and single-sink nerd.