]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | //======================================================================= |
2 | // Copyright 2013 University of Warsaw. | |
f67539c2 | 3 | // Authors: Piotr Wygocki |
7c673cae FG |
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 | ||
1e59de90 | 10 | #include <boost/core/lightweight_test.hpp> |
7c673cae FG |
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 | ||
1e59de90 | 17 | void path_augmentation_def_test() |
f67539c2 TL |
18 | { |
19 | boost::SampleGraph::vertex_descriptor s, t; | |
20 | boost::SampleGraph::Graph g; | |
7c673cae FG |
21 | boost::SampleGraph::getSampleGraph(g, s, t); |
22 | ||
23 | boost::successive_shortest_path_nonnegative_weights(g, s, t); | |
24 | ||
f67539c2 | 25 | int cost = boost::find_flow_cost(g); |
1e59de90 | 26 | BOOST_TEST_EQ(cost, 29); |
7c673cae FG |
27 | } |
28 | ||
1e59de90 | 29 | void path_augmentation_def_test2() |
f67539c2 TL |
30 | { |
31 | boost::SampleGraph::vertex_descriptor s, t; | |
32 | boost::SampleGraph::Graph g; | |
7c673cae FG |
33 | boost::SampleGraph::getSampleGraph2(g, s, t); |
34 | ||
35 | boost::successive_shortest_path_nonnegative_weights(g, s, t); | |
36 | ||
f67539c2 | 37 | int cost = boost::find_flow_cost(g); |
1e59de90 | 38 | BOOST_TEST_EQ(cost, 7); |
7c673cae FG |
39 | } |
40 | ||
1e59de90 | 41 | void path_augmentation_test() |
f67539c2 TL |
42 | { |
43 | boost::SampleGraph::vertex_descriptor s, t; | |
7c673cae FG |
44 | typedef boost::SampleGraph::Graph Graph; |
45 | Graph g; | |
46 | boost::SampleGraph::getSampleGraph(g, s, t); | |
47 | ||
48 | int N = boost::num_vertices(g); | |
f67539c2 TL |
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(boost::vertex_index, g); | |
56 | ||
57 | boost::successive_shortest_path_nonnegative_weights(g, s, t, | |
58 | boost::distance_map( | |
59 | boost::make_iterator_property_map(dist.begin(), idx)) | |
60 | .predecessor_map( | |
61 | boost::make_iterator_property_map(pred.begin(), idx)) | |
62 | .distance_map2( | |
63 | boost::make_iterator_property_map(dist_prev.begin(), idx)) | |
64 | .vertex_index_map(idx)); | |
65 | ||
66 | int cost = boost::find_flow_cost(g); | |
1e59de90 TL |
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(); | |
7c673cae | 76 | } |