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
28namespace boost {
29
30
31namespace detail {
32
33template <class Graph, class Weight, class Distance, class Reversed>
34class MapReducedWeight :
35 public put_get_helper<typename property_traits<Weight>::value_type, MapReducedWeight<Graph, Weight, Distance, Reversed> > {
36 typedef graph_traits<Graph> gtraits;
37public:
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 }
48private:
49 const Graph & g_;
50 Weight weight_;
51 Distance distance_;
52 Reversed rev_;
53};
54
55template <class Graph, class Weight, class Distance, class Reversed>
56MapReducedWeight<Graph, Weight, Distance, Reversed>
57make_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
64template <class Graph, class Capacity, class ResidualCapacity, class Reversed, class Pred, class Weight, class Distance, class Distance2, class VertexIndex>
65void 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
112namespace detail {
113
114template <class Graph, class Capacity, class ResidualCapacity, class Weight, class Reversed, class Pred, class Distance, class Distance2, class VertexIndex>
115void 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
131template <class Graph, class Capacity, class ResidualCapacity, class Weight, class Reversed, class Pred, class Distance, class VertexIndex>
132void 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
152template <class Graph, class P, class T, class R, class Capacity, class ResidualCapacity, class Weight, class Reversed, class Pred, class Distance, class VertexIndex>
153void 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
169template <class Graph, class P, class T, class R, class Capacity, class ResidualCapacity, class Weight, class Reversed, class Pred, class VertexIndex>
170void 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
191template <class Graph, class P, class T, class R, class Capacity, class ResidualCapacity, class Weight, class Reversed, class Pred, class VertexIndex>
192void 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
208template <class Graph, class P, class T, class R, class Capacity, class ResidualCapacity, class Weight, class Reversed, class VertexIndex>
209void 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
231template <class Graph, class P, class T, class R>
232void 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
249template <class Graph>
250void 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

source code of boost/boost/graph/successive_shortest_path_nonnegative_weights.hpp