1 //=======================================================================
2 // Copyright 2013 University of Warsaw.
3 // Authors: Piotr Wygocki
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 //=======================================================================
10 //This algorithm is described in "Network Flows: Theory, Algorithms, and Applications"
11 // by Ahuja, Magnanti, Orlin.
13 #ifndef BOOST_GRAPH_SUCCESSIVE_SHORTEST_PATH_HPP
14 #define BOOST_GRAPH_SUCCESSIVE_SHORTEST_PATH_HPP
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>
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;
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) {}
45 reference operator[](key_type v) const {
46 return get(distance_, source(v, g_)) - get(distance_,target(v, g_)) + get(weight_, v);
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);
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(
67 typename graph_traits<Graph>::vertex_descriptor s,
68 typename graph_traits<Graph>::vertex_descriptor t,
70 ResidualCapacity residual_capacity,
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;
81 BGL_FORALL_EDGES_T(e, g, Graph) {
82 put(residual_capacity, e, get(capacity, e));
85 BGL_FORALL_VERTICES_T(v, g, Graph) {
86 put(distance_prev, v, 0);
90 BGL_FORALL_VERTICES_T(v, g, Graph) {
91 put(pred, v, edge_descriptor());
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()))));
99 if(get(pred, t) == edge_descriptor()) {
103 BGL_FORALL_VERTICES_T(v, g, Graph) {
104 put(distance_prev, v, get(distance_prev, v) + get(distance, v));
107 detail::augment(g, s, t, pred, residual_capacity, rev);
111 //in this namespace argument dispatching tak place
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(
117 typename graph_traits<Graph>::vertex_descriptor s,
118 typename graph_traits<Graph>::vertex_descriptor t,
120 ResidualCapacity residual_capacity,
126 Distance2 dist_pred) {
127 successive_shortest_path_nonnegative_weights(g, s, t, capacity, residual_capacity, weight, rev, index, pred, dist, dist_pred);
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(
134 typename graph_traits<Graph>::vertex_descriptor s,
135 typename graph_traits<Graph>::vertex_descriptor t,
137 ResidualCapacity residual_capacity,
144 typedef typename property_traits<Weight>::value_type D;
146 std::vector<D> d_map(num_vertices(g));
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));
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(
155 typename graph_traits<Graph>::vertex_descriptor s,
156 typename graph_traits<Graph>::vertex_descriptor t,
158 ResidualCapacity residual_capacity,
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));
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(
172 typename graph_traits<Graph>::vertex_descriptor s,
173 typename graph_traits<Graph>::vertex_descriptor t,
175 ResidualCapacity residual_capacity,
181 const bgl_named_params<P, T, R>& params) {
182 typedef typename property_traits<Weight>::value_type D;
184 std::vector<D> d_map(num_vertices(g));
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));
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(
194 typename graph_traits<Graph>::vertex_descriptor s,
195 typename graph_traits<Graph>::vertex_descriptor t,
197 ResidualCapacity residual_capacity,
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);
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(
211 typename graph_traits<Graph>::vertex_descriptor s,
212 typename graph_traits<Graph>::vertex_descriptor t,
214 ResidualCapacity residual_capacity,
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));
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);
231 template <class Graph, class P, class T, class R>
232 void successive_shortest_path_nonnegative_weights(
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) {
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),
249 template <class Graph>
250 void successive_shortest_path_nonnegative_weights(
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);
260 #endif /* BOOST_GRAPH_SUCCESSIVE_SHORTEST_PATH_HPP */