boost/graph/successive_shortest_path_nonnegative_weights.hpp

0001 //=======================================================================
0002 // Copyright 2013 University of Warsaw.
0003 // Authors: Piotr Wygocki
0004 //
0005 // Distributed under the Boost Software License, Version 1.0. (See
0006 // accompanying file LICENSE_1_0.txt or copy at
0007 // http://www.boost.org/LICENSE_1_0.txt)
0008 //=======================================================================
0009 //
0010 // This algorithm is described in "Network Flows: Theory, Algorithms, and
0011 // Applications"
0012 // by Ahuja, Magnanti, Orlin.
0013
0014 #ifndef BOOST_GRAPH_SUCCESSIVE_SHORTEST_PATH_HPP
0015 #define BOOST_GRAPH_SUCCESSIVE_SHORTEST_PATH_HPP
0016
0017 #include <numeric>
0018
0019 #include <boost/property_map/property_map.hpp>
0020 #include <boost/graph/graph_traits.hpp>
0021 #include <boost/graph/graph_concepts.hpp>
0022 #include <boost/pending/indirect_cmp.hpp>
0023 #include <boost/graph/dijkstra_shortest_paths.hpp>
0024 #include <boost/graph/properties.hpp>
0025 #include <boost/graph/iteration_macros.hpp>
0026 #include <boost/graph/detail/augment.hpp>
0027
0028 namespace boost
0029 {
0030
0031 namespace detail
0032 {
0033
0034     template < class Graph, class Weight, class Distance, class Reversed >
0035     class MapReducedWeight
0036     : public put_get_helper< typename property_traits< Weight >::value_type,
0037           MapReducedWeight< Graph, Weight, Distance, Reversed > >
0038     {
0039         typedef graph_traits< Graph > gtraits;
0040
0041     public:
0042         typedef boost::readable_property_map_tag category;
0043         typedef typename property_traits< Weight >::value_type value_type;
0044         typedef value_type reference;
0045         typedef typename gtraits::edge_descriptor key_type;
0046         MapReducedWeight(const Graph& g, Weight w, Distance d, Reversed r)
0047         : g_(g), weight_(w), distance_(d), rev_(r)
0048         {
0049         }
0050
0051         reference operator[](key_type v) const
0052         {
0053             return get(distance_, source(v, g_)) - get(distance_, target(v, g_))
0054                 + get(weight_, v);
0055         }
0056
0057     private:
0058         const Graph& g_;
0059         Weight weight_;
0060         Distance distance_;
0061         Reversed rev_;
0062     };
0063
0064     template < class Graph, class Weight, class Distance, class Reversed >
0065     MapReducedWeight< Graph, Weight, Distance, Reversed > make_mapReducedWeight(
0066         const Graph& g, Weight w, Distance d, Reversed r)
0067     {
0068         return MapReducedWeight< Graph, Weight, Distance, Reversed >(
0069             g, w, d, r);
0070     }
0071
0072 } // detail
0073
0074 template < class Graph, class Capacity, class ResidualCapacity, class Reversed,
0075     class Pred, class Weight, class Distance, class Distance2,
0076     class VertexIndex >
0077 void successive_shortest_path_nonnegative_weights(const Graph& g,
0078     typename graph_traits< Graph >::vertex_descriptor s,
0079     typename graph_traits< Graph >::vertex_descriptor t, Capacity capacity,
0080     ResidualCapacity residual_capacity, Weight weight, Reversed rev,
0081     VertexIndex index, Pred pred, Distance distance, Distance2 distance_prev)
0082 {
0083     filtered_graph< const Graph, is_residual_edge< ResidualCapacity > > gres
0084         = detail::residual_graph(g, residual_capacity);
0085     typedef typename graph_traits< Graph >::edge_descriptor edge_descriptor;
0086
0087     BGL_FORALL_EDGES_T(e, g, Graph)
0088     {
0089         put(residual_capacity, e, get(capacity, e));
0090     }
0091
0092     BGL_FORALL_VERTICES_T(v, g, Graph) { put(distance_prev, v, 0); }
0093
0094     while (true)
0095     {
0096         BGL_FORALL_VERTICES_T(v, g, Graph) { put(pred, v, edge_descriptor()); }
0097         dijkstra_shortest_paths(gres, s,
0098             weight_map(
0099                 detail::make_mapReducedWeight(gres, weight, distance_prev, rev))
0100                 .distance_map(distance)
0101                 .vertex_index_map(index)
0102                 .visitor(make_dijkstra_visitor(
0103                     record_edge_predecessors(pred, on_edge_relaxed()))));
0104
0105         if (get(pred, t) == edge_descriptor())
0106         {
0107             break;
0108         }
0109
0110         BGL_FORALL_VERTICES_T(v, g, Graph)
0111         {
0112             put(distance_prev, v, get(distance_prev, v) + get(distance, v));
0113         }
0114
0115         detail::augment(g, s, t, pred, residual_capacity, rev);
0116     }
0117 }
0118
0119 // in this namespace argument dispatching tak place
0120 namespace detail
0121 {
0122
0123     template < class Graph, class Capacity, class ResidualCapacity,
0124         class Weight, class Reversed, class Pred, class Distance,
0125         class Distance2, class VertexIndex >
0126     void successive_shortest_path_nonnegative_weights_dispatch3(const Graph& g,
0127         typename graph_traits< Graph >::vertex_descriptor s,
0128         typename graph_traits< Graph >::vertex_descriptor t, Capacity capacity,
0129         ResidualCapacity residual_capacity, Weight weight, Reversed rev,
0130         VertexIndex index, Pred pred, Distance dist, Distance2 dist_pred)
0131     {
0132         successive_shortest_path_nonnegative_weights(g, s, t, capacity,
0133             residual_capacity, weight, rev, index, pred, dist, dist_pred);
0134     }
0135
0136     // setting default distance map
0137     template < class Graph, class Capacity, class ResidualCapacity,
0138         class Weight, class Reversed, class Pred, class Distance,
0139         class VertexIndex >
0140     void successive_shortest_path_nonnegative_weights_dispatch3(Graph& g,
0141         typename graph_traits< Graph >::vertex_descriptor s,
0142         typename graph_traits< Graph >::vertex_descriptor t, Capacity capacity,
0143         ResidualCapacity residual_capacity, Weight weight, Reversed rev,
0144         VertexIndex index, Pred pred, Distance dist, param_not_found)
0145     {
0146         typedef typename property_traits< Weight >::value_type D;
0147
0148         std::vector< D > d_map(num_vertices(g));
0149
0150         successive_shortest_path_nonnegative_weights(g, s, t, capacity,
0151             residual_capacity, weight, rev, index, pred, dist,
0152             make_iterator_property_map(d_map.begin(), index));
0153     }
0154
0155     template < class Graph, class P, class T, class R, class Capacity,
0156         class ResidualCapacity, class Weight, class Reversed, class Pred,
0157         class Distance, class VertexIndex >
0158     void successive_shortest_path_nonnegative_weights_dispatch2(Graph& g,
0159         typename graph_traits< Graph >::vertex_descriptor s,
0160         typename graph_traits< Graph >::vertex_descriptor t, Capacity capacity,
0161         ResidualCapacity residual_capacity, Weight weight, Reversed rev,
0162         VertexIndex index, Pred pred, Distance dist,
0163         const bgl_named_params< P, T, R >& params)
0164     {
0165         successive_shortest_path_nonnegative_weights_dispatch3(g, s, t,
0166             capacity, residual_capacity, weight, rev, index, pred, dist,
0167             get_param(params, vertex_distance2));
0168     }
0169
0170     // setting default distance map
0171     template < class Graph, class P, class T, class R, class Capacity,
0172         class ResidualCapacity, class Weight, class Reversed, class Pred,
0173         class VertexIndex >
0174     void successive_shortest_path_nonnegative_weights_dispatch2(Graph& g,
0175         typename graph_traits< Graph >::vertex_descriptor s,
0176         typename graph_traits< Graph >::vertex_descriptor t, Capacity capacity,
0177         ResidualCapacity residual_capacity, Weight weight, Reversed rev,
0178         VertexIndex index, Pred pred, param_not_found,
0179         const bgl_named_params< P, T, R >& params)
0180     {
0181         typedef typename property_traits< Weight >::value_type D;
0182
0183         std::vector< D > d_map(num_vertices(g));
0184
0185         successive_shortest_path_nonnegative_weights_dispatch3(g, s, t,
0186             capacity, residual_capacity, weight, rev, index, pred,
0187             make_iterator_property_map(d_map.begin(), index),
0188             get_param(params, vertex_distance2));
0189     }
0190
0191     template < class Graph, class P, class T, class R, class Capacity,
0192         class ResidualCapacity, class Weight, class Reversed, class Pred,
0193         class VertexIndex >
0194     void successive_shortest_path_nonnegative_weights_dispatch1(Graph& g,
0195         typename graph_traits< Graph >::vertex_descriptor s,
0196         typename graph_traits< Graph >::vertex_descriptor t, Capacity capacity,
0197         ResidualCapacity residual_capacity, Weight weight, Reversed rev,
0198         VertexIndex index, Pred pred, const bgl_named_params< P, T, R >& params)
0199     {
0200         successive_shortest_path_nonnegative_weights_dispatch2(g, s, t,
0201             capacity, residual_capacity, weight, rev, index, pred,
0202             get_param(params, vertex_distance), params);
0203     }
0204
0205     // setting default predecessors map
0206     template < class Graph, class P, class T, class R, class Capacity,
0207         class ResidualCapacity, class Weight, class Reversed,
0208         class VertexIndex >
0209     void successive_shortest_path_nonnegative_weights_dispatch1(Graph& g,
0210         typename graph_traits< Graph >::vertex_descriptor s,
0211         typename graph_traits< Graph >::vertex_descriptor t, Capacity capacity,
0212         ResidualCapacity residual_capacity, Weight weight, Reversed rev,
0213         VertexIndex index, param_not_found,
0214         const bgl_named_params< P, T, R >& params)
0215     {
0216         typedef typename graph_traits< Graph >::edge_descriptor edge_descriptor;
0217         std::vector< edge_descriptor > pred_vec(num_vertices(g));
0218
0219         successive_shortest_path_nonnegative_weights_dispatch2(g, s, t,
0220             capacity, residual_capacity, weight, rev, index,
0221             make_iterator_property_map(pred_vec.begin(), index),
0222             get_param(params, vertex_distance), params);
0223     }
0224
0225 } // detail
0226
0227 template < class Graph, class P, class T, class R >
0228 void successive_shortest_path_nonnegative_weights(Graph& g,
0229     typename graph_traits< Graph >::vertex_descriptor s,
0230     typename graph_traits< Graph >::vertex_descriptor t,
0231     const bgl_named_params< P, T, R >& params)
0232 {
0233
0234     return detail::successive_shortest_path_nonnegative_weights_dispatch1(g, s,
0235         t,
0236         choose_const_pmap(get_param(params, edge_capacity), g, edge_capacity),
0237         choose_pmap(get_param(params, edge_residual_capacity), g,
0238             edge_residual_capacity),
0239         choose_const_pmap(get_param(params, edge_weight), g, edge_weight),
0240         choose_const_pmap(get_param(params, edge_reverse), g, edge_reverse),
0241         choose_const_pmap(get_param(params, vertex_index), g, vertex_index),
0242         get_param(params, vertex_predecessor), params);
0243 }
0244
0245 template < class Graph >
0246 void successive_shortest_path_nonnegative_weights(Graph& g,
0247     typename graph_traits< Graph >::vertex_descriptor s,
0248     typename graph_traits< Graph >::vertex_descriptor t)
0249 {
0250     bgl_named_params< int, buffer_param_t > params(0);
0251     successive_shortest_path_nonnegative_weights(g, s, t, params);
0252 }
0253
0254 } // boost
0255 #endif /* BOOST_GRAPH_SUCCESSIVE_SHORTEST_PATH_HPP */