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 | // three max_flows we test here |
40 | #include <boost/graph/boykov_kolmogorov_max_flow.hpp> |
41 | #include <boost/graph/push_relabel_max_flow.hpp> |
42 | #include <boost/graph/edmonds_karp_max_flow.hpp> |
43 | // boost utilities we use |
44 | #include <boost/graph/adjacency_list.hpp> |
45 | #include <boost/graph/random.hpp> |
46 | #include <boost/property_map/property_map.hpp> |
47 | #include <boost/random/linear_congruential.hpp> |
48 | #include <boost/lexical_cast.hpp> |
49 | |
50 | /*************** |
51 | * test which compares results of the three different max_flow implementations |
52 | * command line parameters: |
53 | * number_of_vertices: defaults to 100 |
54 | * number_of_edges: defaults to 1000 |
55 | * seeed: defaults to 1 |
56 | ***************/ |
57 | |
58 | using namespace boost; |
59 | |
60 | int main(int argc, char* argv[]) |
61 | { |
62 | |
63 | typedef adjacency_list_traits< vecS, vecS, directedS > Traits; |
64 | typedef adjacency_list< vecS, vecS, directedS, |
65 | property< vertex_index_t, long, |
66 | property< vertex_color_t, boost::default_color_type, |
67 | property< vertex_distance_t, long, |
68 | property< vertex_predecessor_t, |
69 | Traits::edge_descriptor > > > >, |
70 | property< edge_capacity_t, long, |
71 | property< edge_residual_capacity_t, long, |
72 | property< edge_reverse_t, Traits::edge_descriptor > > > > |
73 | Graph; |
74 | |
75 | typedef graph_traits< Graph >::edge_descriptor tEdge; |
76 | typedef graph_traits< Graph >::vertex_descriptor tVertex; |
77 | |
78 | graph_traits< Graph >::vertices_size_type n_verts = 100; |
79 | graph_traits< Graph >::edges_size_type n_edges = 1000; |
80 | std::size_t seed = 1; |
81 | |
82 | if (argc > 1) |
83 | n_verts = lexical_cast< std::size_t >(arg: argv[1]); |
84 | if (argc > 2) |
85 | n_edges = lexical_cast< std::size_t >(arg: argv[2]); |
86 | if (argc > 3) |
87 | seed = lexical_cast< std::size_t >(arg: argv[3]); |
88 | |
89 | Graph g; |
90 | const int cap_low = 1; |
91 | const int cap_high = 1000; |
92 | |
93 | // init random numer generator |
94 | minstd_rand gen(seed); |
95 | // generate graph |
96 | generate_random_graph(g, V: n_verts, E: n_edges, gen); |
97 | |
98 | // init an uniform distribution int generator |
99 | typedef variate_generator< minstd_rand, uniform_int< int > > tIntGen; |
100 | tIntGen int_gen(gen, uniform_int< int >(cap_low, cap_high)); |
101 | // init edge-capacities |
102 | randomize_property< edge_capacity_t, Graph, tIntGen >(g, rg&: int_gen); |
103 | |
104 | // get source and sink node |
105 | tVertex source_vertex = random_vertex(g, gen); |
106 | tVertex sink_vertex = graph_traits< Graph >::null_vertex(); |
107 | while (sink_vertex == graph_traits< Graph >::null_vertex() |
108 | || sink_vertex == source_vertex) |
109 | sink_vertex = random_vertex(g, gen); |
110 | |
111 | // add reverse edges (ugly... how to do better?!) |
112 | property_map< Graph, edge_reverse_t >::type rev = get(p: edge_reverse, g); |
113 | property_map< Graph, edge_capacity_t >::type cap = get(p: edge_capacity, g); |
114 | std::list< tEdge > edges_copy; |
115 | graph_traits< Graph >::edge_iterator ei, e_end; |
116 | boost::tie(t0&: ei, t1&: e_end) = edges(g_: g); |
117 | std::copy( |
118 | first: ei, last: e_end, result: std::back_insert_iterator< std::list< tEdge > >(edges_copy)); |
119 | while (!edges_copy.empty()) |
120 | { |
121 | tEdge old_edge = edges_copy.front(); |
122 | edges_copy.pop_front(); |
123 | tVertex source_vertex = target(e: old_edge, g); |
124 | tVertex target_vertex = source(e: old_edge, g); |
125 | bool inserted; |
126 | tEdge new_edge; |
127 | boost::tie(t0&: new_edge, t1&: inserted) |
128 | = add_edge(u: source_vertex, v: target_vertex, g_&: g); |
129 | assert(inserted); |
130 | rev[old_edge] = new_edge; |
131 | rev[new_edge] = old_edge; |
132 | cap[new_edge] = 0; |
133 | } |
134 | |
135 | typedef property_traits< property_map< Graph, |
136 | edge_capacity_t >::const_type >::value_type tEdgeVal; |
137 | |
138 | tEdgeVal bk = boykov_kolmogorov_max_flow(g, src: source_vertex, sink: sink_vertex); |
139 | tEdgeVal push_relabel |
140 | = push_relabel_max_flow(g, src: source_vertex, sink: sink_vertex); |
141 | tEdgeVal edmonds_karp |
142 | = edmonds_karp_max_flow(g, src: source_vertex, sink: sink_vertex); |
143 | |
144 | BOOST_TEST(bk == push_relabel); |
145 | BOOST_TEST(push_relabel == edmonds_karp); |
146 | |
147 | return boost::report_errors(); |
148 | } |
149 | |