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
48using namespace boost;
49
50template < typename Graph, typename CapacityMap, typename ReverseEdgeMap >
51std::pair< typename graph_traits< Graph >::vertex_descriptor,
52 typename graph_traits< Graph >::vertex_descriptor >
53fill_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
106long 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
131long 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
163template < typename EdgeDescriptor > struct Node
164{
165 boost::default_color_type vertex_color;
166 long vertex_distance;
167 EdgeDescriptor vertex_predecessor;
168};
169
170template < typename EdgeDescriptor > struct Link
171{
172 long edge_capacity;
173 long edge_residual_capacity;
174 EdgeDescriptor edge_reverse;
175};
176
177long 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
211long 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
247template < class Graph, class EdgeCapacityMap, class ResidualCapacityEdgeMap,
248 class ReverseEdgeMap, class PredecessorMap, class ColorMap,
249 class DistanceMap, class IndexMap >
250class 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
269public:
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
446long 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
481int 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

source code of boost/libs/graph/test/boykov_kolmogorov_max_flow_test.cpp