ceph/src/boost/boost/graph/cycle_canceling.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 //
  11 //This algorithm is described in "Network Flows: Theory, Algorithms, and Applications"
  12 // by Ahuja, Magnanti, Orlin.
  13
  14 #ifndef BOOST_GRAPH_CYCLE_CANCELING_HPP
  15 #define BOOST_GRAPH_CYCLE_CANCELING_HPP
  16
  17 #include <numeric>
  18
  19 #include <boost/property_map/property_map.hpp>
  20 #include <boost/graph/graph_traits.hpp>
  21 #include <boost/graph/graph_concepts.hpp>
  22 #include <boost/pending/indirect_cmp.hpp>
  23 #include <boost/pending/relaxed_heap.hpp>
  24 #include <boost/graph/bellman_ford_shortest_paths.hpp>
  25 #include <boost/graph/iteration_macros.hpp>
  26 #include <boost/graph/detail/augment.hpp>
  27 #include <boost/graph/find_flow_cost.hpp>
  28
  29 namespace boost {
  30
  31
  32 namespace detail {
  33
  34 template <typename PredEdgeMap, typename Vertex>
  35 class RecordEdgeMapAndCycleVertex
  36     : public bellman_visitor<edge_predecessor_recorder<PredEdgeMap, on_edge_relaxed> > {
  37         typedef edge_predecessor_recorder<PredEdgeMap, on_edge_relaxed> PredRec;
  38 public:
  39     RecordEdgeMapAndCycleVertex(PredEdgeMap pred, Vertex & v) :
  40         bellman_visitor<PredRec>(PredRec(pred)), m_v(v), m_pred(pred) {}
  41
  42     template <typename Graph, typename Edge>
  43     void edge_not_minimized(Edge e, const Graph & g) const {
  44         typename graph_traits<Graph>::vertices_size_type n = num_vertices(g) + 1;
  45
  46         //edge e is not minimized but does not have to be on the negative weight cycle
  47         //to find vertex on negative wieight cycle we move n+1 times backword in the PredEdgeMap graph.
  48         while(n > 0) {
  49             e = get(m_pred, source(e, g));
  50             --n;
  51         }
  52         m_v = source(e, g);
  53     }
  54 private:
  55     Vertex & m_v;
  56     PredEdgeMap m_pred;
  57 };
  58
  59 } //detail
  60
  61
  62 template <class Graph, class Pred, class Distance, class Reversed, class ResidualCapacity, class Weight>
  63 void cycle_canceling(const Graph &g, Weight weight, Reversed rev, ResidualCapacity residual_capacity, Pred pred, Distance distance) {
  64     typedef filtered_graph<const Graph, is_residual_edge<ResidualCapacity> > ResGraph;
  65     ResGraph gres = detail::residual_graph(g, residual_capacity);
  66
  67     typedef graph_traits<ResGraph> ResGTraits;
  68     typedef graph_traits<Graph> GTraits;
  69     typedef typename ResGTraits::edge_descriptor edge_descriptor;
  70     typedef typename ResGTraits::vertex_descriptor vertex_descriptor;
  71
  72     typename GTraits::vertices_size_type N = num_vertices(g);
  73
  74     BGL_FORALL_VERTICES_T(v, g, Graph) {
  75         put(pred, v, edge_descriptor());
  76         put(distance, v, 0);
  77     }
  78
  79     vertex_descriptor cycleStart;
  80     while(!bellman_ford_shortest_paths(gres, N,
  81             weight_map(weight).
  82             distance_map(distance).
  83             visitor(detail::RecordEdgeMapAndCycleVertex<Pred, vertex_descriptor>(pred, cycleStart)))) {
  84
  85         detail::augment(g, cycleStart, cycleStart, pred, residual_capacity, rev);
  86
  87         BGL_FORALL_VERTICES_T(v, g, Graph) {
  88             put(pred, v, edge_descriptor());
  89             put(distance, v, 0);
  90         }
  91     }
  92 }
  93
  94
  95 //in this namespace argument dispatching takes place
  96 namespace detail {
  97
  98 template <class Graph, class P, class T, class R, class ResidualCapacity, class Weight, class Reversed, class Pred, class Distance>
  99 void cycle_canceling_dispatch2(
 100         const Graph &g,
 101         Weight weight,
 102         Reversed rev,
 103         ResidualCapacity residual_capacity,
 104         Pred pred,
 105         Distance dist,
 106         const bgl_named_params<P, T, R>& params) {
 107     cycle_canceling(g, weight, rev, residual_capacity, pred, dist);
 108 }
 109
 110 //setting default distance map
 111 template <class Graph, class P, class T, class R, class Pred, class ResidualCapacity, class Weight, class Reversed>
 112 void cycle_canceling_dispatch2(
 113         Graph &g,
 114         Weight weight,
 115         Reversed rev,
 116         ResidualCapacity residual_capacity,
 117         Pred pred,
 118         param_not_found,
 119         const bgl_named_params<P, T, R>& params) {
 120     typedef typename property_traits<Weight>::value_type D;
 121
 122     std::vector<D> d_map(num_vertices(g));
 123
 124     cycle_canceling(g, weight, rev, residual_capacity, pred,
 125                     make_iterator_property_map(d_map.begin(), choose_const_pmap(get_param(params, vertex_index), g, vertex_index)));
 126 }
 127
 128 template <class Graph, class P, class T, class R, class ResidualCapacity, class Weight, class Reversed, class Pred>
 129 void cycle_canceling_dispatch1(
 130         Graph &g,
 131         Weight weight,
 132         Reversed rev,
 133         ResidualCapacity residual_capacity,
 134         Pred pred,
 135         const bgl_named_params<P, T, R>& params) {
 136     cycle_canceling_dispatch2(g, weight, rev,residual_capacity,  pred,
 137                                 get_param(params, vertex_distance), params);
 138 }
 139
 140 //setting default predecessors map
 141 template <class Graph, class P, class T, class R, class ResidualCapacity, class Weight, class Reversed>
 142 void cycle_canceling_dispatch1(
 143         Graph &g,
 144         Weight weight,
 145         Reversed rev,
 146         ResidualCapacity residual_capacity,
 147         param_not_found,
 148         const bgl_named_params<P, T, R>& params) {
 149     typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor;
 150     std::vector<edge_descriptor> p_map(num_vertices(g));
 151
 152     cycle_canceling_dispatch2(g, weight, rev, residual_capacity,
 153                               make_iterator_property_map(p_map.begin(), choose_const_pmap(get_param(params, vertex_index), g, vertex_index)),
 154                                 get_param(params, vertex_distance), params);
 155 }
 156
 157 }//detail
 158
 159 template <class Graph, class  P, class T, class R>
 160 void cycle_canceling(Graph &g,
 161         const bgl_named_params<P, T, R>& params) {
 162     cycle_canceling_dispatch1(g,
 163            choose_const_pmap(get_param(params, edge_weight), g, edge_weight),
 164            choose_const_pmap(get_param(params, edge_reverse), g, edge_reverse),
 165            choose_pmap(get_param(params, edge_residual_capacity),
 166                        g, edge_residual_capacity),
 167            get_param(params, vertex_predecessor),
 168            params);
 169 }
 170
 171 template <class Graph>
 172 void cycle_canceling(Graph &g) {
 173     bgl_named_params<int, buffer_param_t> params(0);
 174     cycle_canceling(g, params);
 175 }
 176
 177
 178 }
 179
 180 #endif /* BOOST_GRAPH_CYCLE_CANCELING_HPP */
 181