123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249 |
- //=======================================================================
- // 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
|