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 | //This algorithm is described in "Network Flows: Theory, Algorithms, and Applications" |
11 | // by Ahuja, Magnanti, Orlin. |
12 | |
13 | #ifndef BOOST_GRAPH_SUCCESSIVE_SHORTEST_PATH_HPP |
14 | #define BOOST_GRAPH_SUCCESSIVE_SHORTEST_PATH_HPP |
15 | |
16 | #include <numeric> |
17 | |
18 | #include <boost/property_map/property_map.hpp> |
19 | #include <boost/graph/graph_traits.hpp> |
20 | #include <boost/graph/graph_concepts.hpp> |
21 | #include <boost/pending/indirect_cmp.hpp> |
22 | #include <boost/pending/relaxed_heap.hpp> |
23 | #include <boost/graph/dijkstra_shortest_paths.hpp> |
24 | #include <boost/graph/properties.hpp> |
25 | #include <boost/graph/iteration_macros.hpp> |
26 | #include <boost/graph/detail/augment.hpp> |
27 | |
28 | namespace boost { |
29 | |
30 | |
31 | namespace detail { |
32 | |
33 | template <class Graph, class Weight, class Distance, class Reversed> |
34 | class MapReducedWeight : |
35 | public put_get_helper<typename property_traits<Weight>::value_type, MapReducedWeight<Graph, Weight, Distance, Reversed> > { |
36 | typedef graph_traits<Graph> gtraits; |
37 | public: |
38 | typedef boost::readable_property_map_tag category; |
39 | typedef typename property_traits<Weight>::value_type value_type; |
40 | typedef value_type reference; |
41 | typedef typename gtraits::edge_descriptor key_type; |
42 | MapReducedWeight(const Graph & g, Weight w, Distance d, Reversed r) : |
43 | g_(g), weight_(w), distance_(d), rev_(r) {} |
44 | |
45 | reference operator[](key_type v) const { |
46 | return get(distance_, source(v, g_)) - get(distance_,target(v, g_)) + get(weight_, v); |
47 | } |
48 | private: |
49 | const Graph & g_; |
50 | Weight weight_; |
51 | Distance distance_; |
52 | Reversed rev_; |
53 | }; |
54 | |
55 | template <class Graph, class Weight, class Distance, class Reversed> |
56 | MapReducedWeight<Graph, Weight, Distance, Reversed> |
57 | make_mapReducedWeight(const Graph & g, Weight w, Distance d, Reversed r) { |
58 | return MapReducedWeight<Graph, Weight, Distance, Reversed>(g, w, d, r); |
59 | } |
60 | |
61 | }//detail |
62 | |
63 | |
64 | template <class Graph, class Capacity, class ResidualCapacity, class Reversed, class Pred, class Weight, class Distance, class Distance2, class VertexIndex> |
65 | void successive_shortest_path_nonnegative_weights( |
66 | const Graph &g, |
67 | typename graph_traits<Graph>::vertex_descriptor s, |
68 | typename graph_traits<Graph>::vertex_descriptor t, |
69 | Capacity capacity, |
70 | ResidualCapacity residual_capacity, |
71 | Weight weight, |
72 | Reversed rev, |
73 | VertexIndex index, |
74 | Pred pred, |
75 | Distance distance, |
76 | Distance2 distance_prev) { |
77 | filtered_graph<const Graph, is_residual_edge<ResidualCapacity> > |
78 | gres = detail::residual_graph(g, residual_capacity); |
79 | typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor; |
80 | |
81 | BGL_FORALL_EDGES_T(e, g, Graph) { |
82 | put(residual_capacity, e, get(capacity, e)); |
83 | } |
84 | |
85 | BGL_FORALL_VERTICES_T(v, g, Graph) { |
86 | put(distance_prev, v, 0); |
87 | } |
88 | |
89 | while(true) { |
90 | BGL_FORALL_VERTICES_T(v, g, Graph) { |
91 | put(pred, v, edge_descriptor()); |
92 | } |
93 | dijkstra_shortest_paths(gres, s, |
94 | weight_map(detail::make_mapReducedWeight(gres, weight, distance_prev, rev)). |
95 | distance_map(distance). |
96 | vertex_index_map(index). |
97 | visitor(make_dijkstra_visitor(record_edge_predecessors(pred, on_edge_relaxed())))); |
98 | |
99 | if(get(pred, t) == edge_descriptor()) { |
100 | break; |
101 | } |
102 | |
103 | BGL_FORALL_VERTICES_T(v, g, Graph) { |
104 | put(distance_prev, v, get(distance_prev, v) + get(distance, v)); |
105 | } |
106 | |
107 | detail::augment(g, s, t, pred, residual_capacity, rev); |
108 | } |
109 | } |
110 | |
111 | //in this namespace argument dispatching tak place |
112 | namespace detail { |
113 | |
114 | template <class Graph, class Capacity, class ResidualCapacity, class Weight, class Reversed, class Pred, class Distance, class Distance2, class VertexIndex> |
115 | void successive_shortest_path_nonnegative_weights_dispatch3( |
116 | const Graph &g, |
117 | typename graph_traits<Graph>::vertex_descriptor s, |
118 | typename graph_traits<Graph>::vertex_descriptor t, |
119 | Capacity capacity, |
120 | ResidualCapacity residual_capacity, |
121 | Weight weight, |
122 | Reversed rev, |
123 | VertexIndex index, |
124 | Pred pred, |
125 | Distance dist, |
126 | Distance2 dist_pred) { |
127 | successive_shortest_path_nonnegative_weights(g, s, t, capacity, residual_capacity, weight, rev, index, pred, dist, dist_pred); |
128 | } |
129 | |
130 | //setting default distance map |
131 | template <class Graph, class Capacity, class ResidualCapacity, class Weight, class Reversed, class Pred, class Distance, class VertexIndex> |
132 | void successive_shortest_path_nonnegative_weights_dispatch3( |
133 | Graph &g, |
134 | typename graph_traits<Graph>::vertex_descriptor s, |
135 | typename graph_traits<Graph>::vertex_descriptor t, |
136 | Capacity capacity, |
137 | ResidualCapacity residual_capacity, |
138 | Weight weight, |
139 | Reversed rev, |
140 | VertexIndex index, |
141 | Pred pred, |
142 | Distance dist, |
143 | param_not_found) { |
144 | typedef typename property_traits<Weight>::value_type D; |
145 | |
146 | std::vector<D> d_map(num_vertices(g)); |
147 | |
148 | successive_shortest_path_nonnegative_weights(g, s, t, capacity, residual_capacity, weight, rev, index, pred, dist, |
149 | make_iterator_property_map(d_map.begin(), index)); |
150 | } |
151 | |
152 | template <class Graph, class P, class T, class R, class Capacity, class ResidualCapacity, class Weight, class Reversed, class Pred, class Distance, class VertexIndex> |
153 | void successive_shortest_path_nonnegative_weights_dispatch2( |
154 | Graph &g, |
155 | typename graph_traits<Graph>::vertex_descriptor s, |
156 | typename graph_traits<Graph>::vertex_descriptor t, |
157 | Capacity capacity, |
158 | ResidualCapacity residual_capacity, |
159 | Weight weight, |
160 | Reversed rev, |
161 | VertexIndex index, |
162 | Pred pred, |
163 | Distance dist, |
164 | const bgl_named_params<P, T, R>& params) { |
165 | successive_shortest_path_nonnegative_weights_dispatch3(g, s, t, capacity, residual_capacity, weight, rev, index, pred, dist, get_param(params, vertex_distance2)); |
166 | } |
167 | |
168 | //setting default distance map |
169 | template <class Graph, class P, class T, class R, class Capacity, class ResidualCapacity, class Weight, class Reversed, class Pred, class VertexIndex> |
170 | void successive_shortest_path_nonnegative_weights_dispatch2( |
171 | Graph &g, |
172 | typename graph_traits<Graph>::vertex_descriptor s, |
173 | typename graph_traits<Graph>::vertex_descriptor t, |
174 | Capacity capacity, |
175 | ResidualCapacity residual_capacity, |
176 | Weight weight, |
177 | Reversed rev, |
178 | VertexIndex index, |
179 | Pred pred, |
180 | param_not_found, |
181 | const bgl_named_params<P, T, R>& params) { |
182 | typedef typename property_traits<Weight>::value_type D; |
183 | |
184 | std::vector<D> d_map(num_vertices(g)); |
185 | |
186 | successive_shortest_path_nonnegative_weights_dispatch3(g, s, t, capacity, residual_capacity, weight, rev, index, pred, |
187 | make_iterator_property_map(d_map.begin(), index), |
188 | get_param(params, vertex_distance2)); |
189 | } |
190 | |
191 | template <class Graph, class P, class T, class R, class Capacity, class ResidualCapacity, class Weight, class Reversed, class Pred, class VertexIndex> |
192 | void successive_shortest_path_nonnegative_weights_dispatch1( |
193 | Graph &g, |
194 | typename graph_traits<Graph>::vertex_descriptor s, |
195 | typename graph_traits<Graph>::vertex_descriptor t, |
196 | Capacity capacity, |
197 | ResidualCapacity residual_capacity, |
198 | Weight weight, |
199 | Reversed rev, |
200 | VertexIndex index, |
201 | Pred pred, |
202 | const bgl_named_params<P, T, R>& params) { |
203 | successive_shortest_path_nonnegative_weights_dispatch2(g, s, t, capacity, residual_capacity, weight, rev, index, pred, |
204 | get_param(params, vertex_distance), params); |
205 | } |
206 | |
207 | //setting default predecessors map |
208 | template <class Graph, class P, class T, class R, class Capacity, class ResidualCapacity, class Weight, class Reversed, class VertexIndex> |
209 | void successive_shortest_path_nonnegative_weights_dispatch1( |
210 | Graph &g, |
211 | typename graph_traits<Graph>::vertex_descriptor s, |
212 | typename graph_traits<Graph>::vertex_descriptor t, |
213 | Capacity capacity, |
214 | ResidualCapacity residual_capacity, |
215 | Weight weight, |
216 | Reversed rev, |
217 | VertexIndex index, |
218 | param_not_found, |
219 | const bgl_named_params<P, T, R>& params) { |
220 | typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor; |
221 | std::vector<edge_descriptor> pred_vec(num_vertices(g)); |
222 | |
223 | successive_shortest_path_nonnegative_weights_dispatch2(g, s, t, capacity, residual_capacity, weight, rev, index, |
224 | make_iterator_property_map(pred_vec.begin(), index), |
225 | get_param(params, vertex_distance), params); |
226 | } |
227 | |
228 | }//detail |
229 | |
230 | |
231 | template <class Graph, class P, class T, class R> |
232 | void successive_shortest_path_nonnegative_weights( |
233 | Graph &g, |
234 | typename graph_traits<Graph>::vertex_descriptor s, |
235 | typename graph_traits<Graph>::vertex_descriptor t, |
236 | const bgl_named_params<P, T, R>& params) { |
237 | |
238 | return detail::successive_shortest_path_nonnegative_weights_dispatch1(g, s, t, |
239 | choose_const_pmap(get_param(params, edge_capacity), g, edge_capacity), |
240 | choose_pmap(get_param(params, edge_residual_capacity), |
241 | g, edge_residual_capacity), |
242 | choose_const_pmap(get_param(params, edge_weight), g, edge_weight), |
243 | choose_const_pmap(get_param(params, edge_reverse), g, edge_reverse), |
244 | choose_const_pmap(get_param(params, vertex_index), g, vertex_index), |
245 | get_param(params, vertex_predecessor), |
246 | params); |
247 | } |
248 | |
249 | template <class Graph> |
250 | void successive_shortest_path_nonnegative_weights( |
251 | Graph &g, |
252 | typename graph_traits<Graph>::vertex_descriptor s, |
253 | typename graph_traits<Graph>::vertex_descriptor t) { |
254 | bgl_named_params<int, buffer_param_t> params(0); |
255 | successive_shortest_path_nonnegative_weights(g, s, t, params); |
256 | } |
257 | |
258 | |
259 | }//boost |
260 | #endif /* BOOST_GRAPH_SUCCESSIVE_SHORTEST_PATH_HPP */ |
261 | |
262 | |