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