]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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 | ||
f67539c2 | 38 | #include <boost/core/lightweight_test.hpp> |
7c673cae FG |
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 | ||
f67539c2 TL |
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) | |
7c673cae | 56 | { |
f67539c2 TL |
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 | 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 | rev[old_edge] = new_edge; | |
100 | rev[new_edge] = old_edge; | |
101 | cap[new_edge] = 0; | |
102 | } | |
103 | return std::make_pair(s, t); | |
7c673cae FG |
104 | } |
105 | ||
f67539c2 TL |
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(src, sink) = fill_random_max_flow_graph( | |
123 | g, get(edge_capacity, g), get(edge_reverse, g), n_verts, n_edges, seed); | |
124 | ||
125 | return boykov_kolmogorov_max_flow(g, get(edge_capacity, g), | |
126 | get(edge_residual_capacity, g), get(edge_reverse, g), | |
127 | get(vertex_predecessor, g), get(vertex_color, g), | |
128 | get(vertex_distance, g), get(vertex_index, g), src, sink); | |
7c673cae FG |
129 | } |
130 | ||
f67539c2 TL |
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(src, sink) = fill_random_max_flow_graph( | |
148 | g, get(edge_capacity, g), get(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(vi, v_end) = vertices(g); vi != v_end; ++vi) | |
154 | { | |
155 | put(vertex_index, g, *vi, index++); | |
156 | } | |
157 | return boykov_kolmogorov_max_flow(g, get(edge_capacity, g), | |
158 | get(edge_residual_capacity, g), get(edge_reverse, g), | |
159 | get(vertex_predecessor, g), get(vertex_color, g), | |
160 | get(vertex_distance, g), get(vertex_index, g), src, sink); | |
7c673cae FG |
161 | } |
162 | ||
f67539c2 TL |
163 | template < typename EdgeDescriptor > struct Node |
164 | { | |
165 | boost::default_color_type vertex_color; | |
166 | long vertex_distance; | |
167 | EdgeDescriptor vertex_predecessor; | |
7c673cae FG |
168 | }; |
169 | ||
f67539c2 TL |
170 | template < typename EdgeDescriptor > struct Link |
171 | { | |
172 | long edge_capacity; | |
173 | long edge_residual_capacity; | |
174 | EdgeDescriptor edge_reverse; | |
7c673cae FG |
175 | }; |
176 | ||
f67539c2 TL |
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(src, sink) | |
189 | = fill_random_max_flow_graph(g, get(&tEdge::edge_capacity, g), | |
190 | get(&tEdge::edge_reverse, g), n_verts, n_edges, seed); | |
191 | return boykov_kolmogorov_max_flow(g, get(&tEdge::edge_capacity, g), | |
192 | get(&tEdge::edge_residual_capacity, g), get(&tEdge::edge_reverse, g), | |
193 | get(&tVertex::vertex_predecessor, g), get(&tVertex::vertex_color, g), | |
194 | get(&tVertex::vertex_distance, g), get(vertex_index, g), src, sink); | |
7c673cae FG |
195 | } |
196 | ||
f67539c2 TL |
197 | long test_overloads(int n_verts, int n_edges, std::size_t seed) |
198 | { | |
199 | typedef adjacency_list_traits< vecS, vecS, directedS > tTraits; | |
200 | typedef property< edge_capacity_t, long, | |
201 | property< edge_residual_capacity_t, long, | |
202 | property< edge_reverse_t, tTraits::edge_descriptor > > > | |
203 | tEdgeProperty; | |
204 | typedef adjacency_list< vecS, vecS, directedS, no_property, tEdgeProperty > | |
205 | tGraph; | |
206 | ||
207 | tGraph g; | |
208 | ||
209 | graph_traits< tGraph >::vertex_descriptor src, sink; | |
210 | boost::tie(src, sink) = fill_random_max_flow_graph( | |
211 | g, get(edge_capacity, g), get(edge_reverse, g), n_verts, n_edges, seed); | |
212 | ||
213 | std::vector< graph_traits< tGraph >::edge_descriptor > predecessor_vec( | |
214 | n_verts); | |
215 | std::vector< default_color_type > color_vec(n_verts); | |
216 | std::vector< graph_traits< tGraph >::vertices_size_type > distance_vec( | |
217 | n_verts); | |
218 | ||
219 | long flow_overload_1 = boykov_kolmogorov_max_flow(g, get(edge_capacity, g), | |
220 | get(edge_residual_capacity, g), get(edge_reverse, g), | |
221 | get(vertex_index, g), src, sink); | |
222 | ||
223 | long flow_overload_2 = boykov_kolmogorov_max_flow(g, get(edge_capacity, g), | |
224 | get(edge_residual_capacity, g), get(edge_reverse, g), | |
225 | boost::make_iterator_property_map( | |
226 | color_vec.begin(), get(vertex_index, g)), | |
227 | get(vertex_index, g), src, sink); | |
228 | ||
229 | BOOST_TEST(flow_overload_1 == flow_overload_2); | |
230 | return flow_overload_1; | |
7c673cae FG |
231 | } |
232 | ||
f67539c2 TL |
233 | template < class Graph, class EdgeCapacityMap, class ResidualCapacityEdgeMap, |
234 | class ReverseEdgeMap, class PredecessorMap, class ColorMap, | |
235 | class DistanceMap, class IndexMap > | |
7c673cae | 236 | class boykov_kolmogorov_test |
f67539c2 TL |
237 | : public detail::bk_max_flow< Graph, EdgeCapacityMap, ResidualCapacityEdgeMap, |
238 | ReverseEdgeMap, PredecessorMap, ColorMap, DistanceMap, IndexMap > | |
7c673cae FG |
239 | { |
240 | ||
f67539c2 TL |
241 | typedef typename graph_traits< Graph >::edge_descriptor tEdge; |
242 | typedef typename graph_traits< Graph >::vertex_descriptor tVertex; | |
243 | typedef typename property_traits< typename property_map< Graph, | |
244 | edge_capacity_t >::const_type >::value_type tEdgeVal; | |
245 | typedef typename graph_traits< Graph >::vertex_iterator tVertexIterator; | |
246 | typedef typename graph_traits< Graph >::out_edge_iterator tOutEdgeIterator; | |
247 | typedef typename property_traits< ColorMap >::value_type tColorValue; | |
248 | typedef color_traits< tColorValue > tColorTraits; | |
249 | typedef typename property_traits< DistanceMap >::value_type tDistanceVal; | |
250 | typedef typename detail::bk_max_flow< Graph, EdgeCapacityMap, | |
251 | ResidualCapacityEdgeMap, ReverseEdgeMap, PredecessorMap, ColorMap, | |
252 | DistanceMap, IndexMap > | |
253 | tSuper; | |
254 | ||
255 | public: | |
256 | boykov_kolmogorov_test(Graph& g, | |
257 | typename graph_traits< Graph >::vertex_descriptor src, | |
258 | typename graph_traits< Graph >::vertex_descriptor sink) | |
259 | : tSuper(g, get(edge_capacity, g), get(edge_residual_capacity, g), | |
260 | get(edge_reverse, g), get(vertex_predecessor, g), get(vertex_color, g), | |
261 | get(vertex_distance, g), get(vertex_index, g), src, sink) | |
262 | { | |
263 | } | |
264 | ||
265 | void invariant_four(tVertex v) const | |
266 | { | |
267 | // passive nodes in S or T | |
268 | if (v == tSuper::m_source || v == tSuper::m_sink) | |
7c673cae | 269 | return; |
f67539c2 TL |
270 | typename std::list< tVertex >::const_iterator it |
271 | = find(tSuper::m_orphans.begin(), tSuper::m_orphans.end(), v); | |
272 | // a node is active, if its in the active_list AND (is has_a_parent, or | |
273 | // its already in the orphans_list or its the sink, or its the source) | |
274 | bool is_active = (tSuper::m_in_active_list_map[v] | |
275 | && (tSuper::has_parent(v) || it != tSuper::m_orphans.end())); | |
276 | if (this->get_tree(v) != tColorTraits::gray() && !is_active) | |
277 | { | |
278 | typename graph_traits< Graph >::out_edge_iterator ei, e_end; | |
279 | for (boost::tie(ei, e_end) = out_edges(v, tSuper::m_g); ei != e_end; | |
280 | ++ei) | |
281 | { | |
282 | const tVertex& other_node = target(*ei, tSuper::m_g); | |
283 | if (this->get_tree(other_node) != this->get_tree(v)) | |
284 | { | |
285 | if (this->get_tree(v) == tColorTraits::black()) | |
286 | BOOST_TEST(tSuper::m_res_cap_map[*ei] == 0); | |
287 | else | |
288 | BOOST_TEST( | |
289 | tSuper::m_res_cap_map[tSuper::m_rev_edge_map[*ei]] | |
290 | == 0); | |
291 | } | |
292 | } | |
7c673cae | 293 | } |
f67539c2 TL |
294 | } |
295 | ||
296 | void invariant_five(const tVertex& v) const | |
297 | { | |
298 | BOOST_TEST(this->get_tree(v) != tColorTraits::gray() | |
299 | || tSuper::m_time_map[v] <= tSuper::m_time); | |
300 | } | |
301 | ||
302 | void invariant_six(const tVertex& v) const | |
303 | { | |
304 | if (this->get_tree(v) == tColorTraits::gray() | |
305 | || tSuper::m_time_map[v] != tSuper::m_time) | |
7c673cae | 306 | return; |
f67539c2 TL |
307 | else |
308 | { | |
7c673cae FG |
309 | tVertex current_node = v; |
310 | tDistanceVal distance = 0; | |
311 | tColorValue color = this->get_tree(v); | |
f67539c2 TL |
312 | tVertex terminal = (color == tColorTraits::black()) |
313 | ? tSuper::m_source | |
314 | : tSuper::m_sink; | |
315 | while (current_node != terminal) | |
316 | { | |
317 | BOOST_TEST(tSuper::has_parent(current_node)); | |
318 | tEdge e = this->get_edge_to_parent(current_node); | |
319 | ++distance; | |
320 | current_node = (color == tColorTraits::black()) | |
321 | ? source(e, tSuper::m_g) | |
322 | : target(e, tSuper::m_g); | |
323 | if (distance > tSuper::m_dist_map[v]) | |
324 | break; | |
7c673cae | 325 | } |
f67539c2 | 326 | BOOST_TEST(distance == tSuper::m_dist_map[v]); |
7c673cae | 327 | } |
f67539c2 | 328 | } |
7c673cae | 329 | |
f67539c2 TL |
330 | void invariant_seven(const tVertex& v) const |
331 | { | |
332 | if (this->get_tree(v) == tColorTraits::gray()) | |
7c673cae | 333 | return; |
f67539c2 TL |
334 | else |
335 | { | |
7c673cae FG |
336 | tColorValue color = this->get_tree(v); |
337 | long time = tSuper::m_time_map[v]; | |
338 | tVertex current_node = v; | |
f67539c2 TL |
339 | while (tSuper::has_parent(current_node)) |
340 | { | |
341 | tEdge e = this->get_edge_to_parent(current_node); | |
342 | current_node = (color == tColorTraits::black()) | |
343 | ? source(e, tSuper::m_g) | |
344 | : target(e, tSuper::m_g); | |
345 | BOOST_TEST(tSuper::m_time_map[current_node] >= time); | |
7c673cae | 346 | } |
f67539c2 TL |
347 | } |
348 | } // invariant_seven | |
7c673cae | 349 | |
f67539c2 TL |
350 | void invariant_eight(const tVertex& v) const |
351 | { | |
352 | if (this->get_tree(v) == tColorTraits::gray()) | |
353 | return; | |
354 | else | |
355 | { | |
7c673cae FG |
356 | tColorValue color = this->get_tree(v); |
357 | long time = tSuper::m_time_map[v]; | |
358 | tDistanceVal distance = tSuper::m_dist_map[v]; | |
359 | tVertex current_node = v; | |
f67539c2 TL |
360 | while (tSuper::has_parent(current_node)) |
361 | { | |
362 | tEdge e = this->get_edge_to_parent(current_node); | |
363 | current_node = (color == tColorTraits::black()) | |
364 | ? source(e, tSuper::m_g) | |
365 | : target(e, tSuper::m_g); | |
366 | if (tSuper::m_time_map[current_node] == time) | |
367 | BOOST_TEST(tSuper::m_dist_map[current_node] < distance); | |
7c673cae | 368 | } |
f67539c2 TL |
369 | } |
370 | } // invariant_eight | |
7c673cae | 371 | |
f67539c2 TL |
372 | void check_invariants() |
373 | { | |
374 | tVertexIterator vi, v_end; | |
375 | for (boost::tie(vi, v_end) = vertices(tSuper::m_g); vi != v_end; ++vi) | |
376 | { | |
7c673cae FG |
377 | invariant_four(*vi); |
378 | invariant_five(*vi); | |
379 | invariant_six(*vi); | |
380 | invariant_seven(*vi); | |
381 | invariant_eight(*vi); | |
7c673cae | 382 | } |
f67539c2 TL |
383 | } |
384 | ||
385 | tEdgeVal test() | |
386 | { | |
387 | this->add_active_node(this->m_sink); | |
388 | this->augment_direct_paths(); | |
389 | check_invariants(); | |
390 | // start the main-loop | |
391 | while (true) | |
392 | { | |
7c673cae FG |
393 | bool path_found; |
394 | tEdge connecting_edge; | |
f67539c2 TL |
395 | boost::tie(connecting_edge, path_found) |
396 | = this->grow(); // find a path from source to sink | |
397 | if (!path_found) | |
398 | { | |
399 | // we're finished, no more paths were found | |
400 | break; | |
7c673cae FG |
401 | } |
402 | check_invariants(); | |
403 | this->m_time++; | |
f67539c2 | 404 | this->augment(connecting_edge); // augment that path |
7c673cae | 405 | check_invariants(); |
f67539c2 | 406 | this->adopt(); // rebuild search tree structure |
7c673cae | 407 | check_invariants(); |
f67539c2 | 408 | } |
7c673cae | 409 | |
f67539c2 TL |
410 | // check if flow is the sum of outgoing edges of src |
411 | tOutEdgeIterator ei, e_end; | |
412 | tEdgeVal src_sum = 0; | |
413 | for (boost::tie(ei, e_end) = out_edges(this->m_source, this->m_g); | |
414 | ei != e_end; ++ei) | |
415 | { | |
7c673cae | 416 | src_sum += this->m_cap_map[*ei] - this->m_res_cap_map[*ei]; |
f67539c2 TL |
417 | } |
418 | BOOST_TEST(this->m_flow == src_sum); | |
419 | // check if flow is the sum of ingoing edges of sink | |
420 | tEdgeVal sink_sum = 0; | |
421 | for (boost::tie(ei, e_end) = out_edges(this->m_sink, this->m_g); | |
422 | ei != e_end; ++ei) | |
423 | { | |
7c673cae FG |
424 | tEdge in_edge = this->m_rev_edge_map[*ei]; |
425 | sink_sum += this->m_cap_map[in_edge] - this->m_res_cap_map[in_edge]; | |
7c673cae | 426 | } |
f67539c2 TL |
427 | BOOST_TEST(this->m_flow == sink_sum); |
428 | return this->m_flow; | |
429 | } | |
7c673cae FG |
430 | }; |
431 | ||
432 | long test_algorithms_invariant(int n_verts, int n_edges, std::size_t seed) | |
433 | { | |
f67539c2 TL |
434 | typedef adjacency_list_traits< vecS, vecS, directedS > tVectorTraits; |
435 | typedef adjacency_list< vecS, vecS, directedS, | |
436 | property< vertex_index_t, long, | |
437 | property< vertex_predecessor_t, tVectorTraits::edge_descriptor, | |
438 | property< vertex_color_t, default_color_type, | |
439 | property< vertex_distance_t, long > > > >, | |
440 | property< edge_capacity_t, long, | |
441 | property< edge_residual_capacity_t, long, | |
442 | property< edge_reverse_t, tVectorTraits::edge_descriptor > > > > | |
443 | tVectorGraph; | |
444 | ||
445 | tVectorGraph g; | |
446 | ||
447 | graph_traits< tVectorGraph >::vertex_descriptor src, sink; | |
448 | boost::tie(src, sink) = fill_random_max_flow_graph( | |
449 | g, get(edge_capacity, g), get(edge_reverse, g), n_verts, n_edges, seed); | |
450 | ||
451 | typedef property_map< tVectorGraph, edge_capacity_t >::type tEdgeCapMap; | |
452 | typedef property_map< tVectorGraph, edge_residual_capacity_t >::type | |
453 | tEdgeResCapMap; | |
454 | typedef property_map< tVectorGraph, edge_reverse_t >::type tRevEdgeMap; | |
455 | typedef property_map< tVectorGraph, vertex_predecessor_t >::type | |
456 | tVertexPredMap; | |
457 | typedef property_map< tVectorGraph, vertex_color_t >::type tVertexColorMap; | |
458 | typedef property_map< tVectorGraph, vertex_distance_t >::type tDistanceMap; | |
459 | typedef property_map< tVectorGraph, vertex_index_t >::type tIndexMap; | |
460 | typedef boykov_kolmogorov_test< tVectorGraph, tEdgeCapMap, tEdgeResCapMap, | |
461 | tRevEdgeMap, tVertexPredMap, tVertexColorMap, tDistanceMap, tIndexMap > | |
462 | tKolmo; | |
463 | tKolmo instance(g, src, sink); | |
464 | return instance.test(); | |
7c673cae FG |
465 | } |
466 | ||
f67539c2 | 467 | int main(int argc, char* argv[]) |
7c673cae | 468 | { |
f67539c2 TL |
469 | int n_verts = 10; |
470 | int n_edges = 500; | |
471 | std::size_t seed = 1; | |
472 | ||
473 | if (argc > 1) | |
474 | n_verts = lexical_cast< int >(argv[1]); | |
475 | if (argc > 2) | |
476 | n_edges = lexical_cast< int >(argv[2]); | |
477 | if (argc > 3) | |
478 | seed = lexical_cast< std::size_t >(argv[3]); | |
479 | ||
480 | // we need at least 2 vertices to create src and sink in random graphs | |
481 | // this case is also caught in boykov_kolmogorov_max_flow | |
482 | if (n_verts < 2) | |
483 | n_verts = 2; | |
484 | ||
485 | // below are checks for different calls to boykov_kolmogorov_max_flow and | |
486 | // different graph-types | |
487 | ||
488 | // checks support of vecS storage | |
489 | long flow_vecS = test_adjacency_list_vecS(n_verts, n_edges, seed); | |
490 | std::cout << "vecS flow: " << flow_vecS << std::endl; | |
491 | // checks support of listS storage (especially problems with vertex indices) | |
492 | long flow_listS = test_adjacency_list_listS(n_verts, n_edges, seed); | |
493 | std::cout << "listS flow: " << flow_listS << std::endl; | |
494 | BOOST_TEST(flow_vecS == flow_listS); | |
495 | // checks bundled properties | |
496 | long flow_bundles = test_bundled_properties(n_verts, n_edges, seed); | |
497 | std::cout << "bundles flow: " << flow_bundles << std::endl; | |
498 | BOOST_TEST(flow_listS == flow_bundles); | |
499 | // checks overloads | |
500 | long flow_overloads = test_overloads(n_verts, n_edges, seed); | |
501 | std::cout << "overloads flow: " << flow_overloads << std::endl; | |
502 | BOOST_TEST(flow_bundles == flow_overloads); | |
503 | ||
504 | // excessive test version where Boykov-Kolmogorov's algorithm invariants are | |
505 | // checked | |
506 | long flow_invariants = test_algorithms_invariant(n_verts, n_edges, seed); | |
507 | std::cout << "invariants flow: " << flow_invariants << std::endl; | |
508 | BOOST_TEST(flow_overloads == flow_invariants); | |
509 | return boost::report_errors(); | |
7c673cae | 510 | } |