// Derived from // http://www.aduni.org/courses/algorithms/handouts/Reciation_09.html#25630 // For Summer 2002 CSE 2320 Lab 4, the following changes were made to ff.c: // 1. Adjacency lists (sorting, etc.) // 2. Print minimum cut // The Ford-Fulkerson Algorithm in C #include #include // For getrusage() #include #include // Basic Definitions #define WHITE 0 #define GRAY 1 #define BLACK 2 #define oo 1000000000 // Declarations int n; // number of nodes int residualEdges; // number of edges in residual network struct edge { int tail,head,capacity,flow,inverse; }; typedef struct edge edgeType; edgeType *edgeTab; int *firstEdge; // Table indicating first in range of edges with a common tail int *color; // Needed for breadth-first search int *pred; // Array to store augmenting path int *predEdge; // edgeTab subscript of edge used to reach vertex i in BFS float CPUtime() { struct rusage rusage; getrusage(RUSAGE_SELF,&rusage); return rusage.ru_utime.tv_sec+rusage.ru_utime.tv_usec/1000000.0 + rusage.ru_stime.tv_sec+rusage.ru_stime.tv_usec/1000000.0; } int min (int x, int y) { return x0) { enqueue(v); pred[v] = u; predEdge[v]=i; } } } // No augmenting path remains, so a maximum flow and minimum cut // have been found. Black vertices are in the // source side (S) of the minimum cut, while white vertices are in the // sink side (T). return 0; } // Ford-Fulkerson Algorithm int max_flow (int source, int sink) { int i,j,u; int max_flow; int APcount=0; color=(int*) malloc(n*sizeof(int)); pred=(int*) malloc(n*sizeof(int)); predEdge=(int*) malloc(n*sizeof(int)); q=(int*) malloc(n*sizeof(int)); if (!color || !pred || !predEdge || !q) { printf("malloc failed %d\n",__LINE__); exit(0); } // Initialize empty flow. max_flow = 0; for (i=0; itail - y->tail; if (result!=0) return result; else return x->head - y->head; } void dumpEdges(int count) { int i; printf(" i tail head cap\n"); for (i=0; i=n-1 || head<1 || head>=n || capacity<=0) { printf("Invalid input %d %d %d at %d\n",tail,head,capacity,__LINE__); exit(0); } // Save input edge edgeTab[workingEdges].tail=tail; edgeTab[workingEdges].head=head; edgeTab[workingEdges].capacity=capacity; workingEdges++; // Save inverse of input edge edgeTab[workingEdges].tail=head; edgeTab[workingEdges].head=tail; edgeTab[workingEdges].capacity=0; workingEdges++; } if (n<=20) { printf("Input & inverses:\n"); dumpEdges(workingEdges); } // Sort edges to make edges with common tail contiguous in edgeTab, // along with making parallel edges contiguous. // A faster sort is unlikely to speed-up substantially. startCPU=CPUtime(); qsort(edgeTab,workingEdges,sizeof(edgeType),tailThenHead); stopCPU=CPUtime(); printf("qsort CPU %f\n",stopCPU-startCPU); if (n<=20) { printf("Sorted edges:\n"); dumpEdges(workingEdges); } // Coalesce parallel edges into a single edge by adding their capacities. residualEdges=0; for (i=1; i= i. firstEdge=(int*) malloc((n+1)*sizeof(int)); if (!firstEdge) { printf("malloc failed %d\n",__LINE__); exit(0); } j=0; for (i=0; i0) printf("%d->%d has %d\n",edgeTab[i].tail, edgeTab[i].head,edgeTab[i].flow); } free(edgeTab); free(firstEdge); }