1 /* -*- mode: C -*- */
2 /*
3 IGraph library.
4 Copyright (C) 2006-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
check_flow(int errorinc,const igraph_t * graph,igraph_real_t flow_value,const igraph_vector_t * flow,const igraph_vector_t * cut,const igraph_vector_t * partition,const igraph_vector_t * partition2,long int source,long int target,const igraph_vector_t * capacity,igraph_bool_t print)26 int check_flow(int errorinc,
27 const igraph_t *graph, igraph_real_t flow_value,
28 const igraph_vector_t *flow, const igraph_vector_t *cut,
29 const igraph_vector_t *partition,
30 const igraph_vector_t *partition2,
31 long int source, long int target,
32 const igraph_vector_t *capacity,
33 igraph_bool_t print) {
34
35 long int i, n = igraph_vcount(graph), m = igraph_ecount(graph);
36 long int nc = igraph_vector_size(cut);
37 igraph_vector_t inedges, outedges;
38 igraph_bool_t directed = igraph_is_directed(graph);
39 igraph_real_t cutsize;
40 igraph_t graph_copy;
41 igraph_matrix_t sp;
42
43 if (print) {
44 printf("flow value: %g\n", (double) flow_value);
45 printf("flow: ");
46 igraph_vector_print(flow);
47 printf("first partition: ");
48 igraph_vector_print(partition);
49 printf("second partition: ");
50 igraph_vector_print(partition2);
51 printf("edges in the cut: ");
52 for (i = 0; i < nc; i++) {
53 long int edge = VECTOR(*cut)[i];
54 long int from = IGRAPH_FROM(graph, edge);
55 long int to = IGRAPH_TO (graph, edge);
56 if (!directed && from > to) {
57 igraph_integer_t tmp = from;
58 from = to;
59 to = tmp;
60 }
61 printf("%li-%li (%g), ", from, to, VECTOR(*capacity)[edge]);
62 }
63 printf("\n");
64 }
65 fflush(stdout);
66
67 /* Always less than the capacity */
68 for (i = 0; i < m; i++) {
69 if (VECTOR(*flow)[i] > VECTOR(*capacity)[i]) {
70 return errorinc + 3;
71 }
72 }
73
74 /* What comes in goes out, but only in directed graphs,
75 there is no in and out in undirected ones...
76 */
77 if (igraph_is_directed(graph)) {
78 igraph_vector_init(&inedges, 0);
79 igraph_vector_init(&outedges, 0);
80
81 for (i = 0; i < n; i++) {
82 long int n1, n2, j;
83 igraph_real_t in_flow = 0.0, out_flow = 0.0;
84 igraph_incident(graph, &inedges, i, IGRAPH_IN);
85 igraph_incident(graph, &outedges, i, IGRAPH_OUT);
86 n1 = igraph_vector_size(&inedges);
87 n2 = igraph_vector_size(&outedges);
88 for (j = 0; j < n1; j++) {
89 long int e = VECTOR(inedges)[j];
90 in_flow += VECTOR(*flow)[e];
91 }
92 for (j = 0; j < n2; j++) {
93 long int e = VECTOR(outedges)[j];
94 out_flow += VECTOR(*flow)[e];
95 }
96 if (i == source) {
97 if (in_flow > 0) {
98 return errorinc + 4;
99 }
100 if (out_flow != flow_value) {
101 return errorinc + 5;
102 }
103 } else if (i == target) {
104 if (out_flow > 0) {
105 return errorinc + 6;
106 }
107 if (in_flow != flow_value) {
108 return errorinc + 7;
109 }
110
111 } else {
112 if (in_flow != out_flow) {
113 return errorinc + 8;
114 }
115 }
116 }
117
118 igraph_vector_destroy(&inedges);
119 igraph_vector_destroy(&outedges);
120 }
121
122 /* Check the minimum cut size*/
123 for (i = 0, cutsize = 0.0; i < nc; i++) {
124 long int edge = VECTOR(*cut)[i];
125 cutsize += VECTOR(*capacity)[edge];
126 }
127 if (fabs(cutsize - flow_value) > 1e-14) {
128 return errorinc + 9;
129 }
130
131 /* Check that the cut indeed cuts */
132 igraph_copy(&graph_copy, graph);
133 igraph_delete_edges(&graph_copy, igraph_ess_vector(cut));
134 igraph_matrix_init(&sp, 1, 1);
135 igraph_shortest_paths(&graph_copy, &sp, /*from=*/ igraph_vss_1(source),
136 /*to=*/ igraph_vss_1(target), IGRAPH_OUT);
137 if (MATRIX(sp, 0, 0) != IGRAPH_INFINITY) {
138 return errorinc + 10;
139 }
140 igraph_matrix_destroy(&sp);
141 igraph_destroy(&graph_copy);
142
143 return 0;
144 }
145
main()146 int main() {
147
148 igraph_t g;
149 igraph_real_t flow_value;
150 igraph_vector_t cut;
151 igraph_vector_t capacity;
152 igraph_vector_t partition, partition2;
153 igraph_vector_t flow;
154 long int i, n;
155 igraph_integer_t source, target;
156 FILE *infile;
157 igraph_real_t flow_value2 = 0.0;
158 int check;
159 igraph_maxflow_stats_t stats;
160
161 igraph_vector_init(&capacity, 0);
162
163 /***************/
164 infile = fopen("ak-4102.max", "r");
165 igraph_read_graph_dimacs(&g, infile, 0, 0, &source, &target, &capacity,
166 IGRAPH_DIRECTED);
167 fclose(infile);
168
169 igraph_vector_init(&cut, 0);
170 igraph_vector_init(&partition, 0);
171 igraph_vector_init(&partition2, 0);
172 igraph_vector_init(&flow, 0);
173
174 igraph_maxflow(&g, &flow_value, &flow, &cut, &partition,
175 &partition2, source, target, &capacity, &stats);
176
177 if (flow_value != 8207) {
178 return 1;
179 }
180
181 n = igraph_vector_size(&cut);
182 for (i = 0; i < n; i++) {
183 long int e = VECTOR(cut)[i];
184 flow_value2 += VECTOR(capacity)[e];
185 }
186 if (flow_value != flow_value2) {
187 return 2;
188 }
189
190 /* Check the flow */
191 if ( (check = check_flow(0, &g, flow_value, &flow, &cut, &partition,
192 &partition2, source, target, &capacity,
193 /*print=*/ 0))) {
194 return check;
195 }
196
197 igraph_destroy(&g);
198 igraph_vector_destroy(&capacity);
199 igraph_vector_destroy(&cut);
200 igraph_vector_destroy(&partition);
201 igraph_vector_destroy(&partition2);
202 igraph_vector_destroy(&flow);
203
204 /* ------------------------------------- */
205
206 igraph_small(&g, 4, IGRAPH_UNDIRECTED,
207 0, 1, 0, 2, 1, 2, 1, 3, 2, 3, -1);
208 igraph_vector_init_int_end(&capacity, -1, 4, 2, 10, 2, 2, -1);
209 igraph_vector_init(&cut, 0);
210 igraph_vector_init(&partition, 0);
211 igraph_vector_init(&partition2, 0);
212 igraph_vector_init(&flow, 0);
213
214 igraph_maxflow(&g, &flow_value, &flow, &cut, &partition, &partition2,
215 /*source=*/ 0, /*target=*/ 3, &capacity, &stats);
216
217 if ( (check = check_flow(20, &g, flow_value, &flow, &cut, &partition,
218 &partition2, 0, 3, &capacity,
219 /*print=*/ 1))) {
220 return check;
221 }
222
223 igraph_vector_destroy(&cut);
224 igraph_vector_destroy(&partition2);
225 igraph_vector_destroy(&partition);
226 igraph_vector_destroy(&capacity);
227 igraph_vector_destroy(&flow);
228 igraph_destroy(&g);
229
230 /* ------------------------------------- */
231
232 igraph_small(&g, 6, IGRAPH_DIRECTED,
233 0, 1, 1, 2, 2, 3, 0, 5, 5, 4, 4, 3, 3, 0, -1);
234 igraph_vector_init_int_end(&capacity, -1, 3, 1, 2, 10, 1, 3, 2, -1);
235 igraph_vector_init(&cut, 0);
236 igraph_vector_init(&partition, 0);
237 igraph_vector_init(&partition2, 0);
238 igraph_vector_init(&flow, 0);
239
240 igraph_maxflow(&g, &flow_value, &flow, &cut, &partition, &partition2,
241 /*source=*/ 0, /*target=*/ 2, &capacity, &stats);
242
243 if ( (check = check_flow(40, &g, flow_value, &flow, &cut, &partition,
244 &partition2, 0, 2, &capacity,
245 /*print=*/ 1))) {
246 return check;
247 }
248
249 igraph_vector_destroy(&cut);
250 igraph_vector_destroy(&partition2);
251 igraph_vector_destroy(&partition);
252 igraph_vector_destroy(&capacity);
253 igraph_vector_destroy(&flow);
254 igraph_destroy(&g);
255
256 return 0;
257 }
258