//======================================================================= | |
// 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 = p[sink]; | |
do { | |
BOOST_USING_STD_MIN(); | |
delta = min BOOST_PREVENT_MACRO_SUBSTITUTION(delta, residual_capacity[e]); | |
u = source(e, g); | |
e = p[u]; | |
} while (u != src); | |
// push delta units of flow along the augmenting path | |
e = p[sink]; | |
do { | |
residual_capacity[e] -= delta; | |
residual_capacity[reverse_edge[e]] += delta; | |
u = source(e, g); | |
e = 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) | |
res[*ei] = cap[*ei]; | |
color[sink] = Color::gray(); | |
while (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 (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 += (cap[*ei] - 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<detail::error_property_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, | |
detail::error_property_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_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 property_value< bgl_named_params<P,T,R>, vertex_color_t>::type C; | |
return edmonds_karp_dispatch2<C>::apply | |
(g, src, sink, pred, params, get_param(params, vertex_color)); | |
} | |
}; | |
template<> | |
struct edmonds_karp_dispatch1<detail::error_property_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, | |
detail::error_property_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 property_value< bgl_named_params<P,T,R>, vertex_color_t>::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 property_value< bgl_named_params<P,T,R>, vertex_predecessor_t>::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 |