diff -r 666f914201fb -r 2fe1408b6811 epoc32/include/stdapis/boost/graph/edmunds_karp_max_flow.hpp --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/epoc32/include/stdapis/boost/graph/edmunds_karp_max_flow.hpp Tue Mar 16 16:12:26 2010 +0000 @@ -0,0 +1,250 @@ +//======================================================================= +// 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 EDMUNDS_KARP_MAX_FLOW_HPP +#define EDMUNDS_KARP_MAX_FLOW_HPP + +#include +#include +#include // for std::min and std::max +#include +#include +#include +#include +#include +#include +#include + +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 + // Edmunds-Karp algorithm. This solves the maximum flow problem. + + namespace detail { + + template + filtered_graph > + residual_graph(Graph& g, ResCapMap residual_capacity) { + return filtered_graph > + (g, is_residual_edge(residual_capacity)); + } + + template + inline void + augment(Graph& g, + typename graph_traits::vertex_descriptor src, + typename graph_traits::vertex_descriptor sink, + PredEdgeMap p, + ResCapMap residual_capacity, + RevEdgeMap reverse_edge) + { + typename graph_traits::edge_descriptor e; + typename graph_traits::vertex_descriptor u; + typedef typename property_traits::value_type FlowValue; + + // find minimum residual capacity along the augmenting path + FlowValue delta = (std::numeric_limits::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 + typename property_traits::value_type + edmunds_karp_max_flow + (Graph& g, + typename graph_traits::vertex_descriptor src, + typename graph_traits::vertex_descriptor sink, + CapacityEdgeMap cap, + ResidualCapacityEdgeMap res, + ReverseEdgeMap rev, + ColorMap color, + PredEdgeMap pred) + { + typedef typename graph_traits::vertex_descriptor vertex_t; + typedef typename property_traits::value_type ColorValue; + typedef color_traits Color; + + typename graph_traits::vertex_iterator u_iter, u_end; + typename graph_traits::out_edge_iterator ei, e_end; + for (tie(u_iter, u_end) = vertices(g); u_iter != u_end; ++u_iter) + for (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 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::value_type flow = 0; + for (tie(ei, e_end) = out_edges(src, g); ei != e_end; ++ei) + flow += (cap[*ei] - res[*ei]); + return flow; + } // edmunds_karp_max_flow() + + namespace detail { + //------------------------------------------------------------------------- + // Handle default for color property map + + // use of class here is a VC++ workaround + template + struct edmunds_karp_dispatch2 { + template + static typename edge_capacity_value::type + apply + (Graph& g, + typename graph_traits::vertex_descriptor src, + typename graph_traits::vertex_descriptor sink, + PredMap pred, + const bgl_named_params& params, + ColorMap color) + { + return edmunds_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 edmunds_karp_dispatch2 { + template + static typename edge_capacity_value::type + apply + (Graph& g, + typename graph_traits::vertex_descriptor src, + typename graph_traits::vertex_descriptor sink, + PredMap pred, + const bgl_named_params& params, + detail::error_property_not_found) + { + typedef typename graph_traits::edge_descriptor edge_descriptor; + typedef typename graph_traits::vertices_size_type size_type; + size_type n = is_default_param(get_param(params, vertex_color)) ? + num_vertices(g) : 1; + std::vector color_vec(n); + return edmunds_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 + struct edmunds_karp_dispatch1 { + template + static typename edge_capacity_value::type + apply(Graph& g, + typename graph_traits::vertex_descriptor src, + typename graph_traits::vertex_descriptor sink, + const bgl_named_params& params, + PredMap pred) + { + typedef typename property_value< bgl_named_params, vertex_color_t>::type C; + return edmunds_karp_dispatch2::apply + (g, src, sink, pred, params, get_param(params, vertex_color)); + } + }; + template<> + struct edmunds_karp_dispatch1 { + + template + static typename edge_capacity_value::type + apply + (Graph& g, + typename graph_traits::vertex_descriptor src, + typename graph_traits::vertex_descriptor sink, + const bgl_named_params& params, + detail::error_property_not_found) + { + typedef typename graph_traits::edge_descriptor edge_descriptor; + typedef typename graph_traits::vertices_size_type size_type; + size_type n = is_default_param(get_param(params, vertex_predecessor)) ? + num_vertices(g) : 1; + std::vector pred_vec(n); + + typedef typename property_value< bgl_named_params, vertex_color_t>::type C; + return edmunds_karp_dispatch2::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 + typename detail::edge_capacity_value::type + edmunds_karp_max_flow + (Graph& g, + typename graph_traits::vertex_descriptor src, + typename graph_traits::vertex_descriptor sink, + const bgl_named_params& params) + { + typedef typename property_value< bgl_named_params, vertex_predecessor_t>::type Pred; + return detail::edmunds_karp_dispatch1::apply + (g, src, sink, params, get_param(params, vertex_predecessor)); + } + + template + typename property_traits< + typename property_map::const_type + >::value_type + edmunds_karp_max_flow + (Graph& g, + typename graph_traits::vertex_descriptor src, + typename graph_traits::vertex_descriptor sink) + { + bgl_named_params params(0); + return edmunds_karp_max_flow(g, src, sink, params); + } + +} // namespace boost + +#endif // EDMUNDS_KARP_MAX_FLOW_HPP