1 /************************************************************************/
2 /* */
3 /* Demo of Min-Cutw for Directed and Undirected Graphs */
4 /* */
5 /* Written by: Applegate, Bixby, Chvatal, and Cook */
6 /* Date: September, 1994 (Bonn) */
7 /* July 28, 1997 (bico) */
8 /* */
9 /************************************************************************/
10
11 #include "machdefs.h"
12 #include "util.h"
13 #include "cut.h"
14
15 #undef USE_DIRECTED_GRAPH
16
17 static int source = -1, sink = -1;
18 static int showcut = 0;
19 static int violatedcuts = 0;
20 static int use_shrink = 1;
21 static int find_global = 0;
22 static int binary_in = 0;
23 static char *fname = (char *) NULL;
24
25 #ifdef CC_PROTOTYPE_ANSI
26
27 int
28 main (int ac, char **av);
29
30 static void
31 usage (char *f),
32 display_cut (int *cut, int count);
33
34 static int
35 parseargs (int ac, char **av),
36 shrink_ones (int ncount, int ecount, int *elist, double *dlen,
37 int *oncount, int *oecount, int **olist, double **olen,
38 double *minval),
39 display_all_cuts (double val, int cnt, int *cut, void *pass_param);
40
41 #else
42
43 int
44 main ();
45
46 static void
47 usage (),
48 display_cut ();
49
50 static int
51 parseargs (),
52 shrink_ones (),
53 display_all_cuts ();
54
55 #endif
56
57 #ifdef USE_DIRECTED_GRAPH
58 #ifdef CC_PROTOTYPE_ANSI
59 static int
60 duplicate_edges (int ncount, int ecount, int *elist, double *ecap,
61 int **tlist, double **tcap);
62 #else
63 duplicate_edges ();
64 #endif
65 #endif
66
67 #ifdef CC_PROTOTYPE_ANSI
main(int ac,char ** av)68 int main (int ac, char **av)
69 #else
70 int main (ac, av)
71 int ac;
72 char **av;
73 #endif
74 {
75 int rval = 0;
76 double val;
77 double szeit;
78 int i, cutcount;
79 int ncount, ecount;
80 int *elist = (int *) NULL;
81 int *cut = (int *) NULL;
82 int **mycut = (int **) NULL;
83 double *ecap = (double *) NULL;
84
85 if (parseargs (ac, av)) goto CLEANUP;
86
87 if (find_global && violatedcuts) {
88 fprintf (stderr, "use at most one of -p and -c arguments\n");
89 goto CLEANUP;
90 }
91
92 #ifdef USE_DIRECTED
93 if (find_global || violatedcuts) {
94 fprintf (stderr, "not set up for global cut in directed graphs\n");
95 goto CLEANUP;
96 }
97 #endif
98
99
100 rval = CCutil_getedges_double (&ncount, fname, &ecount, &elist, &ecap,
101 binary_in);
102 if (rval) {
103 fprintf (stderr, "getedges_double failed\n"); goto CLEANUP;
104 }
105
106 if (showcut) {
107 mycut = &cut;
108 } else {
109 mycut = (int **) NULL;
110 }
111
112 if (find_global) {
113 szeit = CCutil_zeit ();
114 rval = CCcut_mincut (ncount, ecount, elist, ecap, &val, mycut,
115 &cutcount);
116 if (rval) {
117 fprintf (stderr, "CCcut_mincut failed\n"); goto CLEANUP;
118 }
119 printf ("Minimum Cut Value: %f (%.2f seconds)\n", val, CCutil_zeit () - szeit);
120 fflush (stdout);
121 if (showcut) display_cut (cut, cutcount);
122 goto CLEANUP;
123 } else if (violatedcuts) {
124 szeit = CCutil_zeit ();
125 rval = CCcut_violated_cuts (ncount, ecount, elist, ecap,
126 2.0 - CC_MINCUT_ONE_EPSILON, display_all_cuts, (void *) NULL);
127 if (rval) {
128 fprintf (stderr, "CCcut_violated_cuts failed\n");
129 goto CLEANUP;
130 }
131 printf ("Running time: %.2f seconds\n", CCutil_zeit () - szeit);
132 goto CLEANUP;
133 }
134
135 szeit = CCutil_zeit ();
136 if (use_shrink) {
137 int tncount, tecount;
138 int *telist = (int *) NULL;
139 double *tecap = (double *) NULL;
140 double minval = CC_MINCUT_BIGDOUBLE;
141 double sszeit = CCutil_zeit ();
142
143 rval = shrink_ones (ncount, ecount, elist, ecap, &tncount, &tecount,
144 &telist, &tecap, &minval);
145 if (rval) {
146 fprintf (stderr, "shrink_ones failed\n"); goto CLEANUP;
147 }
148 printf ("Shrunk graph has %d nodes and %d edges\n", tncount, tecount);
149 if (minval != CC_MINCUT_BIGDOUBLE) {
150 printf ("Shrinking found cut of value %f\n", minval);
151 }
152 fflush (stdout);
153 printf ("Time for shrinking: %.2f seconds\n", CCutil_zeit () - sszeit);
154 fflush (stdout);
155 CC_IFFREE(elist, int);
156 CC_IFFREE(ecap, double);
157 ncount = tncount;
158 ecount = tecount;
159 elist = telist;
160 ecap = tecap;
161 }
162
163 #ifdef USE_DIRECTED_GRAPH
164 {
165 int tncount, tecount;
166 int *telist = (int *) NULL;
167 double *tecap = (double *) NULL;
168
169 rval = duplicate_edges (ncount, ecount, elist, ecap, &telist, &tecap);
170 if (rval) {
171 fprintf (stderr, "duplicated_edges failed\n"); goto CLEANUP;
172 }
173 CC_IFFREE(elist, int);
174 CC_IFFREE(ecap, double);
175 ecount *= 2;
176 elist = telist;
177 ecap = tecap;
178 }
179 #endif
180
181
182 if (source == -1)
183 source = 0;
184
185 if (sink != -1) {
186 if (source < 0 || sink < 0 || source >= ncount ||
187 sink >= ncount || source == sink) {
188 printf ("Bad source sink pair\n");
189 fflush (stdout);
190 goto CLEANUP;
191 }
192
193 szeit = CCutil_zeit ();
194 rval = CCcut_mincut_st (ncount, ecount, elist, ecap, source, sink,
195 &val, mycut, &cutcount);
196 if (rval) {
197 fprintf (stderr, "mincut_st failed\n"); goto CLEANUP;
198 }
199 printf ("Cut value: %f\n", val);
200 printf ("Running Time: %.2f (seconds)\n", CCutil_zeit () - szeit);
201 fflush (stdout);
202
203 if (showcut) display_cut (cut, cutcount);
204 } else {
205 double minval = CC_MINCUT_BIGDOUBLE;
206 double fzeit = CCutil_zeit ();
207
208 printf ("compute all cuts from source node %d\n", source);
209 fflush (stdout);
210 for (i = 0; i < ncount; i++) {
211 if (i != source) {
212 rval = CCcut_mincut_st (ncount, ecount, elist, ecap, source, i,
213 &val, (int **) NULL, (int *) NULL);
214 if (rval) {
215 fprintf (stderr, "mincut_digraph failed\n"); goto CLEANUP;
216 }
217 if (val < minval)
218 minval = val;
219 printf ("."); fflush (stdout);
220 if (i % 75 == 0)
221 printf ("%d\n", i);
222 }
223 }
224 printf ("\nMinimum Cut Value: %f\n", minval);
225 printf ("Running Time: %.2f (seconds)\n", CCutil_zeit () - fzeit);
226 fflush (stdout);
227 }
228
229 printf ("Total Running Time: %.2f (seconds)\n", CCutil_zeit () - szeit);
230 fflush (stdout);
231
232 CLEANUP:
233
234 CC_IFFREE (elist, int);
235 CC_IFFREE (ecap, double);
236 CC_IFFREE (cut, int);
237 return 0;
238 }
239
240 #ifdef CC_PROTOTYPE_ANSI
parseargs(int ac,char ** av)241 static int parseargs (int ac, char **av)
242 #else
243 static int parseargs (ac, av)
244 int ac;
245 char **av;
246 #endif
247 {
248 int c;
249
250 while ((c = CCutil_bix_getopt (ac, av, "bcCps:St:")) != EOF)
251 switch (c) {
252 case 'b':
253 binary_in = 1;
254 break;
255 case 'c':
256 violatedcuts = 1;
257 break;
258 case 'C':
259 showcut++;
260 break;
261 case 'p':
262 find_global = 1;
263 break;
264 case 's':
265 source = atoi (CCutil_bix_optarg);
266 break;
267 case 'S':
268 use_shrink = 0;
269 break;
270 case 't':
271 sink = atoi (CCutil_bix_optarg);
272 break;
273 case '?':
274 default:
275 usage (av[0]);
276 return 1;
277 }
278 if (CCutil_bix_optind >= ac) {
279 usage (av[0]);
280 return 1;
281 }
282
283 fname = av[CCutil_bix_optind++];
284 return 0;
285 }
286
287 #ifdef CC_PROTOTYPE_ANSI
usage(char * f)288 static void usage (char *f)
289 #else
290 static void usage (f)
291 char *f;
292 #endif
293 {
294 fprintf (stderr, "usage: %s [- below -] edge_file\n", f);
295 fprintf (stderr, " b: binary input file\n");
296 fprintf (stderr, " c: display all cuts < 2.0\n");
297 fprintf (stderr, " p: use Padberg-Rinaldi style shrinking\n");
298 fprintf (stderr, " s #: source\n");
299 fprintf (stderr, " t #: sink\n");
300 fprintf (stderr, " S: do not use the TSP shrink routines\n");
301 fprintf (stderr, " C: display the min cut\n");
302 }
303
304 #ifdef CC_PROTOTYPE_ANSI
display_cut(int * cut,int count)305 static void display_cut (int *cut, int count)
306 #else
307 static void display_cut (cut, count)
308 int *cut;
309 int count;
310 #endif
311 {
312 int i;
313
314 printf ("MIN CUT:\n");
315 for (i = 0; i < count; i++) {
316 printf ("%3d ", cut[i]);
317 if (i % 10 == 9)
318 printf ("\n");
319 }
320 if (i % 10) printf ("\n");
321 fflush (stdout);
322 }
323
324 #ifdef USE_DIRECTED_GRAPH
325 #ifdef CC_PROTOTYPE_ANSI
duplicate_edges(int ncount,int ecount,int * elist,double * ecap,int ** tlist,double ** tcap)326 static int duplicate_edges (int ncount, int ecount, int *elist, double *ecap,
327 int **tlist, double **tcap)
328 #else
329 static int duplicate_edges (ncount, ecount, elist, ecap, tlist, tcap)
330 int ncount, ecount;
331 int *elist;
332 double *ecap;
333 int **tlist;
334 double **tcap;
335 #endif
336 {
337 int i;
338
339 *tlist = (int *) NULL;
340 *tcap = (double *) NULL;
341
342
343 /* Convert the graph to a digraph */
344
345 *tlist = CC_SAFE_MALLOC (4 * ecount, int);
346 *tcap = CC_SAFE_MALLOC (2 * ecount, double);
347 if (!*tlist || !*tcap) {
348 fprintf (stderr, "Out of memory in duplicate_edges\n");
349 CC_IFFREE (*tlist, int);
350 CC_IFFREE (*tcap, double);
351 return 1;
352 }
353
354 for (i = 0; i < ecount; i++) {
355 (*tlist)[4 * i] = (*tlist)[4 * i + 3] = elist[2 * i];
356 (*tlist)[4 * i + 1] = (*tlist)[4 * i + 2] = elist[2 * i + 1];
357 (*tcap)[2 * i] = (*tcap)[2 * i + 1] = ecap[i];
358 }
359
360 return 0;
361 }
362 #endif
363
364
365 #ifdef CC_PROTOTYPE_ANSI
shrink_ones(int ncount,int ecount,int * elist,double * dlen,int * oncount,int * oecount,int ** olist,double ** olen,double * minval)366 static int shrink_ones (int ncount, int ecount, int *elist, double *dlen,
367 int *oncount, int *oecount, int **olist, double **olen, double *minval)
368 #else
369 static int shrink_ones (ncount, ecount, elist, dlen, oncount, oecount, olist,
370 olen, minval)
371 int ncount, ecount;
372 int *elist;
373 double *dlen;
374 int *oncount, *oecount;
375 int **olist;
376 double **olen;
377 double *minval;
378 #endif
379 {
380 int rval = 0;
381 CC_SRKgraph G;
382
383 CCcut_SRK_init_graph (&G);
384 rval = CCcut_SRK_buildgraph (&G, ncount, ecount, elist, dlen);
385 if (rval) {
386 fprintf (stderr, "buildgraph failed in shrink_ones\n"); goto CLEANUP;
387 }
388 CCcut_SRK_subtour_shrink (&G, minval, CC_MINCUT_ONE_EPSILON,
389 (CC_SRKcallback *) NULL, (int **) NULL, (int *) NULL);
390
391 rval = CCcut_SRK_grab_edges (&G, oncount, oecount, olist, olen,
392 (CC_SRKexpinfo *) NULL);
393 if (rval) {
394 fprintf (stderr, "grab edges failed in shrink_ones\n"); goto CLEANUP;
395 }
396
397
398 CLEANUP:
399
400 CCcut_SRK_free_graph (&G);
401 return rval;
402 }
403
404 #ifdef CC_PROTOTYPE_ANSI
display_all_cuts(double val,int cnt,int * cut,void * pass_param)405 static int display_all_cuts (double val, int cnt, int *cut, void *pass_param)
406 #else
407 static int display_all_cuts (val, cnt, cut, pass_param)
408 double val;
409 int cnt;
410 int *cut;
411 void *pass_param;
412 #endif
413 {
414 if (pass_param) {
415 fprintf (stderr, "don't know about pass_param in display_all_cuts\n");
416 return 1;
417 }
418
419 if (cut && cnt) {
420 printf ("Found cut of value %f\n", val); fflush (stdout);
421 }
422 return 0;
423 }
424