boost/graph/edmonds_karp_max_flow.hpp
//======================================================================= // Copyright 2000 University of Notre Dame. // Authors: Jeremy G. Siek, Andrew Lumsdaine, Lie-Quan Lee // // Distributed under the Boost Software License, Version 1.0. (See // accompanying file LICENSE_1_0.txt or copy at // http://www.boost.org/LICENSE_1_0.txt) //======================================================================= #ifndef EDMONDS_KARP_MAX_FLOW_HPP #define EDMONDS_KARP_MAX_FLOW_HPP #include <boost/config.hpp> #include <vector> #include <algorithm> // for std::min and std::max #include <boost/config.hpp> #include <boost/pending/queue.hpp> #include <boost/property_map/property_map.hpp> #include <boost/graph/graph_traits.hpp> #include <boost/graph/properties.hpp> #include <boost/graph/filtered_graph.hpp> #include <boost/graph/breadth_first_search.hpp> namespace boost { // The "labeling" algorithm from "Network Flows" by Ahuja, Magnanti, // Orlin. I think this is the same as or very similar to the original // Edmonds-Karp algorithm. This solves the maximum flow problem. namespace detail { template <class Graph, class ResCapMap> filtered_graph<Graph, is_residual_edge<ResCapMap> > residual_graph(Graph& g, ResCapMap residual_capacity) { return filtered_graph<Graph, is_residual_edge<ResCapMap> > (g, is_residual_edge<ResCapMap>(residual_capacity)); } template <class Graph, class PredEdgeMap, class ResCapMap, class RevEdgeMap> inline void augment(Graph& g, typename graph_traits<Graph>::vertex_descriptor src, typename graph_traits<Graph>::vertex_descriptor sink, PredEdgeMap p, ResCapMap residual_capacity, RevEdgeMap reverse_edge) { typename graph_traits<Graph>::edge_descriptor e; typename graph_traits<Graph>::vertex_descriptor u; typedef typename property_traits<ResCapMap>::value_type FlowValue; // find minimum residual capacity along the augmenting path FlowValue delta = (std::numeric_limits<FlowValue>::max)(); e = get(p, sink); do { BOOST_USING_STD_MIN(); delta = min BOOST_PREVENT_MACRO_SUBSTITUTION(delta, get(residual_capacity, e)); u = source(e, g); e = get(p, u); } while (u != src); // push delta units of flow along the augmenting path e = get(p, sink); do { put(residual_capacity, e, get(residual_capacity, e) - delta); put(residual_capacity, get(reverse_edge, e), get(residual_capacity, get(reverse_edge, e)) + delta); u = source(e, g); e = get(p, u); } while (u != src); } } // namespace detail template <class Graph, class CapacityEdgeMap, class ResidualCapacityEdgeMap, class ReverseEdgeMap, class ColorMap, class PredEdgeMap> typename property_traits<CapacityEdgeMap>::value_type edmonds_karp_max_flow (Graph& g, typename graph_traits<Graph>::vertex_descriptor src, typename graph_traits<Graph>::vertex_descriptor sink, CapacityEdgeMap cap, ResidualCapacityEdgeMap res, ReverseEdgeMap rev, ColorMap color, PredEdgeMap pred) { typedef typename graph_traits<Graph>::vertex_descriptor vertex_t; typedef typename property_traits<ColorMap>::value_type ColorValue; typedef color_traits<ColorValue> Color; typename graph_traits<Graph>::vertex_iterator u_iter, u_end; typename graph_traits<Graph>::out_edge_iterator ei, e_end; for (boost::tie(u_iter, u_end) = vertices(g); u_iter != u_end; ++u_iter) for (boost::tie(ei, e_end) = out_edges(*u_iter, g); ei != e_end; ++ei) put(res, *ei, get(cap, *ei)); put(color, sink, Color::gray()); while (get(color, sink) != Color::white()) { boost::queue<vertex_t> Q; breadth_first_search (detail::residual_graph(g, res), src, Q, make_bfs_visitor(record_edge_predecessors(pred, on_tree_edge())), color); if (get(color, sink) != Color::white()) detail::augment(g, src, sink, pred, res, rev); } // while typename property_traits<CapacityEdgeMap>::value_type flow = 0; for (boost::tie(ei, e_end) = out_edges(src, g); ei != e_end; ++ei) flow += (get(cap, *ei) - get(res, *ei)); return flow; } // edmonds_karp_max_flow() namespace detail { //------------------------------------------------------------------------- // Handle default for color property map // use of class here is a VC++ workaround template <class ColorMap> struct edmonds_karp_dispatch2 { template <class Graph, class PredMap, class P, class T, class R> static typename edge_capacity_value<Graph, P, T, R>::type apply (Graph& g, typename graph_traits<Graph>::vertex_descriptor src, typename graph_traits<Graph>::vertex_descriptor sink, PredMap pred, const bgl_named_params<P, T, R>& params, ColorMap color) { return edmonds_karp_max_flow (g, src, sink, choose_const_pmap(get_param(params, edge_capacity), g, edge_capacity), choose_pmap(get_param(params, edge_residual_capacity), g, edge_residual_capacity), choose_const_pmap(get_param(params, edge_reverse), g, edge_reverse), color, pred); } }; template<> struct edmonds_karp_dispatch2<param_not_found> { template <class Graph, class PredMap, class P, class T, class R> static typename edge_capacity_value<Graph, P, T, R>::type apply (Graph& g, typename graph_traits<Graph>::vertex_descriptor src, typename graph_traits<Graph>::vertex_descriptor sink, PredMap pred, const bgl_named_params<P, T, R>& params, param_not_found) { typedef typename graph_traits<Graph>::vertices_size_type size_type; size_type n = is_default_param(get_param(params, vertex_color)) ? num_vertices(g) : 1; std::vector<default_color_type> color_vec(n); return edmonds_karp_max_flow (g, src, sink, choose_const_pmap(get_param(params, edge_capacity), g, edge_capacity), choose_pmap(get_param(params, edge_residual_capacity), g, edge_residual_capacity), choose_const_pmap(get_param(params, edge_reverse), g, edge_reverse), make_iterator_property_map(color_vec.begin(), choose_const_pmap (get_param(params, vertex_index), g, vertex_index), color_vec[0]), pred); } }; //------------------------------------------------------------------------- // Handle default for predecessor property map // use of class here is a VC++ workaround template <class PredMap> struct edmonds_karp_dispatch1 { template <class Graph, class P, class T, class R> static typename edge_capacity_value<Graph, P, T, R>::type apply(Graph& g, typename graph_traits<Graph>::vertex_descriptor src, typename graph_traits<Graph>::vertex_descriptor sink, const bgl_named_params<P, T, R>& params, PredMap pred) { typedef typename get_param_type< vertex_color_t, bgl_named_params<P,T,R> >::type C; return edmonds_karp_dispatch2<C>::apply (g, src, sink, pred, params, get_param(params, vertex_color)); } }; template<> struct edmonds_karp_dispatch1<param_not_found> { template <class Graph, class P, class T, class R> static typename edge_capacity_value<Graph, P, T, R>::type apply (Graph& g, typename graph_traits<Graph>::vertex_descriptor src, typename graph_traits<Graph>::vertex_descriptor sink, const bgl_named_params<P, T, R>& params, param_not_found) { typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor; typedef typename graph_traits<Graph>::vertices_size_type size_type; size_type n = is_default_param(get_param(params, vertex_predecessor)) ? num_vertices(g) : 1; std::vector<edge_descriptor> pred_vec(n); typedef typename get_param_type< vertex_color_t, bgl_named_params<P,T,R> >::type C; return edmonds_karp_dispatch2<C>::apply (g, src, sink, make_iterator_property_map(pred_vec.begin(), choose_const_pmap (get_param(params, vertex_index), g, vertex_index), pred_vec[0]), params, get_param(params, vertex_color)); } }; } // namespace detail template <class Graph, class P, class T, class R> typename detail::edge_capacity_value<Graph, P, T, R>::type edmonds_karp_max_flow (Graph& g, typename graph_traits<Graph>::vertex_descriptor src, typename graph_traits<Graph>::vertex_descriptor sink, const bgl_named_params<P, T, R>& params) { typedef typename get_param_type< vertex_predecessor_t, bgl_named_params<P,T,R> >::type Pred; return detail::edmonds_karp_dispatch1<Pred>::apply (g, src, sink, params, get_param(params, vertex_predecessor)); } template <class Graph> typename property_traits< typename property_map<Graph, edge_capacity_t>::const_type >::value_type edmonds_karp_max_flow (Graph& g, typename graph_traits<Graph>::vertex_descriptor src, typename graph_traits<Graph>::vertex_descriptor sink) { bgl_named_params<int, buffer_param_t> params(0); return edmonds_karp_max_flow(g, src, sink, params); } } // namespace boost #endif // EDMONDS_KARP_MAX_FLOW_HPP