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