ceph/src/boost/boost/graph/successive_shortest_path_nonnegative_weights.hpp

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