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