Pastey.net - paste bin

Language:

C++ Change language:

Pastebin:

115644

Author:

Unknown

Subject:

Maximum Flow Minimum Cut

Created:

2009-06-09 06:30:11

Download and save
Toggle line numbers

1	// Derived from
2	// http://www.aduni.org/courses/algorithms/handouts/Reciation_09.html#25630
3
4	// For Summer 2002 CSE 2320 Lab 4, the following changes were made to ff.c:
5	// 1. Adjacency lists (sorting, etc.)
6	// 2. Print minimum cut
7
8	// The Ford-Fulkerson Algorithm in C
9
10	#include <stdio.h>
11	#include <stdlib.h>
12	// For getrusage()
13	#include <sys/time.h>
14	#include <sys/resource.h>
15
16	// Basic Definitions
17
18	#define WHITE 0
19	#define GRAY 1
20	#define BLACK 2
21	#define oo 1000000000
22
23	// Declarations
24
25	int n; // number of nodes
26	int residualEdges; // number of edges in residual network
27	struct edge {
28	int tail,head,capacity,flow,inverse;
29	};
30	typedef struct edge edgeType;
31	edgeType *edgeTab;
32	int *firstEdge; // Table indicating first in range of edges with a common tail
33
34	int *color; // Needed for breadth-first search
35	int *pred; // Array to store augmenting path
36	int *predEdge; // edgeTab subscript of edge used to reach vertex i in BFS
37
38	float CPUtime()
39	{
40	struct rusage rusage;
41
42	getrusage(RUSAGE_SELF,&rusage);
43	return rusage.ru_utime.tv_sec+rusage.ru_utime.tv_usec/1000000.0
44	+ rusage.ru_stime.tv_sec+rusage.ru_stime.tv_usec/1000000.0;
45	}
46
47	int min (int x, int y)
48	{
49	return x<y ? x : y; // returns minimum of x and y
50	}
51
52	// Queue for breadth-first search - not circular.
53
54	int head,tail;
55	int *q;
56
57	void enqueue (int x)
58	{
59	q[tail] = x;
60	tail++;
61	color[x] = GRAY;
62	}
63
64	int dequeue ()
65	{
66	int x = q[head];
67	head++;
68	color[x] = BLACK;
69	return x;
70	}
71
72	// Breadth-First Search for an augmenting path
73
74	int bfs (int start, int target)
75	// Searches for path from start to target.
76	// Returns 1 if found, otherwise 0.
77	{
78	int u,v,i;
79
80	for (u=0; u<n; u++)
81	color[u] = WHITE;
82	head = tail = 0; // Since q is not circular, it is reinitialized for each BFS
83	enqueue(start);
84	pred[start] = -1;
85	while (head!=tail)
86	{
87	u=dequeue();
88	if (u==target)
89	return 1;
90
91	// Search all adjacent white nodes v. If the residual capacity
92	// from u to v in the residual network is positive,
93	// enqueue v.
94	for (i=firstEdge[u]; i<firstEdge[u+1]; i++)
95	{
96	v=edgeTab[i].head;
97	if (color[v]==WHITE && edgeTab[i].capacity-edgeTab[i].flow>0)
98	{
99	enqueue(v);
100	pred[v] = u;
101	predEdge[v]=i;
102	}
103	}
104	}
105	// No augmenting path remains, so a maximum flow and minimum cut
106	// have been found. Black vertices are in the
107	// source side (S) of the minimum cut, while white vertices are in the
108	// sink side (T).
109
110	return 0;
111	}
112
113	// Ford-Fulkerson Algorithm
114
115	int max_flow (int source, int sink)
116	{
117	int i,j,u;
118	int max_flow;
119	int APcount=0;
120
121	color=(int) malloc(nsizeof(int));
122	pred=(int) malloc(nsizeof(int));
123	predEdge=(int) malloc(nsizeof(int));
124	q=(int) malloc(nsizeof(int));
125	if (!color \|\| !pred \|\| !predEdge \|\| !q)
126	{
127	printf("malloc failed %d\n",__LINE__);
128	exit(0);
129	}
130
131	// Initialize empty flow.
132	max_flow = 0;
133	for (i=0; i<residualEdges; i++)
134	edgeTab[i].flow=0;
135
136	// While there exists an augmenting path,
137	// increment the flow along this path.
138	while (bfs(source,sink))
139	{
140	// Determine the amount by which we can increment the flow.
141	int increment = oo;
142	APcount++;
143	for (u=sink; pred[u]!=(-1); u=pred[u])
144	{
145	i=predEdge[u];
146	increment = min(increment,edgeTab[i].capacity-edgeTab[i].flow);
147	}
148	// Now increment the flow.
149	for (u=sink; pred[u]!=(-1); u=pred[u])
150	{
151	i = edgeTab[predEdge[u]].inverse;
152	edgeTab[predEdge[u]].flow += increment;
153	edgeTab[i].flow -= increment; // Reverse in residual
154	}
155	if (n<=20)
156	{
157	// Path trace
158	for (u=sink; pred[u]!=(-1); u=pred[u])
159	printf("%d<-",u);
160	printf("%d adds %d incremental flow\n",source,increment);
161	}
162	max_flow += increment;
163	}
164	printf("%d augmenting paths\n",APcount);
165	// No more augmenting paths, so cut is based on reachability from last BFS.
166	if (n<=20)
167	{
168	printf("S side of min-cut:\n");
169	for (u=0; u<n; u++)
170	if (color[u]==BLACK)
171	printf("%d\n",u);
172
173	printf("T side of min-cut:\n");
174	for (u=0; u<n; u++)
175	if (color[u]==WHITE)
176	printf("%d\n",u);
177	}
178
179	free(color);
180	free(pred);
181	free(predEdge);
182	free(q);
183
184	return max_flow;
185	}
186
187	// Reading the input file and organize adjacency lists for residual network.
188
189	int tailThenHead(const void* xin, const void* yin)
190	// Used in calls to qsort() and bsearch() for read_input_file()
191	{
192	int result;
193	edgeType x,y;
194
195	x=(edgeType*) xin;
196	y=(edgeType*) yin;
197	result=x->tail - y->tail;
198	if (result!=0)
199	return result;
200	else
201	return x->head - y->head;
202	}
203
204	void dumpEdges(int count)
205	{
206	int i;
207
208	printf(" i tail head cap\n");
209	for (i=0; i<count; i++)
210	printf("%3d %3d %3d %5d\n",i,edgeTab[i].tail,edgeTab[i].head,
211	edgeTab[i].capacity);
212	}
213
214	void dumpFinal()
215	{
216	int i;
217
218	printf("Initialized residual network:\n");
219	printf("Vertex firstEdge\n");
220	for (i=0; i<n; i++)
221	printf(" %3d %3d\n",i,firstEdge[i]);
222	printf("=================\n");
223	printf(" %3d %3d\n",n,firstEdge[n]);
224
225	printf(" i tail head cap inv\n");
226	for (i=0; i<residualEdges; i++)
227	printf("%3d %3d %3d %5d %3d\n",i,edgeTab[i].tail,edgeTab[i].head,
228	edgeTab[i].capacity,edgeTab[i].inverse);
229	}
230
231	void read_input_file()
232	{
233	int tail,head,capacity,i,j;
234	int inputEdges; // Number of edges in input file.
235	int workingEdges; // Number of residual network edges initially
236	// generated from input file.
237	edgeType work;
238	edgeType *ptr;
239	float startCPU,stopCPU;
240
241	// read number of nodes and edges
242	scanf("%d %d",&n,&inputEdges);
243	// Table is allocated at worst-case size, since space for inverses is needed.
244	edgeTab=(edgeType) malloc(2inputEdges*sizeof(edgeType));
245	if (!edgeTab)
246	{
247	printf("edgeTab malloc failed %d\n",__LINE__);
248	exit(0);
249	}
250	// read edges, each with a capacity
251	workingEdges=0;
252	for (i=0; i<inputEdges; i++)
253	{
254	scanf("%d %d %d",&tail,&head,&capacity);
255	// Test for illegal edge, including incoming to source and outgoing from
256	// sink.
257	if (tail<0 \|\| tail>=n-1 \|\| head<1 \|\| head>=n \|\| capacity<=0)
258	{
259	printf("Invalid input %d %d %d at %d\n",tail,head,capacity,__LINE__);
260	exit(0);
261	}
262	// Save input edge
263	edgeTab[workingEdges].tail=tail;
264	edgeTab[workingEdges].head=head;
265	edgeTab[workingEdges].capacity=capacity;
266	workingEdges++;
267	// Save inverse of input edge
268	edgeTab[workingEdges].tail=head;
269	edgeTab[workingEdges].head=tail;
270	edgeTab[workingEdges].capacity=0;
271	workingEdges++;
272	}
273	if (n<=20)
274	{
275	printf("Input & inverses:\n");
276	dumpEdges(workingEdges);
277	}
278
279	// Sort edges to make edges with common tail contiguous in edgeTab,
280	// along with making parallel edges contiguous.
281	// A faster sort is unlikely to speed-up substantially.
282	startCPU=CPUtime();
283	qsort(edgeTab,workingEdges,sizeof(edgeType),tailThenHead);
284	stopCPU=CPUtime();
285	printf("qsort CPU %f\n",stopCPU-startCPU);
286	if (n<=20)
287	{
288	printf("Sorted edges:\n");
289	dumpEdges(workingEdges);
290	}
291
292	// Coalesce parallel edges into a single edge by adding their capacities.
293	residualEdges=0;
294	for (i=1; i<workingEdges; i++)
295	if (edgeTab[residualEdges].tail==edgeTab[i].tail
296	&& edgeTab[residualEdges].head==edgeTab[i].head)
297	edgeTab[residualEdges].capacity+=edgeTab[i].capacity; // \|\| case
298	else
299	{
300	residualEdges++;
301	edgeTab[residualEdges].tail=edgeTab[i].tail;
302	edgeTab[residualEdges].head=edgeTab[i].head;
303	edgeTab[residualEdges].capacity=edgeTab[i].capacity;
304	}
305	residualEdges++;
306	if (n<=20)
307	{
308	printf("Coalesced edges:\n");
309	dumpEdges(residualEdges);
310	}
311
312	// Set field in each edgeTab struct to point to inverse
313	startCPU=CPUtime();
314	for (i=0; i<residualEdges; i++)
315	{
316	work.tail=edgeTab[i].head;
317	work.head=edgeTab[i].tail;
318	ptr=(edgeType*) bsearch(&work,edgeTab,residualEdges,sizeof(edgeType),
319	tailThenHead);
320	if (ptr==NULL)
321	{
322	printf("bsearch %d failed %d\n",i,__LINE__);
323	exit(0);
324	}
325	edgeTab[i].inverse=ptr-edgeTab; // ptr arithmetic to get subscript
326	}
327	stopCPU=CPUtime();
328	printf("set inverses CPU %f\n",stopCPU-startCPU);
329
330	// For each vertex i, determine first edge in edgeTab with
331	// a tail >= i.
332	firstEdge=(int) malloc((n+1)sizeof(int));
333	if (!firstEdge)
334	{
335	printf("malloc failed %d\n",__LINE__);
336	exit(0);
337	}
338	j=0;
339	for (i=0; i<n; i++)
340	{
341	firstEdge[i]=j;
342	// Skip over edges with vertex i as their tail.
343	for ( ;
344	j<residualEdges && edgeTab[j].tail==i;
345	j++)
346	;
347	}
348	firstEdge[n]=residualEdges; //Sentinel
349	if (n<=20)
350	dumpFinal();
351	}
352
353	int main ()
354	{
355	int i,j;
356	float startCPU,stopCPU;
357
358	read_input_file();
359	startCPU=CPUtime();
360	printf("total flow is %d\n",max_flow(0,n-1)); // 0=source, n-1=sink
361	stopCPU=CPUtime();
362	printf("Ford-Fulkerson time %f\n",stopCPU-startCPU);
363	if (n<=20)
364	{
365	printf("flows along edges:\n");
366	for (i=0; i<residualEdges; i++)
367	if (edgeTab[i].flow>0)
368	printf("%d->%d has %d\n",edgeTab[i].tail,
369	edgeTab[i].head,edgeTab[i].flow);
370	}
371	free(edgeTab);
372	free(firstEdge);
373	}
374
375

Download and save
Toggle line numbers

Thread:

[115644] Maximum Flow Minimum Cut by Unknown at 2009-06-09 06:30:11

Tip: Click the line numbers to toggle highliting on that line.

Paste followup:

Language:
Author:
Subject:
Secure the url for this pastey.

// 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 <stdio.h>
#include <stdlib.h>
// For getrusage()
#include <sys/time.h>
#include <sys/resource.h>

// 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 x<y ? x : y;  // returns minimum of x and y
}

// Queue for breadth-first search - not circular.

int head,tail;
int *q;

void enqueue (int x)
{
q[tail] = x;
tail++;
color[x] = GRAY;
}

int dequeue ()
{
int x = q[head];
head++;
color[x] = BLACK;
return x;
}

// Breadth-First Search for an augmenting path

int bfs (int start, int target)
// Searches for path from start to target.
// Returns 1 if found, otherwise 0.
{
int u,v,i;

for (u=0; u<n; u++)
  color[u] = WHITE;
head = tail = 0;  // Since q is not circular, it is reinitialized for each BFS
enqueue(start);
pred[start] = -1;
while (head!=tail)
{
  u=dequeue();
  if (u==target)
    return 1;

// Search all adjacent white nodes v. If the residual capacity
  // from u to v in the residual network is positive,
  // enqueue v.
  for (i=firstEdge[u]; i<firstEdge[u+1]; i++)
  {
    v=edgeTab[i].head;
    if (color[v]==WHITE && edgeTab[i].capacity-edgeTab[i].flow>0)
    {
      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; i<residualEdges; i++)
  edgeTab[i].flow=0;

// While there exists an augmenting path,
// increment the flow along this path.
while (bfs(source,sink))
{
  // Determine the amount by which we can increment the flow.
  int increment = oo;
  APcount++;
  for (u=sink; pred[u]!=(-1); u=pred[u])
  {
    i=predEdge[u];
    increment = min(increment,edgeTab[i].capacity-edgeTab[i].flow);
  }
  // Now increment the flow.
  for (u=sink; pred[u]!=(-1); u=pred[u])
  {
    i = edgeTab[predEdge[u]].inverse;
    edgeTab[predEdge[u]].flow += increment;
    edgeTab[i].flow -= increment;  // Reverse in residual
  }
  if (n<=20)
  {
    // Path trace
    for (u=sink; pred[u]!=(-1); u=pred[u])
      printf("%d<-",u);
    printf("%d adds %d incremental flow\n",source,increment);
  }
  max_flow += increment;
}
printf("%d augmenting paths\n",APcount);
// No more augmenting paths, so cut is based on reachability from last BFS.
if (n<=20)
{
  printf("S side of min-cut:\n");
  for (u=0; u<n; u++)
    if (color[u]==BLACK)
      printf("%d\n",u);

printf("T side of min-cut:\n");
  for (u=0; u<n; u++)
    if (color[u]==WHITE)
      printf("%d\n",u);
}

free(color);
free(pred);
free(predEdge);
free(q);

return max_flow;
}

// Reading the input file and organize adjacency lists for residual network.

int tailThenHead(const void* xin, const void* yin)
// Used in calls to qsort() and bsearch() for read_input_file()
{
int result;
edgeType *x,*y;

x=(edgeType*) xin;
y=(edgeType*) yin;
result=x->tail - 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<count; i++)
  printf("%3d %3d  %3d %5d\n",i,edgeTab[i].tail,edgeTab[i].head,
    edgeTab[i].capacity);
}

void dumpFinal()
{
int i;

printf("Initialized residual network:\n");
printf("Vertex firstEdge\n");
for (i=0; i<n; i++)
  printf(" %3d    %3d\n",i,firstEdge[i]);
printf("=================\n");
printf(" %3d    %3d\n",n,firstEdge[n]);

printf("  i tail head  cap  inv\n");
for (i=0; i<residualEdges; i++)
  printf("%3d %3d  %3d %5d  %3d\n",i,edgeTab[i].tail,edgeTab[i].head,
    edgeTab[i].capacity,edgeTab[i].inverse);
}

void read_input_file()
{
int tail,head,capacity,i,j;
int inputEdges;     // Number of edges in input file.
int workingEdges;   // Number of residual network edges initially
                    // generated from input file.
edgeType work;
edgeType *ptr;
float startCPU,stopCPU;

// read number of nodes and edges
scanf("%d %d",&n,&inputEdges);
// Table is allocated at worst-case size, since space for inverses is needed.
edgeTab=(edgeType*) malloc(2*inputEdges*sizeof(edgeType));
if (!edgeTab)
{
  printf("edgeTab malloc failed %d\n",__LINE__);
  exit(0);
}
// read edges, each with a capacity
workingEdges=0;
for (i=0; i<inputEdges; i++)
{
  scanf("%d %d %d",&tail,&head,&capacity);
  // Test for illegal edge, including incoming to source and outgoing from
  // sink.
  if (tail<0 || tail>=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<workingEdges; i++)
  if (edgeTab[residualEdges].tail==edgeTab[i].tail
  &&  edgeTab[residualEdges].head==edgeTab[i].head)
    edgeTab[residualEdges].capacity+=edgeTab[i].capacity;  // || case
  else
  {
    residualEdges++;
    edgeTab[residualEdges].tail=edgeTab[i].tail;
    edgeTab[residualEdges].head=edgeTab[i].head;
    edgeTab[residualEdges].capacity=edgeTab[i].capacity;
  }
residualEdges++;
if (n<=20)
{
  printf("Coalesced edges:\n");
  dumpEdges(residualEdges);
}

// Set field in each edgeTab struct to point to inverse
startCPU=CPUtime();
for (i=0; i<residualEdges; i++)
{
  work.tail=edgeTab[i].head;
  work.head=edgeTab[i].tail;
  ptr=(edgeType*) bsearch(&work,edgeTab,residualEdges,sizeof(edgeType),
    tailThenHead);
  if (ptr==NULL)
  {
    printf("bsearch %d failed %d\n",i,__LINE__);
    exit(0);
  }
  edgeTab[i].inverse=ptr-edgeTab;  // ptr arithmetic to get subscript
}
stopCPU=CPUtime();
printf("set inverses CPU %f\n",stopCPU-startCPU);

// For each vertex i, determine first edge in edgeTab with
// a tail >= i.
firstEdge=(int*) malloc((n+1)*sizeof(int));
if (!firstEdge)
{
  printf("malloc failed %d\n",__LINE__);
  exit(0);
}
j=0;
for (i=0; i<n; i++)
{
  firstEdge[i]=j;
  // Skip over edges with vertex i as their tail.
  for ( ;
       j<residualEdges && edgeTab[j].tail==i;
       j++)
    ;
}
firstEdge[n]=residualEdges;  //Sentinel
if (n<=20)
  dumpFinal();
}

int main ()
{
int i,j;
float startCPU,stopCPU;

read_input_file();
startCPU=CPUtime();
printf("total flow is %d\n",max_flow(0,n-1));  // 0=source, n-1=sink
stopCPU=CPUtime();
printf("Ford-Fulkerson time %f\n",stopCPU-startCPU);
if (n<=20)
{
  printf("flows along edges:\n");
  for (i=0; i<residualEdges; i++)
    if (edgeTab[i].flow>0)
      printf("%d->%d has %d\n",edgeTab[i].tail,
        edgeTab[i].head,edgeTab[i].flow);
}
free(edgeTab);
free(firstEdge);
}

Tabstop: bigger biggest

Note: You can prefix a line with "@@@" to highlight it.