ceph/src/boost/boost/graph/edmonds_karp_max_flow.hpp

   1 //=======================================================================
   2 // Copyright 2000 University of Notre Dame.
   3 // Authors: Jeremy G. Siek, Andrew Lumsdaine, Lie-Quan Lee
   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 #ifndef BOOST_GRAPH_EDMONDS_KARP_MAX_FLOW_HPP
  11 #define BOOST_GRAPH_EDMONDS_KARP_MAX_FLOW_HPP
  12
  13 #include <boost/config.hpp>
  14 #include <vector>
  15 #include <algorithm> // for std::min and std::max
  16 #include <boost/config.hpp>
  17 #include <boost/pending/queue.hpp>
  18 #include <boost/property_map/property_map.hpp>
  19 #include <boost/graph/graph_traits.hpp>
  20 #include <boost/graph/properties.hpp>
  21 #include <boost/graph/filtered_graph.hpp>
  22 #include <boost/graph/breadth_first_search.hpp>
  23
  24 namespace boost
  25 {
  26
  27 // The "labeling" algorithm from "Network Flows" by Ahuja, Magnanti,
  28 // Orlin.  I think this is the same as or very similar to the original
  29 // Edmonds-Karp algorithm.  This solves the maximum flow problem.
  30
  31 namespace detail
  32 {
  33
  34     template < class Graph, class ResCapMap >
  35     filtered_graph< Graph, is_residual_edge< ResCapMap > > residual_graph(
  36         Graph& g, ResCapMap residual_capacity)
  37     {
  38         return filtered_graph< Graph, is_residual_edge< ResCapMap > >(
  39             g, is_residual_edge< ResCapMap >(residual_capacity));
  40     }
  41
  42     template < class Graph, class PredEdgeMap, class ResCapMap,
  43         class RevEdgeMap >
  44     inline void augment(Graph& g,
  45         typename graph_traits< Graph >::vertex_descriptor src,
  46         typename graph_traits< Graph >::vertex_descriptor sink, PredEdgeMap p,
  47         ResCapMap residual_capacity, RevEdgeMap reverse_edge)
  48     {
  49         typename graph_traits< Graph >::edge_descriptor e;
  50         typename graph_traits< Graph >::vertex_descriptor u;
  51         typedef typename property_traits< ResCapMap >::value_type FlowValue;
  52
  53         // find minimum residual capacity along the augmenting path
  54         FlowValue delta = (std::numeric_limits< FlowValue >::max)();
  55         e = get(p, sink);
  56         do
  57         {
  58             BOOST_USING_STD_MIN();
  59             delta = min BOOST_PREVENT_MACRO_SUBSTITUTION(
  60                 delta, get(residual_capacity, e));
  61             u = source(e, g);
  62             e = get(p, u);
  63         } while (u != src);
  64
  65         // push delta units of flow along the augmenting path
  66         e = get(p, sink);
  67         do
  68         {
  69             put(residual_capacity, e, get(residual_capacity, e) - delta);
  70             put(residual_capacity, get(reverse_edge, e),
  71                 get(residual_capacity, get(reverse_edge, e)) + delta);
  72             u = source(e, g);
  73             e = get(p, u);
  74         } while (u != src);
  75     }
  76
  77 } // namespace detail
  78
  79 template < class Graph, class CapacityEdgeMap, class ResidualCapacityEdgeMap,
  80     class ReverseEdgeMap, class ColorMap, class PredEdgeMap >
  81 typename property_traits< CapacityEdgeMap >::value_type edmonds_karp_max_flow(
  82     Graph& g, typename graph_traits< Graph >::vertex_descriptor src,
  83     typename graph_traits< Graph >::vertex_descriptor sink, CapacityEdgeMap cap,
  84     ResidualCapacityEdgeMap res, ReverseEdgeMap rev, ColorMap color,
  85     PredEdgeMap pred)
  86 {
  87     typedef typename graph_traits< Graph >::vertex_descriptor vertex_t;
  88     typedef typename property_traits< ColorMap >::value_type ColorValue;
  89     typedef color_traits< ColorValue > Color;
  90
  91     typename graph_traits< Graph >::vertex_iterator u_iter, u_end;
  92     typename graph_traits< Graph >::out_edge_iterator ei, e_end;
  93     for (boost::tie(u_iter, u_end) = vertices(g); u_iter != u_end; ++u_iter)
  94         for (boost::tie(ei, e_end) = out_edges(*u_iter, g); ei != e_end; ++ei)
  95             put(res, *ei, get(cap, *ei));
  96
  97     put(color, sink, Color::gray());
  98     while (get(color, sink) != Color::white())
  99     {
 100         boost::queue< vertex_t > Q;
 101         breadth_first_search(detail::residual_graph(g, res), src, Q,
 102             make_bfs_visitor(record_edge_predecessors(pred, on_tree_edge())),
 103             color);
 104         if (get(color, sink) != Color::white())
 105             detail::augment(g, src, sink, pred, res, rev);
 106     } // while
 107
 108     typename property_traits< CapacityEdgeMap >::value_type flow = 0;
 109     for (boost::tie(ei, e_end) = out_edges(src, g); ei != e_end; ++ei)
 110         flow += (get(cap, *ei) - get(res, *ei));
 111     return flow;
 112 } // edmonds_karp_max_flow()
 113
 114 namespace detail
 115 {
 116     //-------------------------------------------------------------------------
 117     // Handle default for color property map
 118
 119     // use of class here is a VC++ workaround
 120     template < class ColorMap > struct edmonds_karp_dispatch2
 121     {
 122         template < class Graph, class PredMap, class P, class T, class R >
 123         static typename edge_capacity_value< Graph, P, T, R >::type apply(
 124             Graph& g, typename graph_traits< Graph >::vertex_descriptor src,
 125             typename graph_traits< Graph >::vertex_descriptor sink,
 126             PredMap pred, const bgl_named_params< P, T, R >& params,
 127             ColorMap color)
 128         {
 129             return edmonds_karp_max_flow(g, src, sink,
 130                 choose_const_pmap(
 131                     get_param(params, edge_capacity), g, edge_capacity),
 132                 choose_pmap(get_param(params, edge_residual_capacity), g,
 133                     edge_residual_capacity),
 134                 choose_const_pmap(
 135                     get_param(params, edge_reverse), g, edge_reverse),
 136                 color, pred);
 137         }
 138     };
 139     template <> struct edmonds_karp_dispatch2< param_not_found >
 140     {
 141         template < class Graph, class PredMap, class P, class T, class R >
 142         static typename edge_capacity_value< Graph, P, T, R >::type apply(
 143             Graph& g, typename graph_traits< Graph >::vertex_descriptor src,
 144             typename graph_traits< Graph >::vertex_descriptor sink,
 145             PredMap pred, const bgl_named_params< P, T, R >& params,
 146             param_not_found)
 147         {
 148             typedef
 149                 typename graph_traits< Graph >::vertices_size_type size_type;
 150             size_type n = is_default_param(get_param(params, vertex_color))
 151                 ? num_vertices(g)
 152                 : 1;
 153             std::vector< default_color_type > color_vec(n);
 154             return edmonds_karp_max_flow(g, src, sink,
 155                 choose_const_pmap(
 156                     get_param(params, edge_capacity), g, edge_capacity),
 157                 choose_pmap(get_param(params, edge_residual_capacity), g,
 158                     edge_residual_capacity),
 159                 choose_const_pmap(
 160                     get_param(params, edge_reverse), g, edge_reverse),
 161                 make_iterator_property_map(color_vec.begin(),
 162                     choose_const_pmap(
 163                         get_param(params, vertex_index), g, vertex_index),
 164                     color_vec[0]),
 165                 pred);
 166         }
 167     };
 168
 169     //-------------------------------------------------------------------------
 170     // Handle default for predecessor property map
 171
 172     // use of class here is a VC++ workaround
 173     template < class PredMap > struct edmonds_karp_dispatch1
 174     {
 175         template < class Graph, class P, class T, class R >
 176         static typename edge_capacity_value< Graph, P, T, R >::type apply(
 177             Graph& g, typename graph_traits< Graph >::vertex_descriptor src,
 178             typename graph_traits< Graph >::vertex_descriptor sink,
 179             const bgl_named_params< P, T, R >& params, PredMap pred)
 180         {
 181             typedef typename get_param_type< vertex_color_t,
 182                 bgl_named_params< P, T, R > >::type C;
 183             return edmonds_karp_dispatch2< C >::apply(
 184                 g, src, sink, pred, params, get_param(params, vertex_color));
 185         }
 186     };
 187     template <> struct edmonds_karp_dispatch1< param_not_found >
 188     {
 189
 190         template < class Graph, class P, class T, class R >
 191         static typename edge_capacity_value< Graph, P, T, R >::type apply(
 192             Graph& g, typename graph_traits< Graph >::vertex_descriptor src,
 193             typename graph_traits< Graph >::vertex_descriptor sink,
 194             const bgl_named_params< P, T, R >& params, param_not_found)
 195         {
 196             typedef
 197                 typename graph_traits< Graph >::edge_descriptor edge_descriptor;
 198             typedef
 199                 typename graph_traits< Graph >::vertices_size_type size_type;
 200             size_type n
 201                 = is_default_param(get_param(params, vertex_predecessor))
 202                 ? num_vertices(g)
 203                 : 1;
 204             std::vector< edge_descriptor > pred_vec(n);
 205
 206             typedef typename get_param_type< vertex_color_t,
 207                 bgl_named_params< P, T, R > >::type C;
 208             return edmonds_karp_dispatch2< C >::apply(g, src, sink,
 209                 make_iterator_property_map(pred_vec.begin(),
 210                     choose_const_pmap(
 211                         get_param(params, vertex_index), g, vertex_index),
 212                     pred_vec[0]),
 213                 params, get_param(params, vertex_color));
 214         }
 215     };
 216
 217 } // namespace detail
 218
 219 template < class Graph, class P, class T, class R >
 220 typename detail::edge_capacity_value< Graph, P, T, R >::type
 221 edmonds_karp_max_flow(Graph& g,
 222     typename graph_traits< Graph >::vertex_descriptor src,
 223     typename graph_traits< Graph >::vertex_descriptor sink,
 224     const bgl_named_params< P, T, R >& params)
 225 {
 226     typedef typename get_param_type< vertex_predecessor_t,
 227         bgl_named_params< P, T, R > >::type Pred;
 228     return detail::edmonds_karp_dispatch1< Pred >::apply(
 229         g, src, sink, params, get_param(params, vertex_predecessor));
 230 }
 231
 232 template < class Graph >
 233 typename property_traits<
 234     typename property_map< Graph, edge_capacity_t >::const_type >::value_type
 235 edmonds_karp_max_flow(Graph& g,
 236     typename graph_traits< Graph >::vertex_descriptor src,
 237     typename graph_traits< Graph >::vertex_descriptor sink)
 238 {
 239     bgl_named_params< int, buffer_param_t > params(0);
 240     return edmonds_karp_max_flow(g, src, sink, params);
 241 }
 242
 243 } // namespace boost
 244
 245 #endif // BOOST_GRAPH_EDMONDS_KARP_MAX_FLOW_HPP