/*  An implementation of A Generic Maximum-Flow Algorithm.
 *  Implementation by: Jim Williams, Lars Starbuck  November 1992.
 *  Algorithm Improvements & Simulator: Jim Williams April 1993.
 *
 *     Algorithm from "A New Approach to the Maximum-Flow Problem."
 *     by Andrew V. Goldberg and Robert E. Tarjan.
 *     Journal of the Association for Computing Machinery, Vol. 35, No. 4,
 *     October 1988, pp. 921-940.
 */

/* Table of Algorithm symbols versus implementation symbols.
 *  algorithm       implementation      meaning
 *  V               -Not Used-          vertex set
 *  E               -Not Used-          edge set
 *  v               v                   specific vertex
 *  w               w                   specific vertex
 *  f               flow                preflow
 *  e               excess              flow excess
 *  r               residual            residual capacity of vertex pair
 *  c               capacity            capacity for each edge
 *  n               Vnum                number of vertices
 *  m               -Not Used-          number of edges
 *  s               source              source vertex
 *  t               sink                sink vertex
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/* To port to a Unix or DOS system,
 *    1) uncomment the correct include library and
 *    2) uncomment the correct 2 timing routines below.
 *    3) compile.
 */
/*#include <sys/time.h>*/  /* not portable - for Unix timing */
/*#include <dos.h>*/  /* not portable - for DOS timing */


/*
#define DEBUG
*/

/* if GRAPH is #defined then compile with
 * C:\> bcc maxflow.c displayl.c graphics.lib
 * for DOS graphic representation of algorithm.
 */
#define GRAPH

#ifdef GRAPH
#include "displayl.h" /* not portable - DOS graphics */
#endif


#define TRUE   1
#define FALSE  0

#define MAXNODES       50  /* maximum number of nodes in network */
#define MAXNAMELENGTH  10  /* maximum length of node name */

#define INFINITY   999999  /* larger than distance between nodes in net */

#define FORWARD   2      /* forward pass through network with maxflow */
#define BACKWARD  3      /* backward pass after max channels is determined */

#define DIAGNOSIS_TIME  90   /* network fault diagnosis time in msec. */
#define CONNECTION_TIME 100  /* network connection reestablishment time in msec. */

/* debugging output goes to stdout */
FILE *fp = stdout;

typedef int boolean;

typedef long array2d[ MAXNODES+1 ][ MAXNODES+1 ];  /* waste the 0th location */

typedef long array1d[ MAXNODES+1 ];

typedef struct graphType {
	array2d capacity;    /* matrix contains capacities for all edges */
	array2d flow;        /* computed flow matrix */
	array1d distance;    /* initially, number of links between node and sink */
	array1d excess;
	int     Vnum;        /* number of nodes (vertices) in network */
	int     source;      /* source node in network */
	int     sink;        /* sink node in network */
	char    nodeName[ MAXNODES+1 ][ MAXNAMELENGTH ];  /* node character names */
	long    work;        /* working bandwidth cut */

	array1d srcdistance;        /* distance from source for each node */
	int currentEdgeIndex;       /* index to edgeList of current edge */
	int edgeListNum;            /* number of edges connected to node */
	int edgeConnectNode;        /* node edges are connected to */
	int edgeList[ MAXNODES+1 ]; /* list of edges connected to node sorted by distance. */

	array1d snkdistance;      /* distance to sink node from each node */

	int restoration_paths;    /* number of paths to be restored */
	array2d work_matrix;      /* matrix of working paths */
} graphType;

typedef graphType * graphTypePtr;


/* queue data structure node */
typedef struct queueType {
	int queue[ MAXNODES ];
	int begin;
	int end;
	int max_length;
	int queue_size;
} queueType;


/* Function Prototypes */
void GetTime( int *hr, int *min, int *sec, int *hsec);
void GetDate( int *yr, int *mon, int *day, int *dow);

int mtqueue( queueType * queue );
void initqueue( queueType  * queue );
int dqueue( queueType * queue );
int nqueue( int el, queueType * queue );

void dump_info( graphTypePtr net );
void temp_load( char *s, graphTypePtr net );
void print_capacity( graphTypePtr net );

long Max( long one, long two );
long Min( long one, long two );

int find_path( graphTypePtr net, int maxbandwidth, int *totalspares );
void show_paths( graphTypePtr net );
void init_back_trace( graphTypePtr net );
void back_trace( graphTypePtr net, int v, int w );

void load_graph( char *s, graphTypePtr net );
int find_number( char *name, graphTypePtr net );
void init_net( graphTypePtr net );

void bfs( int init, array1d distance, graphTypePtr net );
void calc_distance( graphTypePtr net );

long residual( int v, int w, graphTypePtr net );
boolean active( int v, graphTypePtr net );

int find_first_edge( int v, graphTypePtr net );
int find_next_edge( int v, graphTypePtr net );
int relabel_find_next_edge( int v, int current, graphTypePtr net );

boolean push( int v, int w, graphTypePtr net );
boolean relabel( int v, graphTypePtr net );
void max_flow( graphTypePtr net, int direction );

#ifndef GRAPH

/*--------- Not portable Timing routines - Unix -------------------------*/

/*
void GetTime( int *hr, int *min, int *sec, int *csec)
{
		  struct timeval t;
		  struct tm *local;

		  gettimeofday(&t, 0);
		  local = localtime(&t.tv_sec);
		  *hr = local->tm_hour;
		  *min = local->tm_min;
		  *sec = local->tm_sec;
		  *csec = t.tv_usec/10000L;
}
*/
/*
void GetDate( int *yr, int *mon, int *day, int *dow)
{
		  struct timeval t;
		  struct tm *local;

		  gettimeofday(&t, 0);
		  local = localtime(&t.tv_sec);
		  *yr = local->tm_year;
		  *mon = local->tm_mon;
		  *day = local->tm_mday;
		  *dow = local->tm_wday;

}
*/
/*--------- End Not portable Timing routines - Unix --------------------*/

/*--------- Not portable Timing routines - DOS -------------------------*/

void GetTime( int *hr, int *min, int *sec, int *hsec)
{

		  struct time t;

		  gettime(&t);
		  *hr = t.ti_hour;
		  *min = t.ti_min;
		  *sec = t.ti_sec;
		  *hsec = t.ti_hund;

}
/*
void GetDate( int *yr, int *mon, int *day, int *dow)
{
	  struct date d;

	  getdate(&d);

	  *yr = d.da_year;
	  *mon = d.da_mon;
	  *day = d.da_day;
	  *dow = 0;

}
*/
/*--------- End Not portable Timing routines - DOS -------------------------*/

#endif

/*--------- QUEUE -------------------------------------------------------*/

int mtqueue( queueType * queue )
{
	return !queue->queue_size;
}


void initqueue( queueType  * queue )
{
	int i;

	queue->begin = 0;
	queue->end = 0;
	queue->queue_size = 0;
	queue->max_length = sizeof( queue->queue ) / sizeof( int );
	for (i = 0 ; i < queue->max_length ; i++ )
		queue->queue[i] = 0;
}

int dqueue( queueType * queue )
{
	int element;

	if ( mtqueue( queue ) )
		return -1;

	element = queue->queue[ queue->begin ];
	queue->queue[ queue->begin++ ] = 0;

	if ( queue->begin >= queue->max_length )
		queue->begin = 0;

	queue->queue_size--;

	return element;
}

int nqueue( int el, queueType * queue )
{
	if ( queue->queue_size >= queue->max_length )
		return FALSE;

	queue->queue[ queue->end++ ] = el;

	if ( queue->end >= queue->max_length )
		queue->end = 0;

	queue->queue_size++;

	return TRUE;

} /* nqueue */

/*--------- End QUEUE ---------------------------------------------------*/

/*--------- debug routines ----------------------------------------------*/
void dump_info( graphTypePtr net )
{
	int i, j;

	fprintf( fp, "\n\nFlow:\n     ");
	for ( i = 1; i <= net->Vnum; i++ )
		fprintf( fp, "%c%3s ",
					((i==net->source)||(i==net->sink))? '*': ' ', net->nodeName[i] );

	for ( i = 1; i <= net->Vnum; i++ )
	{
		fprintf( fp, "\n%c%3s ",
					((i==net->source)||(i==net->sink))? '*': ' ', net->nodeName[i] );

		for ( j = 1; j <= net->Vnum; j++ )
		{
			fprintf( fp, "%4ld ", net->flow[i][j] );
		}
	}

	fprintf( fp, "\n\nDistance:       Excess:\n");
	for ( i = 1; i <= net->Vnum; i++ )
	{
		fprintf( fp, "%c%3s %3ld        %c%3s %3ld\n",
					((i==net->source)||(i==net->sink))? '*': ' ',
					net->nodeName[i], net->distance[i],
					((i==net->source)||(i==net->sink))? '*': ' ',
					net->nodeName[i], net->excess[i] );
	}

	fprintf( fp, "\nResidual:\n     ");
	for ( i = 1; i <= net->Vnum; i++ )
		fprintf( fp, "%c%3s ",
					((i==net->source)||(i==net->sink))? '*': ' ', net->nodeName[i] );

	for ( i = 1; i <= net->Vnum; i++ )
	{
		fprintf( fp, "\n%c%3s ",
					((i==net->source)||(i==net->sink))? '*': ' ', net->nodeName[i] );

		for ( j = 1; j <= net->Vnum; j++ )
		{
			fprintf( fp, "%4ld ", residual( i, j, net ) );
		}
	}

} /* dump_info */

void print_capacity( graphTypePtr net )
{
	int i, j;

	fprintf( fp, "\nCapacity:\n");
	for ( i = 1; i <= net->Vnum; i++ )
		fprintf( fp, "%c%3s ",
					((i==net->source)||(i==net->sink))? '*': ' ', net->nodeName[i] );

	for ( i = 1; i <= net->Vnum; i++ )
	{
		fprintf( fp, "\n%c%3s ",
					((i==net->source)||(i==net->sink))? '*': ' ', net->nodeName[i] );

		for ( j = 1; j <= net->Vnum; j++ )
		{
			fprintf( fp, "%4ld ", net->capacity[i][j] );
		}
	}

} /* print_capacity */


/*--------- end debug routines ------------------------------------------*/

/*--------- Utility Functions -------------------------------------------*/

/* returns the maximum of the two long integers */
long Max( long one, long two )
{
	if ( one > two )
		return one;
	else
		return two;
} /* Max */

/* returns the minimum of the two long integers */
long Min( long one, long two )
{
	if ( one < two )
		return one;
	else
		return two;

} /* Min */

/*--------- End Utility Functions -----------------------------------------*/

/*--------- Path Finding functions ----------------------------------------*/


int find_path( graphTypePtr net, int maxbandwidth, int *totalspares )
{
	int i, j, s;
	array1d path;       /* the path through the network */
	int spares;         /* number of spares in path */
	int bandwidth;      /* current capacity of path */
	int larger_flow, shortest_distance, best_node;


	/* initialization */
	for ( i = 1; i <= net->Vnum; i++ )
		path[i] = 0;

	s = net->source;
	bandwidth = maxbandwidth;

	/* while path not complete from source to sink */
	do{
		/* pick the next node to traverse to:
		 *    1) select by shortest distance than
		 *    2) select by larger flow
		 */
		larger_flow = 0;
		shortest_distance = net->Vnum;
		for ( i = 1; i <= net->Vnum; i++ )
		{
			 if ( net->flow[s][i] > 0 )
			 {
				 if ( net->snkdistance[i] < shortest_distance )
				 {
					 best_node = i;
					 shortest_distance = net->snkdistance[i];
					 larger_flow = net->flow[s][i];
				 }
				 else if ( net->snkdistance[i] == shortest_distance )
				 {
					 if ( net->flow[s][i] > larger_flow )
					 {
						 best_node = i;
						 larger_flow = net->flow[s][i];
						 shortest_distance = net->snkdistance[i];
					 }
				 }
			 }
		} /* for */
		i = best_node;


		if ( path[s] != 0 )
		{
/* remove cycle */
			i = s;
			j = path[s];
			do{
				net->flow[i][j] -= bandwidth;
				i = j;
				j = path[j];
			}while( i != s );

/* start over */
			for ( i = 1; i <= net->Vnum; i++ )
				path[i] = 0;

			i = net->source;
			bandwidth = maxbandwidth;

		}
		else
		{
			path[s] = i;
			bandwidth = Min( net->flow[s][i], bandwidth );
		}
		s = i;

	} while ( i != net->sink );

/* print path, remove bandwidth from graph */
	spares = 0;
	s = net->source;
	do{

#ifndef GRAPH
		printf("%s->", net->nodeName[s]);
#endif

		net->flow[s][path[s]] -= bandwidth;

#ifdef GRAPH
		display_connectNodes( loc, s, path[s] );
#endif

		s = path[s];
		spares++;

	} while ( s != net->sink );

#ifndef GRAPH
	printf("%s  (%d channels) (%d spares)\n",
			 net->nodeName[ net->sink ], bandwidth, spares*bandwidth );
#endif

	*totalspares += spares*bandwidth;

	return bandwidth;

} /* find_path */


void show_paths( graphTypePtr net )
{
	int remaining_cap;
	int totalspares = 0;
	int restored_channels;

	/* restore number of paths broken */
	if ( net->excess[ net->sink ] > net->restoration_paths )
		remaining_cap = net->restoration_paths;
	else  /* else no paths broken, show maximum restoration */
		remaining_cap = net->excess[ net->sink ];

	restored_channels = remaining_cap;

	while( remaining_cap > 0 )
	{
		remaining_cap -= find_path( net, remaining_cap, &totalspares );
	}

#ifndef GRAPH
	printf("\nRestored Channels = %3d    ", restored_channels );
	printf("Total Spares Used: %d\n\n", totalspares );
#endif

} /* show_paths */

/*--------- End Path Finding functions ------------------------------------*/


/*--------- Load Network Functions ----------------------------------------*/

/* Assumptions:
	The nodes in network are numbered consecutively from 1 to Vnum.
	We are given the remaining capacities for all edges in network.
*/

void load_graph( char *s, graphTypePtr net )
{
	FILE * fp;
	int link_count;
	int i, j;
	int work, spare, dest, active;
	int node;
	char string[80];
	float junk;
	int junk1;

	if ( (fp = fopen( s, "r" )) == NULL )
	{
		printf("File: '%s' not found.\n", s );
		exit(1);
	}

	/* read the number of nodes (vertices) in network */
	fscanf( fp, "%d%*[^\n]", &(net->Vnum) );   /* number of vertices */

	for ( i = 1; i <= net->Vnum; i++ )
	{
		/* read necessary information from file. */
		fscanf( fp, "%s%d%f%d%f%f%d%*[^\n]",
				  string, &link_count, &junk, &junk1, &junk, &junk, &node );

		/* save character node name */
		sprintf( net->nodeName[node], "%s", string );

		/* save spare capacity on each edge */
		for ( j = 1; j <= link_count; j++ )
		{
			fscanf( fp, "%d%d%d%d", &dest, &active, &work, &spare );
			net->capacity[node][dest] = spare;
			net->capacity[dest][node] = spare;

			net->work_matrix[node][dest] = work;
			net->work_matrix[dest][node] = work;
		}
	}

	fclose( fp );

} /* load_graph */


/* finds the internal number of a node based on it's name */
int find_number( char *name, graphTypePtr net )
{
	int i;

	for (i = 1; i <= net->Vnum; i++)
	{
		if ( strcmp( net->nodeName[i], name ) == 0 )
			return i;
	}
	return FALSE;
} /* find_number */


/* initializes net structure */
void init_net( graphTypePtr net )
{
	int i, j;

	for ( i = 0; i < MAXNODES + 1; i++ )
	{
		for ( j = i; j < MAXNODES + 1; j++ )
		{
			net->capacity[i][j] = 0;
			net->capacity[j][i] = 0;
			net->flow[i][j] = 0;
			net->flow[j][i] = 0;
			net->work_matrix[i][j] = 0;
			net->work_matrix[j][i] = 0;
		}
	}

	for ( i = 0; i < MAXNODES + 1; i++ )
	{
		 net->distance[i] = 0;
		 net->excess[i] = 0;
	}

} /* init_net */

/*--------- End Load Network Functions ------------------------------------*/


/*--------- Distance Calculating Functions --------------------------------*/

/* breadth first search to determine distance each node is from sink or source. */
void bfs( int init, array1d distance, graphTypePtr net )
{
	short closed[MAXNODES+1];
	short seen_nodes;
	queueType children;
	int depth;
	int node;
	int i;

	for ( i = 0; i <= net->Vnum; i++ )
		closed[ i ] = FALSE;

	initqueue( &children );
	depth = 0;
	seen_nodes = 0;

	node = init;
	closed[ node ] = TRUE;
	distance[ node ] = depth;

	do {

		seen_nodes++;
		for ( i = 1; i <= net->Vnum; i++ )
		{
			if ( (net->capacity[node][i] != 0) && ( !closed[i] ) )
			{
				nqueue( i, &children );
				closed[ i ] = TRUE;
				distance[ i ] = distance[ node ] + 1;
			}
		}

		if ( !mtqueue( &children ) )
			node = dqueue( &children );


	}while (seen_nodes < net->Vnum );

} /* bfs */



void calc_distance( graphTypePtr net )
{
	int i;

	for ( i = 0; i <= net->Vnum; i++ )
	{
		net->distance[i] = 0;
		net->srcdistance[ i ] = 0;
		net->snkdistance[ i ] = 0;
	}

	bfs( net->sink, net->snkdistance, net );

	bfs( net->source, net->srcdistance, net );


	for ( i = 0; i <= net->Vnum; i++ )
	{
		net->distance[i] = Min( net->snkdistance[i],
									  net->srcdistance[i] + net->Vnum );
	}

	/* distance from source to sink always starts as the farthest in the graph */
	net->distance[net->source] = net->Vnum;

#ifdef GRAPH
	for ( i = 1; i <= net->Vnum; i++ )
	{
		display_relabel( loc, i, net->distance[i] );
	}
#endif

} /* calc_distance */

/*--------- End Distance Calculating Functions ----------------------------*/

/*--------- Max Flow Algorithm Specific Functions -------------------------*/

long residual( int v, int w, graphTypePtr net )
{

	return ( net->capacity[v][w] - net->flow[v][w] );

} /* residual */


boolean active( int v, graphTypePtr net )
{
/* if v is a vertex not equal to source or sink
 * and distance of v less than infinity
 * and excess of v is greater than 0
 * then v is active.
 */

	if ( (v != net->source) &&
		  (v != net->sink) &&
		  (net->distance[v] < INFINITY) &&
		  (net->excess[v] > 0) )
		return TRUE;
	else
		return FALSE;

} /* active */


/* initialize edgeList for node v, and return first edge on that list */
int find_first_edge( int v, graphTypePtr net )
{
	int i, edge_i;
	int temp, j;

	net->edgeConnectNode = v;
	edge_i = 0;
	for ( i = 1; i <= net->Vnum; i++ )
	{
		if ( net->capacity[v][i] > 0 )
		{
			net->edgeList[edge_i++] = i;
		}
	}
	net->edgeListNum = edge_i;

	/* insert sort on distance from source */
	for ( i = 1; i < net->edgeListNum; i++ )
	{
		temp = net->edgeList[i];
		j = i - 1;
		while( (j > -1) &&
				 (net->srcdistance[temp] < net->srcdistance[net->edgeList[j]]) )
		{
			net->edgeList[j+1] = net->edgeList[j];
			j = j - 1;
		}
		net->edgeList[j+1] = temp;
	} /* for */
	net->currentEdgeIndex = 0;

	return net->edgeList[ net->currentEdgeIndex++];

} /* find_first_edge */

/* return the next edge on the edgeList */
int find_next_edge( int v, graphTypePtr net )
{
	if ( v != net->edgeConnectNode )
	{
		printf("\n\nMajor ERROR Dude in find_next_edge\n\n");
	}
	if ( net->currentEdgeIndex < net->edgeListNum )
	{
		return net->edgeList[ net->currentEdgeIndex++ ];
	}
	return -1;

} /* find_next_edge */

/* get the next edge connected to node v, starting with current edge */
int relabel_find_next_edge( int v, int current, graphTypePtr net )
{
	int i;

	for ( i = current; i <= net->Vnum; i++ )
	{
		if ( net->capacity[v][i] > 0 )
		{
			return i;
		}
	}
	return -1;

} /* relabel_find_next_edge */

/* push flow from v to w */
boolean push( int v, int w, graphTypePtr net )
{
	long delta;

	if ( active( v, net ) &&
		  (residual( v, w, net ) > 0) &&
		  (net->distance[v] == net->distance[w] + 1) )
	{
		delta = Min( net->excess[v], residual( v, w, net ) );
		net->flow[v][w] += delta;
		net->flow[w][v] -= delta;
		net->excess[v] -= delta;
		net->excess[w] += delta;

#ifdef DEBUG
		printf("\npushed %ld from: %s to: %s\n",
				 delta, net->nodeName[v], net->nodeName[w] );
#endif

#ifdef GRAPH
		/* graphically show flow being pushed on display */
		display_pushIJ( loc, v, w, delta );
#endif

		return TRUE;
	}
	else
		return FALSE;

} /* push */



/* change distance of current node v */
boolean relabel( int v, graphTypePtr net )
{
	long minimum = INFINITY;
	int w;

#ifdef DEBUG
	printf("\nrelabel: %s\n", net->nodeName[v] );
#endif

	if ( active( v, net ) )
	{
		w = 0;
		do{
			w = relabel_find_next_edge( v, w+1, net );
			if ( (w > 0) &&
				  ((net->distance[w] +1) < minimum ) &&
				  (w != net->sink) &&
				  (residual( v, w, net ) > 0) &&
				  (net->distance[v] <= net->distance[w]) )
			{
				minimum = net->distance[w] + 1;
			}

		}while( w > 0 );

		net->distance[v] = minimum;

#ifdef GRAPH
		/* graphical display */
		display_relabel( loc, v, minimum );
#endif

		return TRUE;
	}
	else
		return FALSE;

} /* relabel */

/* insert the initial edges into queue sorted ascending by distance */
void initial_queueing( queueType *Q, graphTypePtr net )
{
	int i, j, k, num_edges, insert_edge, remaining_edges, list_index;
	array1d node_list;
	long minimum;

	num_edges = 0;
	for ( i = 1; i <= net->Vnum; i++ )
	{
		if ( active( i, net ) )
		{
			node_list[num_edges++] = i;

#ifdef GRAPH
			/* graphically display initial flow push */
			display_pushIJ( loc, net->source, i, net->capacity[net->source][i] );
#endif

		}
	}

	remaining_edges = num_edges;
	for ( i = 0; i < num_edges; i++ )
	{
		minimum = INFINITY;
		for ( k = 0; k < remaining_edges; k++ )
		{
			if ( net->distance[node_list[k]] < minimum )
			{
				insert_edge = node_list[k];
				list_index = k;
				minimum = net->distance[node_list[k]];
			}
		}  /* for k */

		nqueue( insert_edge, Q );

		for ( j = list_index; j < remaining_edges; j++ )
			node_list[j] = node_list[j+1];

		 remaining_edges--;
	} /* for i */

} /* initial_queueing */


void max_flow( graphTypePtr net, int direction )
{
	int v, w;       /* nodes (vertices) */
	queueType Q;
	int current_edge;
	int distance_v;
	boolean active_w;

	/* backward ext. */
	array2d temp_array;
	int temp_node;

	/* if maxflow running backwards than switch source and sink and save
	 * flow into former sink.
	 */
	if ( direction == BACKWARD )
	{
		/* swap source & sink nodes */
		temp_node = net->source;
		net->source = net->sink;
		net->sink = temp_node;

		for ( v = 1; v <= net->Vnum; v++ )
		{
			temp_array[net->source][v] = net->flow[v][net->source];
			temp_array[v][net->source] = net->flow[net->source][v];
		}

	} /* if BACKWARD */

/* initialization */
/* initialize preflow */
	for ( v = 1; v <= net->Vnum; v++ )
	{
		for ( w = v; w <= net->Vnum; w++ )
		{
			net->flow[v][w] = 0;
			net->flow[w][v] = 0;
		}
	}

	/* initialize flow from source */
	if ( direction == FORWARD )
	{
		for ( v = 1; v <= net->Vnum; v++ )
		{
			net->flow[net->source][v] = net->capacity[net->source][v];
			net->flow[v][net->source] = -net->capacity[net->source][v];
		}
	}
	else  /* if ( direction == BACKWARD ) */
	{
		for ( v = 1; v <= net->Vnum; v++ )
		{
			net->flow[v][net->source] = temp_array[v][net->source];
			net->flow[net->source][v] = temp_array[net->source][v];
		}
	} /* if direction */


/* initialize labels and excesses */
	for ( v = 1; v <= net->Vnum; v++ )
	{
		net->excess[v] = net->flow[net->source][v];
	}

	calc_distance( net );

	initqueue( &Q );

	initial_queueing( &Q, net );

	while( !mtqueue( &Q ) )
	{
		v = dqueue( &Q );

		distance_v = net->distance[ v ];

/* get initial edge {v,w} */
		current_edge = find_first_edge( v, net );

		do {

#ifdef DEBUG
			dump_info( net );
#endif
			w = current_edge;

			active_w = active( w, net );

			if ( push( v, w, net ) )
			{
				/* everything done inside push */
			}
			else
			{
				/* get next edge */
				current_edge = find_next_edge( v, net );
				if ( current_edge != -1 )
				{
					/* nothing */
				}
				else
				{
					current_edge = find_first_edge( v, net );
					relabel( v, net );
				}
			}

			if ( !active_w && ( active( w, net ) ) )
				nqueue( w, &Q );

		} while ( !((net->excess[v] == 0) || (net->distance[v] > distance_v)) );

		if ( active( v, net ) )
			nqueue( v, &Q );

	} /* while */

} /* max_flow */


/*-------------------------------------------------------------------------*/

int main( int argc, char **argv)
{
#ifndef GRAPH
	int s_hr, s_min, s_sec, s_hsec, e_hr, e_min, e_sec, e_hsec;
	long e_total, s_total, path_finding_time;
#endif

	graphTypePtr network;

	if (argc != 4)   /* filename plus 3 parameters */
	{
		printf(" Maxflow network restoration algorithm implementation\n");
		printf("      by Jim Williams & Lars Starbuck\n");
		printf(" Usage: maxflow <netfilename> <source> <sink>\n");
		exit(1);
	}

	network = (graphTypePtr) malloc( sizeof(graphType) );

	init_net( network );


#ifndef GRAPH
	GetTime( &s_hr, &s_min, &s_sec, &s_hsec );
	/*	printf("\n\nStart Time: %d:%02d:%02d.%02d\n", s_hr, s_min, s_sec, s_hsec );*/
#endif

	load_graph( argv[1], network );

/* get source number */
	if ((network->source = find_number( argv[2], network )) == FALSE )
	{
		printf("bad source node - %s\n", argv[2]);
		exit(1);
	}

/* get sink number */
	if ((network->sink = find_number( argv[3], network )) == FALSE )
	{
		printf("bad sink node - %s\n", argv[3]);
		exit(1);
	}

	printf("Using file %s, with source = %s, and sink = %s\n",
			  argv[1], argv[2], argv[3]);

	/* set number of restoration paths needed */
	network->restoration_paths = network->work_matrix[network->source][network->sink];
	printf("Broken Channels = %d\n", network->restoration_paths );

	/* simulate cut between source and sink */
	network->capacity[network->source][network->sink] = 0;
	network->capacity[network->sink][network->source] = 0;

#ifdef GRAPH
	/* graphical display */
	display_init( argv[1] );
#endif

#ifdef DEBUG
	print_capacity( network );
#endif

	max_flow( network, FORWARD );

#ifndef GRAPH
	printf("Maximum Channels = %d\n", network->excess[ network->sink ] );
#endif

	max_flow( network, BACKWARD);


/* print final flow, distance, excess, and residual */
#ifdef DEBUG
	dump_info( network );
#endif


/* print out one possible set of paths to get maximum flow */
	show_paths( network );

#ifdef GRAPH
/* graphical display */
	display_delete();
#endif

#ifndef GRAPH
	GetTime( &e_hr, &e_min, &e_sec, &e_hsec );
/*	printf("End Time: %d:%02d:%02d.%02d\n", e_hr, e_min, e_sec, e_hsec );*/

	s_total = s_hr*360000 + s_min*6000 + s_sec*100 + s_hsec;
	e_total = e_hr*360000 + e_min*6000 + e_sec*100 + e_hsec;
/* printf("e_total = %ld;  s_total = %ld\n", e_total, s_total ); */
	path_finding_time = (e_total - s_total) * 10;
	printf("DT = %d;  PF = %ld;  CE = %d;  ",
			  DIAGNOSIS_TIME, path_finding_time, CONNECTION_TIME );
	printf("Total Time: %ld msec.\n",
			 (DIAGNOSIS_TIME + path_finding_time + CONNECTION_TIME) );

	printf("--------------------------------------------------------------\n\n");
#endif

	return( 0 );

} /* main */