boost/graph/edmonds_karp_max_flow.hpp

0001 //=======================================================================
0002 // Copyright 2000 University of Notre Dame.
0003 // Authors: Jeremy G. Siek, Andrew Lumsdaine, Lie-Quan Lee
0004 //
0005 // Distributed under the Boost Software License, Version 1.0. (See
0006 // accompanying file LICENSE_1_0.txt or copy at
0007 // http://www.boost.org/LICENSE_1_0.txt)
0008 //=======================================================================
0009
0010 #ifndef BOOST_GRAPH_EDMONDS_KARP_MAX_FLOW_HPP
0011 #define BOOST_GRAPH_EDMONDS_KARP_MAX_FLOW_HPP
0012
0013 #include <boost/config.hpp>
0014 #include <vector>
0015 #include <algorithm> // for std::min and std::max
0016 #include <boost/config.hpp>
0017 #include <boost/pending/queue.hpp>
0018 #include <boost/property_map/property_map.hpp>
0019 #include <boost/graph/graph_traits.hpp>
0020 #include <boost/graph/properties.hpp>
0021 #include <boost/graph/filtered_graph.hpp>
0022 #include <boost/graph/breadth_first_search.hpp>
0023
0024 namespace boost
0025 {
0026
0027 // The "labeling" algorithm from "Network Flows" by Ahuja, Magnanti,
0028 // Orlin.  I think this is the same as or very similar to the original
0029 // Edmonds-Karp algorithm.  This solves the maximum flow problem.
0030
0031 namespace detail
0032 {
0033
0034     template < class Graph, class ResCapMap >
0035     filtered_graph< Graph, is_residual_edge< ResCapMap > > residual_graph(
0036         Graph& g, ResCapMap residual_capacity)
0037     {
0038         return filtered_graph< Graph, is_residual_edge< ResCapMap > >(
0039             g, is_residual_edge< ResCapMap >(residual_capacity));
0040     }
0041
0042     template < class Graph, class PredEdgeMap, class ResCapMap,
0043         class RevEdgeMap >
0044     inline void augment(Graph& g,
0045         typename graph_traits< Graph >::vertex_descriptor src,
0046         typename graph_traits< Graph >::vertex_descriptor sink, PredEdgeMap p,
0047         ResCapMap residual_capacity, RevEdgeMap reverse_edge)
0048     {
0049         typename graph_traits< Graph >::edge_descriptor e;
0050         typename graph_traits< Graph >::vertex_descriptor u;
0051         typedef typename property_traits< ResCapMap >::value_type FlowValue;
0052
0053         // find minimum residual capacity along the augmenting path
0054         FlowValue delta = (std::numeric_limits< FlowValue >::max)();
0055         e = get(p, sink);
0056         do
0057         {
0058             BOOST_USING_STD_MIN();
0059             delta = min BOOST_PREVENT_MACRO_SUBSTITUTION(
0060                 delta, get(residual_capacity, e));
0061             u = source(e, g);
0062             e = get(p, u);
0063         } while (u != src);
0064
0065         // push delta units of flow along the augmenting path
0066         e = get(p, sink);
0067         do
0068         {
0069             put(residual_capacity, e, get(residual_capacity, e) - delta);
0070             put(residual_capacity, get(reverse_edge, e),
0071                 get(residual_capacity, get(reverse_edge, e)) + delta);
0072             u = source(e, g);
0073             e = get(p, u);
0074         } while (u != src);
0075     }
0076
0077 } // namespace detail
0078
0079 template < class Graph, class CapacityEdgeMap, class ResidualCapacityEdgeMap,
0080     class ReverseEdgeMap, class ColorMap, class PredEdgeMap >
0081 typename property_traits< CapacityEdgeMap >::value_type edmonds_karp_max_flow(
0082     Graph& g, typename graph_traits< Graph >::vertex_descriptor src,
0083     typename graph_traits< Graph >::vertex_descriptor sink, CapacityEdgeMap cap,
0084     ResidualCapacityEdgeMap res, ReverseEdgeMap rev, ColorMap color,
0085     PredEdgeMap pred)
0086 {
0087     typedef typename graph_traits< Graph >::vertex_descriptor vertex_t;
0088     typedef typename property_traits< ColorMap >::value_type ColorValue;
0089     typedef color_traits< ColorValue > Color;
0090
0091     typename graph_traits< Graph >::vertex_iterator u_iter, u_end;
0092     typename graph_traits< Graph >::out_edge_iterator ei, e_end;
0093     for (boost::tie(u_iter, u_end) = vertices(g); u_iter != u_end; ++u_iter)
0094         for (boost::tie(ei, e_end) = out_edges(*u_iter, g); ei != e_end; ++ei)
0095             put(res, *ei, get(cap, *ei));
0096
0097     put(color, sink, Color::gray());
0098     while (get(color, sink) != Color::white())
0099     {
0100         boost::queue< vertex_t > Q;
0101         breadth_first_search(detail::residual_graph(g, res), src, Q,
0102             make_bfs_visitor(record_edge_predecessors(pred, on_tree_edge())),
0103             color);
0104         if (get(color, sink) != Color::white())
0105             detail::augment(g, src, sink, pred, res, rev);
0106     } // while
0107
0108     typename property_traits< CapacityEdgeMap >::value_type flow = 0;
0109     for (boost::tie(ei, e_end) = out_edges(src, g); ei != e_end; ++ei)
0110         flow += (get(cap, *ei) - get(res, *ei));
0111     return flow;
0112 } // edmonds_karp_max_flow()
0113
0114 namespace detail
0115 {
0116     //-------------------------------------------------------------------------
0117     // Handle default for color property map
0118
0119     // use of class here is a VC++ workaround
0120     template < class ColorMap > struct edmonds_karp_dispatch2
0121     {
0122         template < class Graph, class PredMap, class P, class T, class R >
0123         static typename edge_capacity_value< Graph, P, T, R >::type apply(
0124             Graph& g, typename graph_traits< Graph >::vertex_descriptor src,
0125             typename graph_traits< Graph >::vertex_descriptor sink,
0126             PredMap pred, const bgl_named_params< P, T, R >& params,
0127             ColorMap color)
0128         {
0129             return edmonds_karp_max_flow(g, src, sink,
0130                 choose_const_pmap(
0131                     get_param(params, edge_capacity), g, edge_capacity),
0132                 choose_pmap(get_param(params, edge_residual_capacity), g,
0133                     edge_residual_capacity),
0134                 choose_const_pmap(
0135                     get_param(params, edge_reverse), g, edge_reverse),
0136                 color, pred);
0137         }
0138     };
0139     template <> struct edmonds_karp_dispatch2< param_not_found >
0140     {
0141         template < class Graph, class PredMap, class P, class T, class R >
0142         static typename edge_capacity_value< Graph, P, T, R >::type apply(
0143             Graph& g, typename graph_traits< Graph >::vertex_descriptor src,
0144             typename graph_traits< Graph >::vertex_descriptor sink,
0145             PredMap pred, const bgl_named_params< P, T, R >& params,
0146             param_not_found)
0147         {
0148             typedef
0149                 typename graph_traits< Graph >::vertices_size_type size_type;
0150             size_type n = is_default_param(get_param(params, vertex_color))
0151                 ? num_vertices(g)
0152                 : 1;
0153             std::vector< default_color_type > color_vec(n);
0154             return edmonds_karp_max_flow(g, src, sink,
0155                 choose_const_pmap(
0156                     get_param(params, edge_capacity), g, edge_capacity),
0157                 choose_pmap(get_param(params, edge_residual_capacity), g,
0158                     edge_residual_capacity),
0159                 choose_const_pmap(
0160                     get_param(params, edge_reverse), g, edge_reverse),
0161                 make_iterator_property_map(color_vec.begin(),
0162                     choose_const_pmap(
0163                         get_param(params, vertex_index), g, vertex_index),
0164                     color_vec[0]),
0165                 pred);
0166         }
0167     };
0168
0169     //-------------------------------------------------------------------------
0170     // Handle default for predecessor property map
0171
0172     // use of class here is a VC++ workaround
0173     template < class PredMap > struct edmonds_karp_dispatch1
0174     {
0175         template < class Graph, class P, class T, class R >
0176         static typename edge_capacity_value< Graph, P, T, R >::type apply(
0177             Graph& g, typename graph_traits< Graph >::vertex_descriptor src,
0178             typename graph_traits< Graph >::vertex_descriptor sink,
0179             const bgl_named_params< P, T, R >& params, PredMap pred)
0180         {
0181             typedef typename get_param_type< vertex_color_t,
0182                 bgl_named_params< P, T, R > >::type C;
0183             return edmonds_karp_dispatch2< C >::apply(
0184                 g, src, sink, pred, params, get_param(params, vertex_color));
0185         }
0186     };
0187     template <> struct edmonds_karp_dispatch1< param_not_found >
0188     {
0189
0190         template < class Graph, class P, class T, class R >
0191         static typename edge_capacity_value< Graph, P, T, R >::type apply(
0192             Graph& g, typename graph_traits< Graph >::vertex_descriptor src,
0193             typename graph_traits< Graph >::vertex_descriptor sink,
0194             const bgl_named_params< P, T, R >& params, param_not_found)
0195         {
0196             typedef
0197                 typename graph_traits< Graph >::edge_descriptor edge_descriptor;
0198             typedef
0199                 typename graph_traits< Graph >::vertices_size_type size_type;
0200             size_type n
0201                 = is_default_param(get_param(params, vertex_predecessor))
0202                 ? num_vertices(g)
0203                 : 1;
0204             std::vector< edge_descriptor > pred_vec(n);
0205
0206             typedef typename get_param_type< vertex_color_t,
0207                 bgl_named_params< P, T, R > >::type C;
0208             return edmonds_karp_dispatch2< C >::apply(g, src, sink,
0209                 make_iterator_property_map(pred_vec.begin(),
0210                     choose_const_pmap(
0211                         get_param(params, vertex_index), g, vertex_index),
0212                     pred_vec[0]),
0213                 params, get_param(params, vertex_color));
0214         }
0215     };
0216
0217 } // namespace detail
0218
0219 template < class Graph, class P, class T, class R >
0220 typename detail::edge_capacity_value< Graph, P, T, R >::type
0221 edmonds_karp_max_flow(Graph& g,
0222     typename graph_traits< Graph >::vertex_descriptor src,
0223     typename graph_traits< Graph >::vertex_descriptor sink,
0224     const bgl_named_params< P, T, R >& params)
0225 {
0226     typedef typename get_param_type< vertex_predecessor_t,
0227         bgl_named_params< P, T, R > >::type Pred;
0228     return detail::edmonds_karp_dispatch1< Pred >::apply(
0229         g, src, sink, params, get_param(params, vertex_predecessor));
0230 }
0231
0232 template < class Graph >
0233 typename property_traits<
0234     typename property_map< Graph, edge_capacity_t >::const_type >::value_type
0235 edmonds_karp_max_flow(Graph& g,
0236     typename graph_traits< Graph >::vertex_descriptor src,
0237     typename graph_traits< Graph >::vertex_descriptor sink)
0238 {
0239     bgl_named_params< int, buffer_param_t > params(0);
0240     return edmonds_karp_max_flow(g, src, sink, params);
0241 }
0242
0243 } // namespace boost
0244
0245 #endif // BOOST_GRAPH_EDMONDS_KARP_MAX_FLOW_HPP