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/successive_shortest_path_nonnegative_weights.hpp> |
13 | #include <boost/graph/find_flow_cost.hpp> |
14 | |
15 | #include "min_cost_max_flow_utils.hpp" |
16 | |
17 | void path_augmentation_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::successive_shortest_path_nonnegative_weights(g, s, t); |
24 | |
25 | int cost = boost::find_flow_cost(g); |
26 | BOOST_TEST_EQ(cost, 29); |
27 | } |
28 | |
29 | void path_augmentation_def_test2() |
30 | { |
31 | boost::SampleGraph::vertex_descriptor s, t; |
32 | boost::SampleGraph::Graph g; |
33 | boost::SampleGraph::getSampleGraph2(g, s, t); |
34 | |
35 | boost::successive_shortest_path_nonnegative_weights(g, s, t); |
36 | |
37 | int cost = boost::find_flow_cost(g); |
38 | BOOST_TEST_EQ(cost, 7); |
39 | } |
40 | |
41 | void path_augmentation_test() |
42 | { |
43 | boost::SampleGraph::vertex_descriptor s, t; |
44 | typedef boost::SampleGraph::Graph Graph; |
45 | Graph g; |
46 | boost::SampleGraph::getSampleGraph(g, s, t); |
47 | |
48 | int N = boost::num_vertices(g_: g); |
49 | std::vector< int > dist(N); |
50 | std::vector< int > dist_prev(N); |
51 | typedef boost::graph_traits< Graph >::edge_descriptor edge_descriptor; |
52 | std::vector< edge_descriptor > pred(N); |
53 | |
54 | boost::property_map< Graph, boost::vertex_index_t >::const_type idx |
55 | = get(p: boost::vertex_index, g); |
56 | |
57 | boost::successive_shortest_path_nonnegative_weights(g, s, t, |
58 | params: boost::distance_map( |
59 | p: boost::make_iterator_property_map(iter: dist.begin(), id: idx)) |
60 | .predecessor_map( |
61 | p: boost::make_iterator_property_map(iter: pred.begin(), id: idx)) |
62 | .distance_map2( |
63 | p: boost::make_iterator_property_map(iter: dist_prev.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 | path_augmentation_def_test(); |
73 | path_augmentation_def_test2(); |
74 | path_augmentation_test(); |
75 | return boost::report_errors(); |
76 | } |
77 | |