1 /* -*- mode: C -*- */
2 /*
3 IGraph library.
4 Copyright (C) 2010-2012 Gabor Csardi <csardi.gabor@gmail.com>
5 334 Harvard street, Cambridge, MA 02139 USA
6
7 This program is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 2 of the License, or
10 (at your option) any later version.
11
12 This program is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with this program; if not, write to the Free Software
19 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
20 02110-1301 USA
21
22 */
23
24 #include <igraph.h>
25
26 #include "core/marked_queue.h"
27 #include "core/estack.h"
28
29 #include "flow/flow_internal.h"
30
31 #include "test_utilities.inc"
32
test_all_st_cuts(const igraph_t * graph,long int source,long int target)33 int test_all_st_cuts(const igraph_t *graph,
34 long int source,
35 long int target) {
36 igraph_vector_ptr_t cuts, partition1s;
37 long int n, i;
38
39 igraph_vector_ptr_init(&cuts, 0);
40 igraph_vector_ptr_init(&partition1s, 0);
41 igraph_all_st_cuts(graph, &cuts, &partition1s,
42 source, target);
43
44 n = igraph_vector_ptr_size(&partition1s);
45 printf("Partitions and cuts:\n");
46 for (i = 0; i < n; i++) {
47 igraph_vector_t *v = VECTOR(partition1s)[i];
48 igraph_vector_t *v2 = VECTOR(cuts)[i];
49 printf("P: ");
50 igraph_vector_print(v);
51 igraph_vector_destroy(v);
52 igraph_free(v);
53 printf("C: ");
54 igraph_vector_print(v2);
55 igraph_vector_destroy(v2);
56 igraph_free(v2);
57 }
58 igraph_vector_ptr_destroy(&partition1s);
59 igraph_vector_ptr_destroy(&cuts);
60
61 return 0;
62 }
63
main()64 int main() {
65 igraph_t g;
66 igraph_vector_ptr_t cuts, partition1s;
67 long int i, n;
68
69 igraph_marked_queue_t S;
70 igraph_estack_t T;
71 long int v;
72 igraph_vector_t Isv;
73
74 /* ----------------------------------------------------------- */
75 /* This is the example from the Provan-Shier paper,
76 for calculating the dominator tree and finding the right pivot
77 element */
78
79 igraph_small(&g, 12, IGRAPH_DIRECTED,
80 /* a->b */ 0, 1,
81 /* b->t */ 1, 11,
82 /* c->b */ 2, 1, /* c->d */ 2, 3,
83 /* d->e */ 3, 4, /* d->i */ 3, 8,
84 /* e->c */ 4, 2,
85 /* f->c */ 5, 2, /* f->e */ 5, 4,
86 /* g->d */ 6, 3, /* g->e */ 6, 4, /* g->f */ 6, 5,
87 /* g->j */ 6, 9,
88 /* h->g */ 7, 6, /* h->t */ 7, 11,
89 /* i->a */ 8, 0,
90 /* j->i */ 9, 8,
91 /* s->a */ 10, 0, /* s->c */ 10, 2, /* s->h */ 10, 7,
92 -1);
93
94 /* S={s,a} */
95 igraph_marked_queue_init(&S, igraph_vcount(&g));
96 igraph_marked_queue_start_batch(&S);
97 igraph_marked_queue_push(&S, 10);
98 igraph_marked_queue_push(&S, 0);
99
100 /* T={t} */
101 igraph_estack_init(&T, igraph_vcount(&g), 1);
102 igraph_estack_push(&T, 11);
103
104 igraph_vector_init(&Isv, 0);
105 igraph_i_all_st_cuts_pivot(&g, &S, &T,
106 /*source=*/ 10, /*target=*/ 11,
107 &v, &Isv, NULL);
108
109 /* Expected result: v=c, Isv={c,d,e,i} */
110 printf("%li; ", v);
111 igraph_vector_print(&Isv);
112
113 igraph_vector_destroy(&Isv);
114 igraph_estack_destroy(&T);
115 igraph_marked_queue_destroy(&S);
116 igraph_destroy(&g);
117
118 /* ----------------------------------------------------------- */
119
120 igraph_small(&g, 3, IGRAPH_DIRECTED,
121 0, 1, 1, 2,
122 -1);
123
124 /* S={}, T={} */
125 igraph_marked_queue_init(&S, igraph_vcount(&g));
126 igraph_estack_init(&T, igraph_vcount(&g), 3);
127
128 igraph_vector_init(&Isv, 0);
129 igraph_i_all_st_cuts_pivot(&g, &S, &T,
130 /*source=*/ 0, /*target=*/ 2,
131 &v, &Isv, NULL);
132 printf("%li; ", v);
133 igraph_vector_print(&Isv);
134
135 igraph_vector_destroy(&Isv);
136 igraph_estack_destroy(&T);
137 igraph_marked_queue_destroy(&S);
138 igraph_destroy(&g);
139
140 /* ----------------------------------------------------------- */
141
142 igraph_small(&g, 3, IGRAPH_DIRECTED,
143 0, 1, 1, 2,
144 -1);
145
146 /* S={}, T={0} */
147 igraph_marked_queue_init(&S, igraph_vcount(&g));
148
149 igraph_estack_init(&T, igraph_vcount(&g), 3);
150 igraph_estack_push(&T, 0);
151
152 igraph_vector_init(&Isv, 0);
153 igraph_i_all_st_cuts_pivot(&g, &S, &T,
154 /*source=*/ 0, /*target=*/ 2,
155 &v, &Isv, NULL);
156 printf("%li; ", v);
157 igraph_vector_print(&Isv);
158
159 igraph_vector_destroy(&Isv);
160 igraph_estack_destroy(&T);
161 igraph_marked_queue_destroy(&S);
162 igraph_destroy(&g);
163
164 /* ----------------------------------------------------------- */
165
166 igraph_small(&g, 3, IGRAPH_DIRECTED,
167 0, 1, 1, 2,
168 -1);
169
170 /* S={0}, T={} */
171 igraph_marked_queue_init(&S, igraph_vcount(&g));
172 igraph_marked_queue_push(&S, 0);
173
174 igraph_estack_init(&T, igraph_vcount(&g), 3);
175
176 igraph_vector_init(&Isv, 0);
177 igraph_i_all_st_cuts_pivot(&g, &S, &T,
178 /*source=*/ 0, /*target=*/ 2,
179 &v, &Isv, NULL);
180 printf("%li; ", v);
181 igraph_vector_print(&Isv);
182
183 igraph_vector_destroy(&Isv);
184 igraph_estack_destroy(&T);
185 igraph_marked_queue_destroy(&S);
186 igraph_destroy(&g);
187
188 /* ----------------------------------------------------------- */
189
190 igraph_small(&g, 3, IGRAPH_DIRECTED,
191 0, 1, 1, 2,
192 -1);
193
194 /* S={0}, T={1} */
195 igraph_marked_queue_init(&S, igraph_vcount(&g));
196 igraph_marked_queue_push(&S, 0);
197
198 igraph_estack_init(&T, igraph_vcount(&g), 3);
199 igraph_estack_push(&T, 1);
200
201 igraph_vector_init(&Isv, 0);
202 igraph_i_all_st_cuts_pivot(&g, &S, &T,
203 /*source=*/ 0, /*target=*/ 2,
204 &v, &Isv, NULL);
205 printf("%li; ", v);
206 igraph_vector_print(&Isv);
207
208 igraph_vector_destroy(&Isv);
209 igraph_estack_destroy(&T);
210 igraph_marked_queue_destroy(&S);
211 igraph_destroy(&g);
212
213 /* ----------------------------------------------------------- */
214
215 igraph_small(&g, 3, IGRAPH_DIRECTED,
216 0, 1, 1, 2,
217 -1);
218
219 /* S={0,1}, T={} */
220 igraph_marked_queue_init(&S, igraph_vcount(&g));
221 igraph_marked_queue_push(&S, 0);
222 igraph_marked_queue_push(&S, 1);
223
224 igraph_estack_init(&T, igraph_vcount(&g), 3);
225
226 igraph_vector_init(&Isv, 0);
227 igraph_i_all_st_cuts_pivot(&g, &S, &T,
228 /*source=*/ 0, /*target=*/ 2,
229 &v, &Isv, NULL);
230 printf("%li; ", v);
231 igraph_vector_print(&Isv);
232
233 igraph_vector_destroy(&Isv);
234 igraph_estack_destroy(&T);
235 igraph_marked_queue_destroy(&S);
236 igraph_destroy(&g);
237
238 /* ----------------------------------------------------------- */
239
240 igraph_small(&g, 3, IGRAPH_DIRECTED,
241 0, 1, 1, 2,
242 -1);
243
244 igraph_vector_ptr_init(&partition1s, 0);
245 igraph_all_st_cuts(&g, /*cuts=*/ 0, &partition1s,
246 /*source=*/ 0, /*target=*/ 2);
247
248 n = igraph_vector_ptr_size(&partition1s);
249 for (i = 0; i < n; i++) {
250 igraph_vector_t *v = VECTOR(partition1s)[i];
251 igraph_vector_print(v);
252 igraph_vector_destroy(v);
253 igraph_free(v);
254 }
255 igraph_vector_ptr_destroy(&partition1s);
256
257 igraph_destroy(&g);
258
259 /* ----------------------------------------------------------- */
260
261 igraph_small(&g, 5, IGRAPH_DIRECTED,
262 0, 1, 1, 2, 1, 3, 2, 4, 3, 4,
263 -1);
264
265 igraph_vector_ptr_init(&partition1s, 0);
266 igraph_all_st_cuts(&g, /*cuts=*/ 0, &partition1s,
267 /*source=*/ 0, /*target=*/ 4);
268
269 n = igraph_vector_ptr_size(&partition1s);
270 for (i = 0; i < n; i++) {
271 igraph_vector_t *v = VECTOR(partition1s)[i];
272 igraph_vector_print(v);
273 igraph_vector_destroy(v);
274 igraph_free(v);
275 }
276 igraph_vector_ptr_destroy(&partition1s);
277
278 igraph_destroy(&g);
279
280 /* ----------------------------------------------------------- */
281
282 igraph_small(&g, 6, IGRAPH_DIRECTED,
283 0, 1, 1, 2, 1, 3, 2, 4, 3, 4, 1, 5, 5, 4,
284 -1);
285
286 igraph_vector_ptr_init(&cuts, 0);
287 igraph_vector_ptr_init(&partition1s, 0);
288 igraph_all_st_cuts(&g, &cuts, &partition1s,
289 /*source=*/ 0, /*target=*/ 4);
290
291 n = igraph_vector_ptr_size(&partition1s);
292 printf("Partitions and cuts:\n");
293 for (i = 0; i < n; i++) {
294 igraph_vector_t *v = VECTOR(partition1s)[i];
295 igraph_vector_t *v2 = VECTOR(cuts)[i];
296 printf("P: ");
297 igraph_vector_print(v);
298 igraph_vector_destroy(v);
299 igraph_free(v);
300 printf("C: ");
301 igraph_vector_print(v2);
302 igraph_vector_destroy(v2);
303 igraph_free(v2);
304 }
305 igraph_vector_ptr_destroy(&partition1s);
306 igraph_vector_ptr_destroy(&cuts);
307
308 igraph_destroy(&g);
309
310 /* ----------------------------------------------------------- */
311
312 igraph_small(&g, 3, IGRAPH_DIRECTED,
313 0, 2, 1, 2,
314 -1);
315
316 igraph_vector_ptr_init(&cuts, 0);
317 igraph_vector_ptr_init(&partition1s, 0);
318 igraph_all_st_cuts(&g, &cuts, &partition1s,
319 /*source=*/ 1, /*target=*/ 2);
320
321 n = igraph_vector_ptr_size(&partition1s);
322 printf("Partitions and cuts:\n");
323 for (i = 0; i < n; i++) {
324 igraph_vector_t *v = VECTOR(partition1s)[i];
325 igraph_vector_t *v2 = VECTOR(cuts)[i];
326 printf("P: ");
327 igraph_vector_print(v);
328 igraph_vector_destroy(v);
329 igraph_free(v);
330 printf("C: ");
331 igraph_vector_print(v2);
332 igraph_vector_destroy(v2);
333 igraph_free(v2);
334 }
335 igraph_vector_ptr_destroy(&partition1s);
336 igraph_vector_ptr_destroy(&cuts);
337
338 igraph_destroy(&g);
339
340 /* ----------------------------------------------------------- */
341
342 igraph_small(&g, 5, IGRAPH_DIRECTED,
343 0, 1, 1, 2, 2, 3, 3, 4, 3, 1,
344 -1);
345
346 igraph_vector_ptr_init(&cuts, 0);
347 igraph_vector_ptr_init(&partition1s, 0);
348 igraph_all_st_cuts(&g, &cuts, &partition1s,
349 /*source=*/ 0, /*target=*/ 4);
350
351 n = igraph_vector_ptr_size(&partition1s);
352 printf("Partitions and cuts:\n");
353 for (i = 0; i < n; i++) {
354 igraph_vector_t *v = VECTOR(partition1s)[i];
355 igraph_vector_t *v2 = VECTOR(cuts)[i];
356 printf("P: ");
357 igraph_vector_print(v);
358 igraph_vector_destroy(v);
359 igraph_free(v);
360 printf("C: ");
361 igraph_vector_print(v2);
362 igraph_vector_destroy(v2);
363 igraph_free(v2);
364 }
365 igraph_vector_ptr_destroy(&partition1s);
366 igraph_vector_ptr_destroy(&cuts);
367
368 igraph_destroy(&g);
369
370 /* ----------------------------------------------------------- */
371
372 igraph_small(&g, 7, IGRAPH_DIRECTED,
373 0, 1, 0, 2, 1, 3, 2, 3,
374 1, 4, 1, 5, 1, 6,
375 4, 2, 5, 2, 6, 2,
376 -1);
377
378 igraph_vector_ptr_init(&cuts, 0);
379 igraph_vector_ptr_init(&partition1s, 0);
380 igraph_all_st_cuts(&g, &cuts, &partition1s,
381 /*source=*/ 0, /*target=*/ 3);
382
383 n = igraph_vector_ptr_size(&partition1s);
384 printf("Partitions and cuts:\n");
385 for (i = 0; i < n; i++) {
386 igraph_vector_t *v = VECTOR(partition1s)[i];
387 igraph_vector_t *v2 = VECTOR(cuts)[i];
388 printf("P: ");
389 igraph_vector_print(v);
390 igraph_vector_destroy(v);
391 igraph_free(v);
392 printf("C: ");
393 igraph_vector_print(v2);
394 igraph_vector_destroy(v2);
395 igraph_free(v2);
396 }
397 igraph_vector_ptr_destroy(&partition1s);
398 igraph_vector_ptr_destroy(&cuts);
399
400 /* Check whether it also works if we don't provide partition1s */
401 igraph_vector_ptr_init(&cuts, 0);
402 igraph_vector_ptr_init(&partition1s, 0);
403 igraph_all_st_cuts(&g, &cuts, /*partition1s=*/ 0,
404 /*source=*/ 0, /*target=*/ 3);
405
406 n = igraph_vector_ptr_size(&cuts);
407 printf("Cuts only (no partitions):\n");
408 for (i = 0; i < n; i++) {
409 igraph_vector_t *v2 = VECTOR(cuts)[i];
410 printf("C: ");
411 igraph_vector_print(v2);
412 igraph_vector_destroy(v2);
413 igraph_free(v2);
414 }
415 igraph_vector_ptr_destroy(&partition1s);
416 igraph_vector_ptr_destroy(&cuts);
417
418 igraph_destroy(&g);
419
420 /* -----------------------------------------------------------
421 * Check problematic cases in issue #1102
422 * ----------------------------------------------------------- */
423
424 igraph_small(&g, 4, IGRAPH_DIRECTED,
425 0, 1, 1, 2, 2, 3,
426 -1);
427 test_all_st_cuts(&g, 0, 2);
428 igraph_destroy(&g);
429
430 igraph_small(&g, 5, IGRAPH_DIRECTED,
431 0, 1, 1, 2, 2, 3, 3, 4,
432 -1);
433 test_all_st_cuts(&g, 0, 2);
434 test_all_st_cuts(&g, 1, 3);
435 igraph_destroy(&g);
436
437 VERIFY_FINALLY_STACK();
438
439 return 0;
440 }
441