1 | // Copyright (c) 2006, Stephan Diederich |
2 | // |
3 | // This code may be used under either of the following two licences: |
4 | // |
5 | // Permission is hereby granted, free of charge, to any person |
6 | // obtaining a copy of this software and associated documentation |
7 | // files (the "Software"), to deal in the Software without |
8 | // restriction, including without limitation the rights to use, |
9 | // copy, modify, merge, publish, distribute, sublicense, and/or |
10 | // sell copies of the Software, and to permit persons to whom the |
11 | // Software is furnished to do so, subject to the following |
12 | // conditions: |
13 | // |
14 | // The above copyright notice and this permission notice shall be |
15 | // included in all copies or substantial portions of the Software. |
16 | // |
17 | // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, |
18 | // EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES |
19 | // OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND |
20 | // NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT |
21 | // HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, |
22 | // WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING |
23 | // FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR |
24 | // OTHER DEALINGS IN THE SOFTWARE. OF SUCH DAMAGE. |
25 | // |
26 | // Or: |
27 | // |
28 | // Distributed under the Boost Software License, Version 1.0. |
29 | // (See accompanying file LICENSE_1_0.txt or copy at |
30 | // http://www.boost.org/LICENSE_1_0.txt) |
31 | |
32 | #include <vector> |
33 | #include <iterator> |
34 | #include <iostream> |
35 | #include <algorithm> |
36 | #include <fstream> |
37 | |
38 | #include <boost/core/lightweight_test.hpp> |
39 | #include <boost/graph/boykov_kolmogorov_max_flow.hpp> |
40 | |
41 | #include <boost/graph/adjacency_list.hpp> |
42 | #include <boost/graph/adjacency_matrix.hpp> |
43 | #include <boost/graph/random.hpp> |
44 | #include <boost/property_map/property_map.hpp> |
45 | #include <boost/random/linear_congruential.hpp> |
46 | #include <boost/lexical_cast.hpp> |
47 | |
48 | using namespace boost; |
49 | |
50 | template < typename Graph, typename CapacityMap, typename ReverseEdgeMap > |
51 | std::pair< typename graph_traits< Graph >::vertex_descriptor, |
52 | typename graph_traits< Graph >::vertex_descriptor > |
53 | fill_random_max_flow_graph(Graph& g, CapacityMap cap, ReverseEdgeMap rev, |
54 | typename graph_traits< Graph >::vertices_size_type n_verts, |
55 | typename graph_traits< Graph >::edges_size_type n_edges, std::size_t seed) |
56 | { |
57 | typedef typename graph_traits< Graph >::edge_descriptor edge_descriptor; |
58 | typedef typename graph_traits< Graph >::vertex_descriptor vertex_descriptor; |
59 | const int cap_low = 1; |
60 | const int cap_high = 1000; |
61 | |
62 | // init random numer generator |
63 | minstd_rand gen(seed); |
64 | // generate graph |
65 | generate_random_graph(g, n_verts, n_edges, gen); |
66 | |
67 | // init an uniform distribution int generator |
68 | typedef variate_generator< minstd_rand, uniform_int< int > > tIntGen; |
69 | tIntGen int_gen(gen, uniform_int< int >(cap_low, cap_high)); |
70 | // randomize edge-capacities |
71 | // randomize_property<edge_capacity, Graph, tIntGen> (g,int_gen); //we |
72 | // cannot use this, as we have no idea how properties are stored, right? |
73 | typename graph_traits< Graph >::edge_iterator ei, e_end; |
74 | for (boost::tie(ei, e_end) = edges(g); ei != e_end; ++ei) |
75 | put(cap, *ei, int_gen()); |
76 | |
77 | // get source and sink node |
78 | vertex_descriptor s = random_vertex(g, gen); |
79 | vertex_descriptor t = graph_traits< Graph >::null_vertex(); |
80 | while (t == graph_traits< Graph >::null_vertex() || t == s) |
81 | t = random_vertex(g, gen); |
82 | |
83 | // add reverse edges (ugly... how to do better?!) |
84 | std::list< edge_descriptor > edges_copy; |
85 | boost::tie(ei, e_end) = edges(g); |
86 | std::copy(ei, e_end, |
87 | std::back_insert_iterator< std::list< edge_descriptor > >(edges_copy)); |
88 | while (!edges_copy.empty()) |
89 | { |
90 | edge_descriptor old_edge = edges_copy.front(); |
91 | edges_copy.pop_front(); |
92 | vertex_descriptor source_vertex = target(old_edge, g); |
93 | vertex_descriptor target_vertex = source(old_edge, g); |
94 | bool inserted; |
95 | edge_descriptor new_edge; |
96 | boost::tie(new_edge, inserted) |
97 | = add_edge(source_vertex, target_vertex, g); |
98 | assert(inserted); |
99 | put(rev, old_edge, new_edge); |
100 | put(rev, new_edge, old_edge); |
101 | put(cap, new_edge, 0); |
102 | } |
103 | return std::make_pair(s, t); |
104 | } |
105 | |
106 | long test_adjacency_list_vecS(int n_verts, int n_edges, std::size_t seed) |
107 | { |
108 | typedef adjacency_list_traits< vecS, vecS, directedS > tVectorTraits; |
109 | typedef adjacency_list< vecS, vecS, directedS, |
110 | property< vertex_index_t, long, |
111 | property< vertex_predecessor_t, tVectorTraits::edge_descriptor, |
112 | property< vertex_color_t, boost::default_color_type, |
113 | property< vertex_distance_t, long > > > >, |
114 | property< edge_capacity_t, long, |
115 | property< edge_residual_capacity_t, long, |
116 | property< edge_reverse_t, tVectorTraits::edge_descriptor > > > > |
117 | tVectorGraph; |
118 | |
119 | tVectorGraph g; |
120 | |
121 | graph_traits< tVectorGraph >::vertex_descriptor src, sink; |
122 | boost::tie(t0&: src, t1&: sink) = fill_random_max_flow_graph( |
123 | g, cap: get(p: edge_capacity, g), rev: get(p: edge_reverse, g), n_verts, n_edges, seed); |
124 | |
125 | return boykov_kolmogorov_max_flow(g, cap: get(p: edge_capacity, g), |
126 | res_cap: get(p: edge_residual_capacity, g), rev_map: get(p: edge_reverse, g), |
127 | pre_map: get(p: vertex_predecessor, g), color: get(p: vertex_color, g), |
128 | dist: get(p: vertex_distance, g), idx: get(p: vertex_index, g), src, sink); |
129 | } |
130 | |
131 | long test_adjacency_list_listS(int n_verts, int n_edges, std::size_t seed) |
132 | { |
133 | typedef adjacency_list_traits< listS, listS, directedS > tListTraits; |
134 | typedef adjacency_list< listS, listS, directedS, |
135 | property< vertex_index_t, long, |
136 | property< vertex_predecessor_t, tListTraits::edge_descriptor, |
137 | property< vertex_color_t, boost::default_color_type, |
138 | property< vertex_distance_t, long > > > >, |
139 | property< edge_capacity_t, long, |
140 | property< edge_residual_capacity_t, long, |
141 | property< edge_reverse_t, tListTraits::edge_descriptor > > > > |
142 | tListGraph; |
143 | |
144 | tListGraph g; |
145 | |
146 | graph_traits< tListGraph >::vertex_descriptor src, sink; |
147 | boost::tie(t0&: src, t1&: sink) = fill_random_max_flow_graph( |
148 | g, cap: get(p: edge_capacity, g), rev: get(p: edge_reverse, g), n_verts, n_edges, seed); |
149 | |
150 | // initialize vertex indices |
151 | graph_traits< tListGraph >::vertex_iterator vi, v_end; |
152 | graph_traits< tListGraph >::vertices_size_type index = 0; |
153 | for (boost::tie(t0&: vi, t1&: v_end) = vertices(g_: g); vi != v_end; ++vi) |
154 | { |
155 | put(p: vertex_index, g, key: *vi, value: index++); |
156 | } |
157 | return boykov_kolmogorov_max_flow(g, cap: get(p: edge_capacity, g), |
158 | res_cap: get(p: edge_residual_capacity, g), rev_map: get(p: edge_reverse, g), |
159 | pre_map: get(p: vertex_predecessor, g), color: get(p: vertex_color, g), |
160 | dist: get(p: vertex_distance, g), idx: get(p: vertex_index, g), src, sink); |
161 | } |
162 | |
163 | template < typename EdgeDescriptor > struct Node |
164 | { |
165 | boost::default_color_type vertex_color; |
166 | long vertex_distance; |
167 | EdgeDescriptor vertex_predecessor; |
168 | }; |
169 | |
170 | template < typename EdgeDescriptor > struct Link |
171 | { |
172 | long edge_capacity; |
173 | long edge_residual_capacity; |
174 | EdgeDescriptor edge_reverse; |
175 | }; |
176 | |
177 | long test_bundled_properties(int n_verts, int n_edges, std::size_t seed) |
178 | { |
179 | typedef adjacency_list_traits< vecS, vecS, directedS > tTraits; |
180 | typedef Node< tTraits::edge_descriptor > tVertex; |
181 | typedef Link< tTraits::edge_descriptor > tEdge; |
182 | typedef adjacency_list< vecS, vecS, directedS, tVertex, tEdge > |
183 | tBundleGraph; |
184 | |
185 | tBundleGraph g; |
186 | |
187 | graph_traits< tBundleGraph >::vertex_descriptor src, sink; |
188 | boost::tie(t0&: src, t1&: sink) |
189 | = fill_random_max_flow_graph(g, cap: get(p: &tEdge::edge_capacity, g), |
190 | rev: get(p: &tEdge::edge_reverse, g), n_verts, n_edges, seed); |
191 | |
192 | long flow_unnamed_overload = boykov_kolmogorov_max_flow(g, |
193 | cap: get(p: &tEdge::edge_capacity, g), res_cap: get(p: &tEdge::edge_residual_capacity, g), |
194 | rev_map: get(p: &tEdge::edge_reverse, g), pre_map: get(p: &tVertex::vertex_predecessor, g), |
195 | color: get(p: &tVertex::vertex_color, g), dist: get(p: &tVertex::vertex_distance, g), |
196 | idx: get(p: vertex_index, g), src, sink); |
197 | |
198 | long flow_named_overload = boykov_kolmogorov_max_flow(g, src, sink, |
199 | params: capacity_map(p: get(p: &tEdge::edge_capacity, g)) |
200 | .residual_capacity_map(p: get(p: &tEdge::edge_residual_capacity, g)) |
201 | .reverse_edge_map(p: get(p: &tEdge::edge_reverse, g)) |
202 | .predecessor_map(p: get(p: &tVertex::vertex_predecessor, g)) |
203 | .color_map(p: get(p: &tVertex::vertex_color, g)) |
204 | .distance_map(p: get(p: &tVertex::vertex_distance, g)) |
205 | .vertex_index_map(p: get(p: vertex_index, g))); |
206 | |
207 | BOOST_TEST(flow_unnamed_overload == flow_named_overload); |
208 | return flow_named_overload; |
209 | } |
210 | |
211 | long test_overloads(int n_verts, int n_edges, std::size_t seed) |
212 | { |
213 | typedef adjacency_list_traits< vecS, vecS, directedS > tTraits; |
214 | typedef property< edge_capacity_t, long, |
215 | property< edge_residual_capacity_t, long, |
216 | property< edge_reverse_t, tTraits::edge_descriptor > > > |
217 | tEdgeProperty; |
218 | typedef adjacency_list< vecS, vecS, directedS, no_property, tEdgeProperty > |
219 | tGraph; |
220 | |
221 | tGraph g; |
222 | |
223 | graph_traits< tGraph >::vertex_descriptor src, sink; |
224 | boost::tie(t0&: src, t1&: sink) = fill_random_max_flow_graph( |
225 | g, cap: get(p: edge_capacity, g), rev: get(p: edge_reverse, g), n_verts, n_edges, seed); |
226 | |
227 | std::vector< graph_traits< tGraph >::edge_descriptor > predecessor_vec( |
228 | n_verts); |
229 | std::vector< default_color_type > color_vec(n_verts); |
230 | std::vector< graph_traits< tGraph >::vertices_size_type > distance_vec( |
231 | n_verts); |
232 | |
233 | long flow_overload_1 = boykov_kolmogorov_max_flow(g, cap: get(p: edge_capacity, g), |
234 | res_cap: get(p: edge_residual_capacity, g), rev: get(p: edge_reverse, g), |
235 | idx: get(p: vertex_index, g), src, sink); |
236 | |
237 | long flow_overload_2 = boykov_kolmogorov_max_flow(g, cap: get(p: edge_capacity, g), |
238 | res_cap: get(p: edge_residual_capacity, g), rev: get(p: edge_reverse, g), |
239 | color: boost::make_iterator_property_map( |
240 | iter: color_vec.begin(), id: get(p: vertex_index, g)), |
241 | idx: get(p: vertex_index, g), src, sink); |
242 | |
243 | BOOST_TEST(flow_overload_1 == flow_overload_2); |
244 | return flow_overload_1; |
245 | } |
246 | |
247 | template < class Graph, class EdgeCapacityMap, class ResidualCapacityEdgeMap, |
248 | class ReverseEdgeMap, class PredecessorMap, class ColorMap, |
249 | class DistanceMap, class IndexMap > |
250 | class boykov_kolmogorov_test |
251 | : public detail::bk_max_flow< Graph, EdgeCapacityMap, ResidualCapacityEdgeMap, |
252 | ReverseEdgeMap, PredecessorMap, ColorMap, DistanceMap, IndexMap > |
253 | { |
254 | |
255 | typedef typename graph_traits< Graph >::edge_descriptor tEdge; |
256 | typedef typename graph_traits< Graph >::vertex_descriptor tVertex; |
257 | typedef typename property_traits< typename property_map< Graph, |
258 | edge_capacity_t >::const_type >::value_type tEdgeVal; |
259 | typedef typename graph_traits< Graph >::vertex_iterator tVertexIterator; |
260 | typedef typename graph_traits< Graph >::out_edge_iterator tOutEdgeIterator; |
261 | typedef typename property_traits< ColorMap >::value_type tColorValue; |
262 | typedef color_traits< tColorValue > tColorTraits; |
263 | typedef typename property_traits< DistanceMap >::value_type tDistanceVal; |
264 | typedef typename detail::bk_max_flow< Graph, EdgeCapacityMap, |
265 | ResidualCapacityEdgeMap, ReverseEdgeMap, PredecessorMap, ColorMap, |
266 | DistanceMap, IndexMap > |
267 | tSuper; |
268 | |
269 | public: |
270 | boykov_kolmogorov_test(Graph& g, |
271 | typename graph_traits< Graph >::vertex_descriptor src, |
272 | typename graph_traits< Graph >::vertex_descriptor sink) |
273 | : tSuper(g, get(edge_capacity, g), get(edge_residual_capacity, g), |
274 | get(edge_reverse, g), get(vertex_predecessor, g), get(vertex_color, g), |
275 | get(vertex_distance, g), get(vertex_index, g), src, sink) |
276 | { |
277 | } |
278 | |
279 | void invariant_four(tVertex v) const |
280 | { |
281 | // passive nodes in S or T |
282 | if (v == tSuper::m_source || v == tSuper::m_sink) |
283 | return; |
284 | typename std::list< tVertex >::const_iterator it |
285 | = find(tSuper::m_orphans.begin(), tSuper::m_orphans.end(), v); |
286 | // a node is active, if its in the active_list AND (is has_a_parent, or |
287 | // its already in the orphans_list or its the sink, or its the source) |
288 | bool is_active = (tSuper::m_in_active_list_map[v] |
289 | && (tSuper::has_parent(v) || it != tSuper::m_orphans.end())); |
290 | if (this->get_tree(v) != tColorTraits::gray() && !is_active) |
291 | { |
292 | typename graph_traits< Graph >::out_edge_iterator ei, e_end; |
293 | for (boost::tie(ei, e_end) = out_edges(v, tSuper::m_g); ei != e_end; |
294 | ++ei) |
295 | { |
296 | const tVertex& other_node = target(*ei, tSuper::m_g); |
297 | if (this->get_tree(other_node) != this->get_tree(v)) |
298 | { |
299 | if (this->get_tree(v) == tColorTraits::black()) |
300 | BOOST_TEST(tSuper::m_res_cap_map[*ei] == 0); |
301 | else |
302 | BOOST_TEST( |
303 | tSuper::m_res_cap_map[tSuper::m_rev_edge_map[*ei]] |
304 | == 0); |
305 | } |
306 | } |
307 | } |
308 | } |
309 | |
310 | void invariant_five(const tVertex& v) const |
311 | { |
312 | BOOST_TEST(this->get_tree(v) != tColorTraits::gray() |
313 | || tSuper::m_time_map[v] <= tSuper::m_time); |
314 | } |
315 | |
316 | void invariant_six(const tVertex& v) const |
317 | { |
318 | if (this->get_tree(v) == tColorTraits::gray() |
319 | || tSuper::m_time_map[v] != tSuper::m_time) |
320 | return; |
321 | else |
322 | { |
323 | tVertex current_node = v; |
324 | tDistanceVal distance = 0; |
325 | tColorValue color = this->get_tree(v); |
326 | tVertex terminal = (color == tColorTraits::black()) |
327 | ? tSuper::m_source |
328 | : tSuper::m_sink; |
329 | while (current_node != terminal) |
330 | { |
331 | BOOST_TEST(tSuper::has_parent(current_node)); |
332 | tEdge e = this->get_edge_to_parent(current_node); |
333 | ++distance; |
334 | current_node = (color == tColorTraits::black()) |
335 | ? source(e, tSuper::m_g) |
336 | : target(e, tSuper::m_g); |
337 | if (distance > tSuper::m_dist_map[v]) |
338 | break; |
339 | } |
340 | BOOST_TEST(distance == tSuper::m_dist_map[v]); |
341 | } |
342 | } |
343 | |
344 | void invariant_seven(const tVertex& v) const |
345 | { |
346 | if (this->get_tree(v) == tColorTraits::gray()) |
347 | return; |
348 | else |
349 | { |
350 | tColorValue color = this->get_tree(v); |
351 | long time = tSuper::m_time_map[v]; |
352 | tVertex current_node = v; |
353 | while (tSuper::has_parent(current_node)) |
354 | { |
355 | tEdge e = this->get_edge_to_parent(current_node); |
356 | current_node = (color == tColorTraits::black()) |
357 | ? source(e, tSuper::m_g) |
358 | : target(e, tSuper::m_g); |
359 | BOOST_TEST(tSuper::m_time_map[current_node] >= time); |
360 | } |
361 | } |
362 | } // invariant_seven |
363 | |
364 | void invariant_eight(const tVertex& v) const |
365 | { |
366 | if (this->get_tree(v) == tColorTraits::gray()) |
367 | return; |
368 | else |
369 | { |
370 | tColorValue color = this->get_tree(v); |
371 | long time = tSuper::m_time_map[v]; |
372 | tDistanceVal distance = tSuper::m_dist_map[v]; |
373 | tVertex current_node = v; |
374 | while (tSuper::has_parent(current_node)) |
375 | { |
376 | tEdge e = this->get_edge_to_parent(current_node); |
377 | current_node = (color == tColorTraits::black()) |
378 | ? source(e, tSuper::m_g) |
379 | : target(e, tSuper::m_g); |
380 | if (tSuper::m_time_map[current_node] == time) |
381 | BOOST_TEST(tSuper::m_dist_map[current_node] < distance); |
382 | } |
383 | } |
384 | } // invariant_eight |
385 | |
386 | void check_invariants() |
387 | { |
388 | tVertexIterator vi, v_end; |
389 | for (boost::tie(vi, v_end) = vertices(tSuper::m_g); vi != v_end; ++vi) |
390 | { |
391 | invariant_four(v: *vi); |
392 | invariant_five(v: *vi); |
393 | invariant_six(v: *vi); |
394 | invariant_seven(v: *vi); |
395 | invariant_eight(v: *vi); |
396 | } |
397 | } |
398 | |
399 | tEdgeVal test() |
400 | { |
401 | this->add_active_node(this->m_sink); |
402 | this->augment_direct_paths(); |
403 | check_invariants(); |
404 | // start the main-loop |
405 | while (true) |
406 | { |
407 | bool path_found; |
408 | tEdge connecting_edge; |
409 | boost::tie(connecting_edge, path_found) |
410 | = this->grow(); // find a path from source to sink |
411 | if (!path_found) |
412 | { |
413 | // we're finished, no more paths were found |
414 | break; |
415 | } |
416 | check_invariants(); |
417 | this->m_time++; |
418 | this->augment(connecting_edge); // augment that path |
419 | check_invariants(); |
420 | this->adopt(); // rebuild search tree structure |
421 | check_invariants(); |
422 | } |
423 | |
424 | // check if flow is the sum of outgoing edges of src |
425 | tOutEdgeIterator ei, e_end; |
426 | tEdgeVal src_sum = 0; |
427 | for (boost::tie(ei, e_end) = out_edges(this->m_source, this->m_g); |
428 | ei != e_end; ++ei) |
429 | { |
430 | src_sum += this->m_cap_map[*ei] - this->m_res_cap_map[*ei]; |
431 | } |
432 | BOOST_TEST(this->m_flow == src_sum); |
433 | // check if flow is the sum of ingoing edges of sink |
434 | tEdgeVal sink_sum = 0; |
435 | for (boost::tie(ei, e_end) = out_edges(this->m_sink, this->m_g); |
436 | ei != e_end; ++ei) |
437 | { |
438 | tEdge in_edge = this->m_rev_edge_map[*ei]; |
439 | sink_sum += this->m_cap_map[in_edge] - this->m_res_cap_map[in_edge]; |
440 | } |
441 | BOOST_TEST(this->m_flow == sink_sum); |
442 | return this->m_flow; |
443 | } |
444 | }; |
445 | |
446 | long test_algorithms_invariant(int n_verts, int n_edges, std::size_t seed) |
447 | { |
448 | typedef adjacency_list_traits< vecS, vecS, directedS > tVectorTraits; |
449 | typedef adjacency_list< vecS, vecS, directedS, |
450 | property< vertex_index_t, long, |
451 | property< vertex_predecessor_t, tVectorTraits::edge_descriptor, |
452 | property< vertex_color_t, default_color_type, |
453 | property< vertex_distance_t, long > > > >, |
454 | property< edge_capacity_t, long, |
455 | property< edge_residual_capacity_t, long, |
456 | property< edge_reverse_t, tVectorTraits::edge_descriptor > > > > |
457 | tVectorGraph; |
458 | |
459 | tVectorGraph g; |
460 | |
461 | graph_traits< tVectorGraph >::vertex_descriptor src, sink; |
462 | boost::tie(t0&: src, t1&: sink) = fill_random_max_flow_graph( |
463 | g, cap: get(p: edge_capacity, g), rev: get(p: edge_reverse, g), n_verts, n_edges, seed); |
464 | |
465 | typedef property_map< tVectorGraph, edge_capacity_t >::type tEdgeCapMap; |
466 | typedef property_map< tVectorGraph, edge_residual_capacity_t >::type |
467 | tEdgeResCapMap; |
468 | typedef property_map< tVectorGraph, edge_reverse_t >::type tRevEdgeMap; |
469 | typedef property_map< tVectorGraph, vertex_predecessor_t >::type |
470 | tVertexPredMap; |
471 | typedef property_map< tVectorGraph, vertex_color_t >::type tVertexColorMap; |
472 | typedef property_map< tVectorGraph, vertex_distance_t >::type tDistanceMap; |
473 | typedef property_map< tVectorGraph, vertex_index_t >::type tIndexMap; |
474 | typedef boykov_kolmogorov_test< tVectorGraph, tEdgeCapMap, tEdgeResCapMap, |
475 | tRevEdgeMap, tVertexPredMap, tVertexColorMap, tDistanceMap, tIndexMap > |
476 | tKolmo; |
477 | tKolmo instance(g, src, sink); |
478 | return instance.test(); |
479 | } |
480 | |
481 | int main(int argc, char* argv[]) |
482 | { |
483 | int n_verts = 10; |
484 | int n_edges = 500; |
485 | std::size_t seed = 1; |
486 | |
487 | if (argc > 1) |
488 | n_verts = lexical_cast< int >(arg: argv[1]); |
489 | if (argc > 2) |
490 | n_edges = lexical_cast< int >(arg: argv[2]); |
491 | if (argc > 3) |
492 | seed = lexical_cast< std::size_t >(arg: argv[3]); |
493 | |
494 | // we need at least 2 vertices to create src and sink in random graphs |
495 | // this case is also caught in boykov_kolmogorov_max_flow |
496 | if (n_verts < 2) |
497 | n_verts = 2; |
498 | |
499 | // below are checks for different calls to boykov_kolmogorov_max_flow and |
500 | // different graph-types |
501 | |
502 | // checks support of vecS storage |
503 | long flow_vecS = test_adjacency_list_vecS(n_verts, n_edges, seed); |
504 | std::cout << "vecS flow: " << flow_vecS << std::endl; |
505 | // checks support of listS storage (especially problems with vertex indices) |
506 | long flow_listS = test_adjacency_list_listS(n_verts, n_edges, seed); |
507 | std::cout << "listS flow: " << flow_listS << std::endl; |
508 | BOOST_TEST(flow_vecS == flow_listS); |
509 | // checks bundled properties |
510 | long flow_bundles = test_bundled_properties(n_verts, n_edges, seed); |
511 | std::cout << "bundles flow: " << flow_bundles << std::endl; |
512 | BOOST_TEST(flow_listS == flow_bundles); |
513 | // checks overloads |
514 | long flow_overloads = test_overloads(n_verts, n_edges, seed); |
515 | std::cout << "overloads flow: " << flow_overloads << std::endl; |
516 | BOOST_TEST(flow_bundles == flow_overloads); |
517 | |
518 | // excessive test version where Boykov-Kolmogorov's algorithm invariants are |
519 | // checked |
520 | long flow_invariants = test_algorithms_invariant(n_verts, n_edges, seed); |
521 | std::cout << "invariants flow: " << flow_invariants << std::endl; |
522 | BOOST_TEST(flow_overloads == flow_invariants); |
523 | return boost::report_errors(); |
524 | } |
525 | |