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