1 | //======================================================================= |
2 | // Copyright 2013 University of Warsaw. |
3 | // Authors: Piotr Wygocki |
4 | // |
5 | // Distributed under the Boost Software License, Version 1.0. (See |
6 | // accompanying file LICENSE_1_0.txt or copy at |
7 | // http://www.boost.org/LICENSE_1_0.txt) |
8 | //======================================================================= |
9 | |
10 | #include <boost/core/lightweight_test.hpp> |
11 | |
12 | #include <boost/graph/cycle_canceling.hpp> |
13 | #include <boost/graph/edmonds_karp_max_flow.hpp> |
14 | |
15 | #include "min_cost_max_flow_utils.hpp" |
16 | |
17 | void cycle_canceling_def_test() |
18 | { |
19 | boost::SampleGraph::vertex_descriptor s, t; |
20 | boost::SampleGraph::Graph g; |
21 | boost::SampleGraph::getSampleGraph(g, s, t); |
22 | |
23 | boost::edmonds_karp_max_flow(g, src: s, sink: t); |
24 | boost::cycle_canceling(g); |
25 | |
26 | int cost = boost::find_flow_cost(g); |
27 | BOOST_TEST_EQ(cost, 29); |
28 | } |
29 | |
30 | void path_augmentation_def_test2() |
31 | { |
32 | boost::SampleGraph::vertex_descriptor s, t; |
33 | boost::SampleGraph::Graph g; |
34 | boost::SampleGraph::getSampleGraph2(g, s, t); |
35 | |
36 | boost::edmonds_karp_max_flow(g, src: s, sink: t); |
37 | boost::cycle_canceling(g); |
38 | |
39 | int cost = boost::find_flow_cost(g); |
40 | BOOST_TEST_EQ(cost, 7); |
41 | } |
42 | |
43 | void cycle_canceling_test() |
44 | { |
45 | boost::SampleGraph::vertex_descriptor s, t; |
46 | typedef boost::SampleGraph::Graph Graph; |
47 | boost::SampleGraph::Graph g; |
48 | boost::SampleGraph::getSampleGraph(g, s, t); |
49 | |
50 | int N = num_vertices(g_: g); |
51 | std::vector< int > dist(N); |
52 | typedef boost::graph_traits< Graph >::edge_descriptor edge_descriptor; |
53 | std::vector< edge_descriptor > pred(N); |
54 | |
55 | boost::property_map< Graph, boost::vertex_index_t >::const_type idx |
56 | = get(p: boost::vertex_index, g); |
57 | |
58 | boost::edmonds_karp_max_flow(g, src: s, sink: t); |
59 | boost::cycle_canceling(g, |
60 | params: boost::distance_map( |
61 | p: boost::make_iterator_property_map(iter: dist.begin(), id: idx)) |
62 | .predecessor_map( |
63 | p: boost::make_iterator_property_map(iter: pred.begin(), id: idx)) |
64 | .vertex_index_map(p: idx)); |
65 | |
66 | int cost = boost::find_flow_cost(g); |
67 | BOOST_TEST_EQ(cost, 29); |
68 | } |
69 | |
70 | int main() |
71 | { |
72 | cycle_canceling_def_test(); |
73 | path_augmentation_def_test2(); |
74 | cycle_canceling_test(); |
75 | return boost::report_errors(); |
76 | } |
77 | |