1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/epoc32/include/stdapis/boost/graph/edmunds_karp_max_flow.hpp Tue Mar 16 16:12:26 2010 +0000
1.3 @@ -0,0 +1,250 @@
1.4 +//=======================================================================
1.5 +// Copyright 2000 University of Notre Dame.
1.6 +// Authors: Jeremy G. Siek, Andrew Lumsdaine, Lie-Quan Lee
1.7 +//
1.8 +// Distributed under the Boost Software License, Version 1.0. (See
1.9 +// accompanying file LICENSE_1_0.txt or copy at
1.10 +// http://www.boost.org/LICENSE_1_0.txt)
1.11 +//=======================================================================
1.12 +
1.13 +#ifndef EDMUNDS_KARP_MAX_FLOW_HPP
1.14 +#define EDMUNDS_KARP_MAX_FLOW_HPP
1.15 +
1.16 +#include <boost/config.hpp>
1.17 +#include <vector>
1.18 +#include <algorithm> // for std::min and std::max
1.19 +#include <boost/config.hpp>
1.20 +#include <boost/pending/queue.hpp>
1.21 +#include <boost/property_map.hpp>
1.22 +#include <boost/graph/graph_traits.hpp>
1.23 +#include <boost/graph/properties.hpp>
1.24 +#include <boost/graph/filtered_graph.hpp>
1.25 +#include <boost/graph/breadth_first_search.hpp>
1.26 +
1.27 +namespace boost {
1.28 +
1.29 + // The "labeling" algorithm from "Network Flows" by Ahuja, Magnanti,
1.30 + // Orlin. I think this is the same as or very similar to the original
1.31 + // Edmunds-Karp algorithm. This solves the maximum flow problem.
1.32 +
1.33 + namespace detail {
1.34 +
1.35 + template <class Graph, class ResCapMap>
1.36 + filtered_graph<Graph, is_residual_edge<ResCapMap> >
1.37 + residual_graph(Graph& g, ResCapMap residual_capacity) {
1.38 + return filtered_graph<Graph, is_residual_edge<ResCapMap> >
1.39 + (g, is_residual_edge<ResCapMap>(residual_capacity));
1.40 + }
1.41 +
1.42 + template <class Graph, class PredEdgeMap, class ResCapMap,
1.43 + class RevEdgeMap>
1.44 + inline void
1.45 + augment(Graph& g,
1.46 + typename graph_traits<Graph>::vertex_descriptor src,
1.47 + typename graph_traits<Graph>::vertex_descriptor sink,
1.48 + PredEdgeMap p,
1.49 + ResCapMap residual_capacity,
1.50 + RevEdgeMap reverse_edge)
1.51 + {
1.52 + typename graph_traits<Graph>::edge_descriptor e;
1.53 + typename graph_traits<Graph>::vertex_descriptor u;
1.54 + typedef typename property_traits<ResCapMap>::value_type FlowValue;
1.55 +
1.56 + // find minimum residual capacity along the augmenting path
1.57 + FlowValue delta = (std::numeric_limits<FlowValue>::max)();
1.58 + e = p[sink];
1.59 + do {
1.60 + BOOST_USING_STD_MIN();
1.61 + delta = min BOOST_PREVENT_MACRO_SUBSTITUTION(delta, residual_capacity[e]);
1.62 + u = source(e, g);
1.63 + e = p[u];
1.64 + } while (u != src);
1.65 +
1.66 + // push delta units of flow along the augmenting path
1.67 + e = p[sink];
1.68 + do {
1.69 + residual_capacity[e] -= delta;
1.70 + residual_capacity[reverse_edge[e]] += delta;
1.71 + u = source(e, g);
1.72 + e = p[u];
1.73 + } while (u != src);
1.74 + }
1.75 +
1.76 + } // namespace detail
1.77 +
1.78 + template <class Graph,
1.79 + class CapacityEdgeMap, class ResidualCapacityEdgeMap,
1.80 + class ReverseEdgeMap, class ColorMap, class PredEdgeMap>
1.81 + typename property_traits<CapacityEdgeMap>::value_type
1.82 + edmunds_karp_max_flow
1.83 + (Graph& g,
1.84 + typename graph_traits<Graph>::vertex_descriptor src,
1.85 + typename graph_traits<Graph>::vertex_descriptor sink,
1.86 + CapacityEdgeMap cap,
1.87 + ResidualCapacityEdgeMap res,
1.88 + ReverseEdgeMap rev,
1.89 + ColorMap color,
1.90 + PredEdgeMap pred)
1.91 + {
1.92 + typedef typename graph_traits<Graph>::vertex_descriptor vertex_t;
1.93 + typedef typename property_traits<ColorMap>::value_type ColorValue;
1.94 + typedef color_traits<ColorValue> Color;
1.95 +
1.96 + typename graph_traits<Graph>::vertex_iterator u_iter, u_end;
1.97 + typename graph_traits<Graph>::out_edge_iterator ei, e_end;
1.98 + for (tie(u_iter, u_end) = vertices(g); u_iter != u_end; ++u_iter)
1.99 + for (tie(ei, e_end) = out_edges(*u_iter, g); ei != e_end; ++ei)
1.100 + res[*ei] = cap[*ei];
1.101 +
1.102 + color[sink] = Color::gray();
1.103 + while (color[sink] != Color::white()) {
1.104 + boost::queue<vertex_t> Q;
1.105 + breadth_first_search
1.106 + (detail::residual_graph(g, res), src, Q,
1.107 + make_bfs_visitor(record_edge_predecessors(pred, on_tree_edge())),
1.108 + color);
1.109 + if (color[sink] != Color::white())
1.110 + detail::augment(g, src, sink, pred, res, rev);
1.111 + } // while
1.112 +
1.113 + typename property_traits<CapacityEdgeMap>::value_type flow = 0;
1.114 + for (tie(ei, e_end) = out_edges(src, g); ei != e_end; ++ei)
1.115 + flow += (cap[*ei] - res[*ei]);
1.116 + return flow;
1.117 + } // edmunds_karp_max_flow()
1.118 +
1.119 + namespace detail {
1.120 + //-------------------------------------------------------------------------
1.121 + // Handle default for color property map
1.122 +
1.123 + // use of class here is a VC++ workaround
1.124 + template <class ColorMap>
1.125 + struct edmunds_karp_dispatch2 {
1.126 + template <class Graph, class PredMap, class P, class T, class R>
1.127 + static typename edge_capacity_value<Graph, P, T, R>::type
1.128 + apply
1.129 + (Graph& g,
1.130 + typename graph_traits<Graph>::vertex_descriptor src,
1.131 + typename graph_traits<Graph>::vertex_descriptor sink,
1.132 + PredMap pred,
1.133 + const bgl_named_params<P, T, R>& params,
1.134 + ColorMap color)
1.135 + {
1.136 + return edmunds_karp_max_flow
1.137 + (g, src, sink,
1.138 + choose_const_pmap(get_param(params, edge_capacity), g, edge_capacity),
1.139 + choose_pmap(get_param(params, edge_residual_capacity),
1.140 + g, edge_residual_capacity),
1.141 + choose_const_pmap(get_param(params, edge_reverse), g, edge_reverse),
1.142 + color, pred);
1.143 + }
1.144 + };
1.145 + template<>
1.146 + struct edmunds_karp_dispatch2<detail::error_property_not_found> {
1.147 + template <class Graph, class PredMap, class P, class T, class R>
1.148 + static typename edge_capacity_value<Graph, P, T, R>::type
1.149 + apply
1.150 + (Graph& g,
1.151 + typename graph_traits<Graph>::vertex_descriptor src,
1.152 + typename graph_traits<Graph>::vertex_descriptor sink,
1.153 + PredMap pred,
1.154 + const bgl_named_params<P, T, R>& params,
1.155 + detail::error_property_not_found)
1.156 + {
1.157 + typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor;
1.158 + typedef typename graph_traits<Graph>::vertices_size_type size_type;
1.159 + size_type n = is_default_param(get_param(params, vertex_color)) ?
1.160 + num_vertices(g) : 1;
1.161 + std::vector<default_color_type> color_vec(n);
1.162 + return edmunds_karp_max_flow
1.163 + (g, src, sink,
1.164 + choose_const_pmap(get_param(params, edge_capacity), g, edge_capacity),
1.165 + choose_pmap(get_param(params, edge_residual_capacity),
1.166 + g, edge_residual_capacity),
1.167 + choose_const_pmap(get_param(params, edge_reverse), g, edge_reverse),
1.168 + make_iterator_property_map(color_vec.begin(), choose_const_pmap
1.169 + (get_param(params, vertex_index),
1.170 + g, vertex_index), color_vec[0]),
1.171 + pred);
1.172 + }
1.173 + };
1.174 +
1.175 + //-------------------------------------------------------------------------
1.176 + // Handle default for predecessor property map
1.177 +
1.178 + // use of class here is a VC++ workaround
1.179 + template <class PredMap>
1.180 + struct edmunds_karp_dispatch1 {
1.181 + template <class Graph, class P, class T, class R>
1.182 + static typename edge_capacity_value<Graph, P, T, R>::type
1.183 + apply(Graph& g,
1.184 + typename graph_traits<Graph>::vertex_descriptor src,
1.185 + typename graph_traits<Graph>::vertex_descriptor sink,
1.186 + const bgl_named_params<P, T, R>& params,
1.187 + PredMap pred)
1.188 + {
1.189 + typedef typename property_value< bgl_named_params<P,T,R>, vertex_color_t>::type C;
1.190 + return edmunds_karp_dispatch2<C>::apply
1.191 + (g, src, sink, pred, params, get_param(params, vertex_color));
1.192 + }
1.193 + };
1.194 + template<>
1.195 + struct edmunds_karp_dispatch1<detail::error_property_not_found> {
1.196 +
1.197 + template <class Graph, class P, class T, class R>
1.198 + static typename edge_capacity_value<Graph, P, T, R>::type
1.199 + apply
1.200 + (Graph& g,
1.201 + typename graph_traits<Graph>::vertex_descriptor src,
1.202 + typename graph_traits<Graph>::vertex_descriptor sink,
1.203 + const bgl_named_params<P, T, R>& params,
1.204 + detail::error_property_not_found)
1.205 + {
1.206 + typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor;
1.207 + typedef typename graph_traits<Graph>::vertices_size_type size_type;
1.208 + size_type n = is_default_param(get_param(params, vertex_predecessor)) ?
1.209 + num_vertices(g) : 1;
1.210 + std::vector<edge_descriptor> pred_vec(n);
1.211 +
1.212 + typedef typename property_value< bgl_named_params<P,T,R>, vertex_color_t>::type C;
1.213 + return edmunds_karp_dispatch2<C>::apply
1.214 + (g, src, sink,
1.215 + make_iterator_property_map(pred_vec.begin(), choose_const_pmap
1.216 + (get_param(params, vertex_index),
1.217 + g, vertex_index), pred_vec[0]),
1.218 + params,
1.219 + get_param(params, vertex_color));
1.220 + }
1.221 + };
1.222 +
1.223 + } // namespace detail
1.224 +
1.225 + template <class Graph, class P, class T, class R>
1.226 + typename detail::edge_capacity_value<Graph, P, T, R>::type
1.227 + edmunds_karp_max_flow
1.228 + (Graph& g,
1.229 + typename graph_traits<Graph>::vertex_descriptor src,
1.230 + typename graph_traits<Graph>::vertex_descriptor sink,
1.231 + const bgl_named_params<P, T, R>& params)
1.232 + {
1.233 + typedef typename property_value< bgl_named_params<P,T,R>, vertex_predecessor_t>::type Pred;
1.234 + return detail::edmunds_karp_dispatch1<Pred>::apply
1.235 + (g, src, sink, params, get_param(params, vertex_predecessor));
1.236 + }
1.237 +
1.238 + template <class Graph>
1.239 + typename property_traits<
1.240 + typename property_map<Graph, edge_capacity_t>::const_type
1.241 + >::value_type
1.242 + edmunds_karp_max_flow
1.243 + (Graph& g,
1.244 + typename graph_traits<Graph>::vertex_descriptor src,
1.245 + typename graph_traits<Graph>::vertex_descriptor sink)
1.246 + {
1.247 + bgl_named_params<int, buffer_param_t> params(0);
1.248 + return edmunds_karp_max_flow(g, src, sink, params);
1.249 + }
1.250 +
1.251 +} // namespace boost
1.252 +
1.253 +#endif // EDMUNDS_KARP_MAX_FLOW_HPP