1 | #include <boost/core/lightweight_test.hpp> |
2 | #include <boost/graph/successive_shortest_path_nonnegative_weights.hpp> |
3 | #include <boost/graph/find_flow_cost.hpp> |
4 | #include "min_cost_max_flow_utils.hpp" |
5 | |
6 | typedef boost::adjacency_list_traits< boost::vecS, boost::vecS, |
7 | boost::directedS > |
8 | traits; |
9 | struct edge_t |
10 | { |
11 | double capacity; |
12 | float cost; |
13 | float residual_capacity; |
14 | traits::edge_descriptor reversed_edge; |
15 | }; |
16 | struct node_t |
17 | { |
18 | traits::edge_descriptor predecessor; |
19 | int dist; |
20 | int dist_prev; |
21 | boost::vertex_index_t id; |
22 | }; |
23 | typedef boost::adjacency_list< boost::listS, boost::vecS, boost::directedS, |
24 | node_t, edge_t > |
25 | Graph; |
26 | |
27 | // Unit test written in order to fails (at compile time) if the find_flow_cost() |
28 | // is not properly handling bundled properties |
29 | void using_bundled_properties_with_find_max_flow_test() |
30 | { |
31 | Graph g; |
32 | traits::vertex_descriptor s, t; |
33 | |
34 | boost::property_map< Graph, double edge_t::* >::type capacity |
35 | = get(p: &edge_t::capacity, g); |
36 | boost::property_map< Graph, float edge_t::* >::type cost |
37 | = get(p: &edge_t::cost, g); |
38 | boost::property_map< Graph, float edge_t::* >::type residual_capacity |
39 | = get(p: &edge_t::residual_capacity, g); |
40 | boost::property_map< Graph, traits::edge_descriptor edge_t::* >::type rev |
41 | = get(p: &edge_t::reversed_edge, g); |
42 | boost::property_map< Graph, traits::edge_descriptor node_t::* >::type pred |
43 | = get(p: &node_t::predecessor, g); |
44 | boost::property_map< Graph, boost::vertex_index_t >::type vertex_indices |
45 | = get(p: boost::vertex_index, g); |
46 | boost::property_map< Graph, int node_t::* >::type dist |
47 | = get(p: &node_t::dist, g); |
48 | boost::property_map< Graph, int node_t::* >::type dist_prev |
49 | = get(p: &node_t::dist_prev, g); |
50 | |
51 | boost::SampleGraph::getSampleGraph( |
52 | g, s, t, capacity, residual_capacity, weight: cost, rev); |
53 | |
54 | boost::successive_shortest_path_nonnegative_weights(g, s, t, capacity, |
55 | residual_capacity, weight: cost, rev, index: vertex_indices, pred, distance: dist, distance_prev: dist_prev); |
56 | |
57 | // The "bundled properties" version (producing errors) |
58 | int flow_cost = boost::find_flow_cost(g, capacity, residual_capacity, weight: cost); |
59 | BOOST_TEST_EQ(flow_cost, 29); |
60 | } |
61 | |
62 | // Unit test written in order to fails (at compile time) if the find_flow_cost() |
63 | // is not properly handling bundled properties |
64 | void using_named_params_and_bundled_properties_with_find_max_flow_test() |
65 | { |
66 | Graph g; |
67 | traits::vertex_descriptor s, t; |
68 | |
69 | boost::property_map< Graph, double edge_t::* >::type capacity |
70 | = get(p: &edge_t::capacity, g); |
71 | boost::property_map< Graph, float edge_t::* >::type cost |
72 | = get(p: &edge_t::cost, g); |
73 | boost::property_map< Graph, float edge_t::* >::type residual_capacity |
74 | = get(p: &edge_t::residual_capacity, g); |
75 | boost::property_map< Graph, traits::edge_descriptor edge_t::* >::type rev |
76 | = get(p: &edge_t::reversed_edge, g); |
77 | boost::property_map< Graph, traits::edge_descriptor node_t::* >::type pred |
78 | = get(p: &node_t::predecessor, g); |
79 | boost::property_map< Graph, boost::vertex_index_t >::type vertex_indices |
80 | = get(p: boost::vertex_index, g); |
81 | boost::property_map< Graph, int node_t::* >::type dist |
82 | = get(p: &node_t::dist, g); |
83 | boost::property_map< Graph, int node_t::* >::type dist_prev |
84 | = get(p: &node_t::dist_prev, g); |
85 | |
86 | boost::SampleGraph::getSampleGraph( |
87 | g, s, t, capacity, residual_capacity, weight: cost, rev); |
88 | |
89 | boost::successive_shortest_path_nonnegative_weights(g, s, t, capacity, |
90 | residual_capacity, weight: cost, rev, index: vertex_indices, pred, distance: dist, distance_prev: dist_prev); |
91 | |
92 | // The "named parameters" version (with "bundled properties"; producing |
93 | // errors) |
94 | int flow_cost = boost::find_flow_cost(g, |
95 | params: boost::capacity_map(p: capacity) |
96 | .residual_capacity_map(p: residual_capacity) |
97 | .weight_map(p: cost)); |
98 | BOOST_TEST_EQ(flow_cost, 29); |
99 | } |
100 | |
101 | int main() |
102 | { |
103 | using_bundled_properties_with_find_max_flow_test(); |
104 | using_named_params_and_bundled_properties_with_find_max_flow_test(); |
105 | return boost::report_errors(); |
106 | } |
107 | |