From: kbelco_at_[hidden]
Date: 2008-01-26 13:36:00
Author: noel_belcourt
Date: 2008-01-26 13:35:59 EST (Sat, 26 Jan 2008)
New Revision: 42984
URL: http://svn.boost.org/trac/boost/changeset/42984
Log:
Fixes #416
Fixed spelling of Jack Edmonds name and renamed files
where necessary. Updated the documentation as well.
Tested changes by building/running tests in libs/graph/test.
Added:
trunk/boost/graph/edmonds_karp_max_flow.hpp (contents, props changed)
trunk/libs/graph/doc/edmonds_karp_max_flow.html (contents, props changed)
trunk/libs/graph/example/edmonds-karp-eg.cpp (contents, props changed)
Removed:
trunk/boost/graph/edmunds_karp_max_flow.hpp
trunk/libs/graph/doc/edmunds_karp_max_flow.html
trunk/libs/graph/example/edmunds-karp-eg.cpp
Text files modified:
trunk/boost/graph/edge_connectivity.hpp | 4 ++--
trunk/libs/graph/doc/kolmogorov_max_flow.html | 2 +-
trunk/libs/graph/doc/push_relabel_max_flow.html | 2 +-
trunk/libs/graph/example/edge-connectivity.cpp | 4 ++--
trunk/libs/graph/example/regression.cfg | 2 +-
trunk/libs/graph/test/max_flow_test.cpp | 6 +++---
6 files changed, 10 insertions(+), 10 deletions(-)
Modified: trunk/boost/graph/edge_connectivity.hpp
==============================================================================
--- trunk/boost/graph/edge_connectivity.hpp (original)
+++ trunk/boost/graph/edge_connectivity.hpp 2008-01-26 13:35:59 EST (Sat, 26 Jan 2008)
@@ -16,7 +16,7 @@
#include <vector>
#include <set>
#include <algorithm>
-#include <boost/graph/edmunds_karp_max_flow.hpp>
+#include <boost/graph/edmonds_karp_max_flow.hpp>
namespace boost {
@@ -139,7 +139,7 @@
while (!non_neighbor_S.empty()) { // at most n - 1 times
k = non_neighbor_S.front();
- alpha_S_k = edmunds_karp_max_flow
+ alpha_S_k = edmonds_karp_max_flow
(flow_g, p, k, cap, res_cap, rev_edge, &color[0], &pred[0]);
if (alpha_S_k < alpha_star) {
Added: trunk/boost/graph/edmonds_karp_max_flow.hpp
==============================================================================
--- (empty file)
+++ trunk/boost/graph/edmonds_karp_max_flow.hpp 2008-01-26 13:35:59 EST (Sat, 26 Jan 2008)
@@ -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 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.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 (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<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 (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
Deleted: trunk/boost/graph/edmunds_karp_max_flow.hpp
==============================================================================
--- trunk/boost/graph/edmunds_karp_max_flow.hpp 2008-01-26 13:35:59 EST (Sat, 26 Jan 2008)
+++ (empty file)
@@ -1,250 +0,0 @@
-//=======================================================================
-// 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 <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.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
- // Edmunds-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
- edmunds_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 (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<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 (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 <class ColorMap>
- struct edmunds_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 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<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 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 <class PredMap>
- struct edmunds_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 edmunds_karp_dispatch2<C>::apply
- (g, src, sink, pred, params, get_param(params, vertex_color));
- }
- };
- template<>
- struct edmunds_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 edmunds_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
- edmunds_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::edmunds_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
- edmunds_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 edmunds_karp_max_flow(g, src, sink, params);
- }
-
-} // namespace boost
-
-#endif // EDMUNDS_KARP_MAX_FLOW_HPP
Added: trunk/libs/graph/doc/edmonds_karp_max_flow.html
==============================================================================
--- (empty file)
+++ trunk/libs/graph/doc/edmonds_karp_max_flow.html 2008-01-26 13:35:59 EST (Sat, 26 Jan 2008)
@@ -0,0 +1,247 @@
+<HTML>
+<!--
+ -- Copyright (c) Jeremy Siek 2000
+ --
+ -- 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)
+ -->
+<Head>
+<Title>Boost Graph Library: Edmonds-Karp Maximum Flow</Title>
+<BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b"
+ ALINK="#ff0000">
+<IMG SRC="../../../boost.png"
+ ALT="C++ Boost" width="277" height="86">
+
+<BR Clear>
+
+<H1><A NAME="sec:edmonds_karp_max_flow">
+<TT>edmonds_karp_max_flow</TT>
+</H1>
+
+<PRE>
+<i>// named paramter version</i>
+template <class Graph, class P, class T, class R>
+typename detail::edge_capacity_value<Graph, P, T, R>::value_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 = <i>all defaults</i>)
+
+<i>// non-named parameter version</i>
+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)
+</PRE>
+
+<P>
+The <tt>edmonds_karp_max_flow()</tt> function calculates the maximum flow
+of a network. See Section <a
+href="./graph_theory_review.html#sec:network-flow-algorithms">Network
+Flow Algorithms</a> for a description of maximum flow. The calculated
+maximum flow will be the return value of the function. The function
+also calculates the flow values <i>f(u,v)</i> for all <i>(u,v)</i> in
+<i>E</i>, which are returned in the form of the residual capacity
+<i>r(u,v) = c(u,v) - f(u,v)</i>.
+
+<p>
+There are several special requirements on the input graph and property
+map parameters for this algorithm. First, the directed graph
+<i>G=(V,E)</i> that represents the network must be augmented to
+include the reverse edge for every edge in <i>E</i>. That is, the
+input graph should be <i>G<sub>in</sub> = (V,{E U
+E<sup>T</sup>})</i>. The <tt>ReverseEdgeMap</tt> argument <tt>rev</tt>
+must map each edge in the original graph to its reverse edge, that is
+<i>(u,v) -> (v,u)</i> for all <i>(u,v)</i> in <i>E</i>. The
+<tt>CapacityEdgeMap</tt> argument <tt>cap</tt> must map each edge in
+<i>E</i> to a positive number, and each edge in <i>E<sup>T</sup></i>
+to 0.
+
+<p>
+The algorithm is due to <a
+href="./bibliography.html#edmonds72:_improvements_netflow">Edmonds and
+Karp</a>, though we are using the variation called the ``labeling
+algorithm'' described in <a
+href="./bibliography.html#ahuja93:_network_flows">Network Flows</a>.
+
+<p>
+This algorithm provides a very simple and easy to implement solution to
+the maximum flow problem. However, there are several reasons why this
+algorithm is not as good as the <a
+href="./push_relabel_max_flow.html"><tt>push_relabel_max_flow()</tt></a>
+or the <a
+href="./kolmogorov_max_flow.html"><tt>kolmogorov_max_flow()</tt></a>
+algorithm.
+
+<ul>
+ <li>In the non-integer capacity case, the time complexity is <i>O(V
+ E<sup>2</sup>)</i> which is worse than the time complexity of the
+ push-relabel algorithm <i>O(V<sup>2</sup>E<sup>1/2</sup>)</i>
+ for all but the sparsest of graphs.</li>
+
+ <li>In the integer capacity case, if the capacity bound <i>U</i> is
+ very large then the algorithm will take a long time.</li>
+</ul>
+
+
+<H3>Where Defined</H3>
+
+<P>
+boost/graph/edmonds_karp_max_flow.hpp
+
+<P>
+
+<h3>Parameters</h3>
+
+IN: <tt>Graph& g</tt>
+<blockquote>
+ A directed graph. The
+ graph's type must be a model of <a
+ href="./VertexListGraph.html">VertexListGraph</a> and IncidenceGraph For each edge
+ <i>(u,v)</i> in the graph, the reverse edge <i>(v,u)</i> must also
+ be in the graph.
+</blockquote>
+
+IN: <tt>vertex_descriptor src</tt>
+<blockquote>
+ The source vertex for the flow network graph.
+</blockquote>
+
+IN: <tt>vertex_descriptor sink</tt>
+<blockquote>
+ The sink vertex for the flow network graph.
+</blockquote>
+
+<h3>Named Parameters</h3>
+
+
+IN: <tt>capacity_map(CapacityEdgeMap cap)</tt>
+<blockquote>
+ The edge capacity property map. The type must be a model of a
+ constant <a
+ href="../../property_map/LvaluePropertyMap.html">Lvalue Property Map</a>. The
+ key type of the map must be the graph's edge descriptor type.<br>
+ <b>Default:</b> <tt>get(edge_capacity, g)</tt>
+</blockquote>
+
+OUT: <tt>residual_capacity_map(ResidualCapacityEdgeMap res)</tt>
+<blockquote>
+ This maps edges to their residual capacity. The type must be a model
+ of a mutable <a
+ href="../../property_map/LvaluePropertyMap.html">Lvalue Property
+ Map</a>. The key type of the map must be the graph's edge descriptor
+ type.<br>
+ <b>Default:</b> <tt>get(edge_residual_capacity, g)</tt>
+</blockquote>
+
+IN: <tt>reverse_edge_map(ReverseEdgeMap rev)</tt>
+<blockquote>
+ An edge property map that maps every edge <i>(u,v)</i> in the graph
+ to the reverse edge <i>(v,u)</i>. The map must be a model of
+ constant <a href="../../property_map/LvaluePropertyMap.html">Lvalue
+ Property Map</a>. The key type of the map must be the graph's edge
+ descriptor type.<br>
+ <b>Default:</b> <tt>get(edge_reverse, g)</tt>
+</blockquote>
+
+UTIL: <tt>color_map(ColorMap color)</tt>
+<blockquote>
+ Used by the algorithm to keep track of progress during the
+ breadth-first search stage. At the end of the algorithm, the white
+ vertices define the minimum cut set. The map must be a model of
+ mutable <a
+ href="../../property_map/LvaluePropertyMap.html">Lvalue Property Map</a>.
+ The key type of the map should be the graph's vertex descriptor type, and
+ the value type must be a model of <a
+ href="./ColorValue.html">ColorValue</a>.<br>
+
+ <b>Default:</b> an <a
+ href="../../property_map/iterator_property_map.html">
+ <tt>iterator_property_map</tt></a> created from a <tt>std::vector</tt>
+ of <tt>default_color_type</tt> of size <tt>num_vertices(g)</tt> and
+ using the <tt>i_map</tt> for the index map.
+</blockquote>
+
+UTIL: <tt>predecessor_map(PredEdgeMap pred)</tt>
+<blockquote>
+ Use by the algorithm to store augmenting paths. The map must be a
+ model of mutable <a
+ href="../../property_map/LvaluePropertyMap.html">Lvalue Property Map</a>.
+ The key type must be the graph's vertex descriptor type and the
+ value type must be the graph's edge descriptor type.<br>
+
+ <b>Default:</b> an <a
+ href="../../property_map/iterator_property_map.html">
+ <tt>iterator_property_map</tt></a> created from a <tt>std::vector</tt>
+ of edge descriptors of size <tt>num_vertices(g)</tt> and
+ using the <tt>i_map</tt> for the index map.
+</blockquote>
+
+IN: <tt>vertex_index_map(VertexIndexMap i_map)</tt>
+<blockquote>
+ Maps each vertex of the graph to a unique integer in the range
+ <tt>[0, num_vertices(g))</tt>. This property map is only needed
+ if the default for the color or predecessor map is used.
+ The vertex index map must be a model of <a
+ href="../../property_map/ReadablePropertyMap.html">Readable Property
+ Map</a>. The key type of the map must be the graph's vertex
+ descriptor type.<br>
+ <b>Default:</b> <tt>get(vertex_index, g)</tt>
+ Note: if you use this default, make sure your graph has
+ an internal <tt>vertex_index</tt> property. For example,
+ <tt>adjacenty_list</tt> with <tt>VertexList=listS</tt> does
+ not have an internal <tt>vertex_index</tt> property.
+</blockquote>
+
+
+<h3>Complexity</h3>
+
+The time complexity is <i>O(V E<sup>2</sup>)</i> in the general case
+or <i>O(V E U)</i> if capacity values are integers bounded by
+some constant <i>U</i>.
+
+<h3>Example</h3>
+
+The program in <a
+href="../example/edmonds-karp-eg.cpp"><tt>example/edmonds-karp-eg.cpp</tt></a>
+reads an example maximum flow problem (a graph with edge capacities)
+from a file in the DIMACS format and computes the maximum flow.
+
+
+<h3>See Also</h3>
+
+push_relabel_max_flow()<br>
+kolmogorov_max_flow().
+
+<br>
+<HR>
+<TABLE>
+<TR valign=top>
+<TD nowrap>Copyright © 2000-2001</TD><TD>
+<A HREF="../../../people/jeremy_siek.htm">Jeremy Siek</A>, Indiana University (<A HREF="mailto:jsiek_at_[hidden]">jsiek_at_[hidden]</A>)
+</TD></TR></TABLE>
+
+</BODY>
+</HTML>
+<!-- LocalWords: HTML Siek Edmonds BGCOLOR ffffff ee VLINK ALINK ff IMG SRC
+ -->
+<!-- LocalWords: gif ALT BR sec edmonds karp TT DIV CELLPADDING TR TD PRE lt
+ -->
+<!-- LocalWords: typename VertexListGraph CapacityEdgeMap ReverseEdgeMap gt
+ -->
+<!-- LocalWords: ResidualCapacityEdgeMap VertexIndexMap src rev ColorMap pred
+ -->
+<!-- LocalWords: PredEdgeMap tt href html hpp ul li nbsp br LvaluePropertyMap
+ -->
+<!-- LocalWords: num ColorValue DIMACS cpp pre config iostream dimacs int std
+ -->
+<!-- LocalWords: namespace vecS directedS cout endl iter ei HR valign nowrap
+ -->
+<!-- LocalWords: jeremy siek htm Univ mailto jsiek lsc edu
+p -->
Deleted: trunk/libs/graph/doc/edmunds_karp_max_flow.html
==============================================================================
--- trunk/libs/graph/doc/edmunds_karp_max_flow.html 2008-01-26 13:35:59 EST (Sat, 26 Jan 2008)
+++ (empty file)
@@ -1,247 +0,0 @@
-<HTML>
-<!--
- -- Copyright (c) Jeremy Siek 2000
- --
- -- 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)
- -->
-<Head>
-<Title>Boost Graph Library: Edmunds-Karp Maximum Flow</Title>
-<BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b"
- ALINK="#ff0000">
-<IMG SRC="../../../boost.png"
- ALT="C++ Boost" width="277" height="86">
-
-<BR Clear>
-
-<H1><A NAME="sec:edmunds_karp_max_flow">
-<TT>edmunds_karp_max_flow</TT>
-</H1>
-
-<PRE>
-<i>// named paramter version</i>
-template <class Graph, class P, class T, class R>
-typename detail::edge_capacity_value<Graph, P, T, R>::value_type
-edmunds_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 = <i>all defaults</i>)
-
-<i>// non-named parameter version</i>
-template <class Graph,
- class CapacityEdgeMap, class ResidualCapacityEdgeMap,
- class ReverseEdgeMap, class ColorMap, class PredEdgeMap>
-typename property_traits<CapacityEdgeMap>::value_type
-edmunds_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)
-</PRE>
-
-<P>
-The <tt>edmunds_karp_max_flow()</tt> function calculates the maximum flow
-of a network. See Section <a
-href="./graph_theory_review.html#sec:network-flow-algorithms">Network
-Flow Algorithms</a> for a description of maximum flow. The calculated
-maximum flow will be the return value of the function. The function
-also calculates the flow values <i>f(u,v)</i> for all <i>(u,v)</i> in
-<i>E</i>, which are returned in the form of the residual capacity
-<i>r(u,v) = c(u,v) - f(u,v)</i>.
-
-<p>
-There are several special requirements on the input graph and property
-map parameters for this algorithm. First, the directed graph
-<i>G=(V,E)</i> that represents the network must be augmented to
-include the reverse edge for every edge in <i>E</i>. That is, the
-input graph should be <i>G<sub>in</sub> = (V,{E U
-E<sup>T</sup>})</i>. The <tt>ReverseEdgeMap</tt> argument <tt>rev</tt>
-must map each edge in the original graph to its reverse edge, that is
-<i>(u,v) -> (v,u)</i> for all <i>(u,v)</i> in <i>E</i>. The
-<tt>CapacityEdgeMap</tt> argument <tt>cap</tt> must map each edge in
-<i>E</i> to a positive number, and each edge in <i>E<sup>T</sup></i>
-to 0.
-
-<p>
-The algorithm is due to <a
-href="./bibliography.html#edmonds72:_improvements_netflow">Edmonds and
-Karp</a>, though we are using the variation called the ``labeling
-algorithm'' described in <a
-href="./bibliography.html#ahuja93:_network_flows">Network Flows</a>.
-
-<p>
-This algorithm provides a very simple and easy to implement solution to
-the maximum flow problem. However, there are several reasons why this
-algorithm is not as good as the <a
-href="./push_relabel_max_flow.html"><tt>push_relabel_max_flow()</tt></a>
-or the <a
-href="./kolmogorov_max_flow.html"><tt>kolmogorov_max_flow()</tt></a>
-algorithm.
-
-<ul>
- <li>In the non-integer capacity case, the time complexity is <i>O(V
- E<sup>2</sup>)</i> which is worse than the time complexity of the
- push-relabel algorithm <i>O(V<sup>2</sup>E<sup>1/2</sup>)</i>
- for all but the sparsest of graphs.</li>
-
- <li>In the integer capacity case, if the capacity bound <i>U</i> is
- very large then the algorithm will take a long time.</li>
-</ul>
-
-
-<H3>Where Defined</H3>
-
-<P>
-boost/graph/edmunds_karp_max_flow.hpp
-
-<P>
-
-<h3>Parameters</h3>
-
-IN: <tt>Graph& g</tt>
-<blockquote>
- A directed graph. The
- graph's type must be a model of <a
- href="./VertexListGraph.html">VertexListGraph</a> and IncidenceGraph For each edge
- <i>(u,v)</i> in the graph, the reverse edge <i>(v,u)</i> must also
- be in the graph.
-</blockquote>
-
-IN: <tt>vertex_descriptor src</tt>
-<blockquote>
- The source vertex for the flow network graph.
-</blockquote>
-
-IN: <tt>vertex_descriptor sink</tt>
-<blockquote>
- The sink vertex for the flow network graph.
-</blockquote>
-
-<h3>Named Parameters</h3>
-
-
-IN: <tt>capacity_map(CapacityEdgeMap cap)</tt>
-<blockquote>
- The edge capacity property map. The type must be a model of a
- constant <a
- href="../../property_map/LvaluePropertyMap.html">Lvalue Property Map</a>. The
- key type of the map must be the graph's edge descriptor type.<br>
- <b>Default:</b> <tt>get(edge_capacity, g)</tt>
-</blockquote>
-
-OUT: <tt>residual_capacity_map(ResidualCapacityEdgeMap res)</tt>
-<blockquote>
- This maps edges to their residual capacity. The type must be a model
- of a mutable <a
- href="../../property_map/LvaluePropertyMap.html">Lvalue Property
- Map</a>. The key type of the map must be the graph's edge descriptor
- type.<br>
- <b>Default:</b> <tt>get(edge_residual_capacity, g)</tt>
-</blockquote>
-
-IN: <tt>reverse_edge_map(ReverseEdgeMap rev)</tt>
-<blockquote>
- An edge property map that maps every edge <i>(u,v)</i> in the graph
- to the reverse edge <i>(v,u)</i>. The map must be a model of
- constant <a href="../../property_map/LvaluePropertyMap.html">Lvalue
- Property Map</a>. The key type of the map must be the graph's edge
- descriptor type.<br>
- <b>Default:</b> <tt>get(edge_reverse, g)</tt>
-</blockquote>
-
-UTIL: <tt>color_map(ColorMap color)</tt>
-<blockquote>
- Used by the algorithm to keep track of progress during the
- breadth-first search stage. At the end of the algorithm, the white
- vertices define the minimum cut set. The map must be a model of
- mutable <a
- href="../../property_map/LvaluePropertyMap.html">Lvalue Property Map</a>.
- The key type of the map should be the graph's vertex descriptor type, and
- the value type must be a model of <a
- href="./ColorValue.html">ColorValue</a>.<br>
-
- <b>Default:</b> an <a
- href="../../property_map/iterator_property_map.html">
- <tt>iterator_property_map</tt></a> created from a <tt>std::vector</tt>
- of <tt>default_color_type</tt> of size <tt>num_vertices(g)</tt> and
- using the <tt>i_map</tt> for the index map.
-</blockquote>
-
-UTIL: <tt>predecessor_map(PredEdgeMap pred)</tt>
-<blockquote>
- Use by the algorithm to store augmenting paths. The map must be a
- model of mutable <a
- href="../../property_map/LvaluePropertyMap.html">Lvalue Property Map</a>.
- The key type must be the graph's vertex descriptor type and the
- value type must be the graph's edge descriptor type.<br>
-
- <b>Default:</b> an <a
- href="../../property_map/iterator_property_map.html">
- <tt>iterator_property_map</tt></a> created from a <tt>std::vector</tt>
- of edge descriptors of size <tt>num_vertices(g)</tt> and
- using the <tt>i_map</tt> for the index map.
-</blockquote>
-
-IN: <tt>vertex_index_map(VertexIndexMap i_map)</tt>
-<blockquote>
- Maps each vertex of the graph to a unique integer in the range
- <tt>[0, num_vertices(g))</tt>. This property map is only needed
- if the default for the color or predecessor map is used.
- The vertex index map must be a model of <a
- href="../../property_map/ReadablePropertyMap.html">Readable Property
- Map</a>. The key type of the map must be the graph's vertex
- descriptor type.<br>
- <b>Default:</b> <tt>get(vertex_index, g)</tt>
- Note: if you use this default, make sure your graph has
- an internal <tt>vertex_index</tt> property. For example,
- <tt>adjacenty_list</tt> with <tt>VertexList=listS</tt> does
- not have an internal <tt>vertex_index</tt> property.
-</blockquote>
-
-
-<h3>Complexity</h3>
-
-The time complexity is <i>O(V E<sup>2</sup>)</i> in the general case
-or <i>O(V E U)</i> if capacity values are integers bounded by
-some constant <i>U</i>.
-
-<h3>Example</h3>
-
-The program in <a
-href="../example/edmunds-karp-eg.cpp"><tt>example/edmunds-karp-eg.cpp</tt></a>
-reads an example maximum flow problem (a graph with edge capacities)
-from a file in the DIMACS format and computes the maximum flow.
-
-
-<h3>See Also</h3>
-
-push_relabel_max_flow()<br>
-kolmogorov_max_flow().
-
-<br>
-<HR>
-<TABLE>
-<TR valign=top>
-<TD nowrap>Copyright © 2000-2001</TD><TD>
-<A HREF="../../../people/jeremy_siek.htm">Jeremy Siek</A>, Indiana University (<A HREF="mailto:jsiek_at_[hidden]">jsiek_at_[hidden]</A>)
-</TD></TR></TABLE>
-
-</BODY>
-</HTML>
-<!-- LocalWords: HTML Siek Edmunds BGCOLOR ffffff ee VLINK ALINK ff IMG SRC
- -->
-<!-- LocalWords: gif ALT BR sec edmunds karp TT DIV CELLPADDING TR TD PRE lt
- -->
-<!-- LocalWords: typename VertexListGraph CapacityEdgeMap ReverseEdgeMap gt
- -->
-<!-- LocalWords: ResidualCapacityEdgeMap VertexIndexMap src rev ColorMap pred
- -->
-<!-- LocalWords: PredEdgeMap tt href html hpp ul li nbsp br LvaluePropertyMap
- -->
-<!-- LocalWords: num ColorValue DIMACS cpp pre config iostream dimacs int std
- -->
-<!-- LocalWords: namespace vecS directedS cout endl iter ei HR valign nowrap
- -->
-<!-- LocalWords: jeremy siek htm Univ mailto jsiek lsc edu
-p -->
Modified: trunk/libs/graph/doc/kolmogorov_max_flow.html
==============================================================================
--- trunk/libs/graph/doc/kolmogorov_max_flow.html (original)
+++ trunk/libs/graph/doc/kolmogorov_max_flow.html 2008-01-26 13:35:59 EST (Sat, 26 Jan 2008)
@@ -364,7 +364,7 @@
f 7 6 0
f 7 5 0</PRE><H3>
See Also</H3>
-<P STYLE="margin-bottom: 0cm"><TT>edmunds_karp_max_flow()</TT>,<BR><TT>push_relabel_max_flow()</TT>.
+<P STYLE="margin-bottom: 0cm"><TT>edmonds_karp_max_flow()</TT>,<BR><TT>push_relabel_max_flow()</TT>.
</P>
<HR>
<TABLE CELLPADDING=2 CELLSPACING=2>
Modified: trunk/libs/graph/doc/push_relabel_max_flow.html
==============================================================================
--- trunk/libs/graph/doc/push_relabel_max_flow.html (original)
+++ trunk/libs/graph/doc/push_relabel_max_flow.html 2008-01-26 13:35:59 EST (Sat, 26 Jan 2008)
@@ -225,7 +225,7 @@
<h3>See Also</h3>
-edmunds_karp_max_flow()<br>
+edmonds_karp_max_flow()<br>
<a href="./kolmogorov_max_flow.html"><tt>kolmogorov_max_flow()</tt></a>.
<br>
Modified: trunk/libs/graph/example/edge-connectivity.cpp
==============================================================================
--- trunk/libs/graph/example/edge-connectivity.cpp (original)
+++ trunk/libs/graph/example/edge-connectivity.cpp 2008-01-26 13:35:59 EST (Sat, 26 Jan 2008)
@@ -8,7 +8,7 @@
#include <boost/config.hpp>
#include <algorithm>
#include <utility>
-#include <boost/graph/edmunds_karp_max_flow.hpp>
+#include <boost/graph/edmonds_karp_max_flow.hpp>
#include <boost/graph/push_relabel_max_flow.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graphviz.hpp>
@@ -110,7 +110,7 @@
while (!nonneighbor_S.empty()) {
k = nonneighbor_S.front();
- alpha_S_k = edmunds_karp_max_flow
+ alpha_S_k = edmonds_karp_max_flow
(flow_g, p, k, cap, res_cap, rev_edge, &color[0], &pred[0]);
if (alpha_S_k < alpha_star) {
alpha_star = alpha_S_k;
Added: trunk/libs/graph/example/edmonds-karp-eg.cpp
==============================================================================
--- (empty file)
+++ trunk/libs/graph/example/edmonds-karp-eg.cpp 2008-01-26 13:35:59 EST (Sat, 26 Jan 2008)
@@ -0,0 +1,90 @@
+//=======================================================================
+// Copyright 2001 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)
+//=======================================================================
+#include <boost/config.hpp>
+#include <iostream>
+#include <string>
+#include <boost/graph/edmonds_karp_max_flow.hpp>
+#include <boost/graph/adjacency_list.hpp>
+#include <boost/graph/read_dimacs.hpp>
+#include <boost/graph/graph_utility.hpp>
+
+// Use a DIMACS network flow file as stdin.
+// edmonds-karp-eg < max_flow.dat
+//
+// Sample output:
+// c The total flow:
+// s 13
+//
+// c flow values:
+// f 0 6 3
+// f 0 1 6
+// f 0 2 4
+// f 1 5 1
+// f 1 0 0
+// f 1 3 5
+// f 2 4 4
+// f 2 3 0
+// f 2 0 0
+// f 3 7 5
+// f 3 2 0
+// f 3 1 0
+// f 4 5 4
+// f 4 6 0
+// f 5 4 0
+// f 5 7 5
+// f 6 7 3
+// f 6 4 0
+// f 7 6 0
+// f 7 5 0
+
+int
+main()
+{
+ using namespace boost;
+
+ typedef adjacency_list_traits < vecS, vecS, directedS > Traits;
+ typedef adjacency_list < listS, vecS, directedS,
+ property < vertex_name_t, std::string >,
+ property < edge_capacity_t, long,
+ property < edge_residual_capacity_t, long,
+ property < edge_reverse_t, Traits::edge_descriptor > > > > Graph;
+
+ Graph g;
+
+ property_map < Graph, edge_capacity_t >::type
+ capacity = get(edge_capacity, g);
+ property_map < Graph, edge_reverse_t >::type rev = get(edge_reverse, g);
+ property_map < Graph, edge_residual_capacity_t >::type
+ residual_capacity = get(edge_residual_capacity, g);
+
+ Traits::vertex_descriptor s, t;
+ read_dimacs_max_flow(g, capacity, rev, s, t);
+
+#if defined(BOOST_MSVC) && BOOST_MSVC <= 1300
+ std::vector<default_color_type> color(num_vertices(g));
+ std::vector<Traits::edge_descriptor> pred(num_vertices(g));
+ long flow = edmonds_karp_max_flow
+ (g, s, t, capacity, residual_capacity, rev, &color[0], &pred[0]);
+#else
+ long flow = edmonds_karp_max_flow(g, s, t);
+#endif
+
+ std::cout << "c The total flow:" << std::endl;
+ std::cout << "s " << flow << std::endl << std::endl;
+
+ std::cout << "c flow values:" << std::endl;
+ graph_traits < Graph >::vertex_iterator u_iter, u_end;
+ graph_traits < Graph >::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)
+ if (capacity[*ei] > 0)
+ std::cout << "f " << *u_iter << " " << target(*ei, g) << " "
+ << (capacity[*ei] - residual_capacity[*ei]) << std::endl;
+
+ return EXIT_SUCCESS;
+}
Deleted: trunk/libs/graph/example/edmunds-karp-eg.cpp
==============================================================================
--- trunk/libs/graph/example/edmunds-karp-eg.cpp 2008-01-26 13:35:59 EST (Sat, 26 Jan 2008)
+++ (empty file)
@@ -1,90 +0,0 @@
-//=======================================================================
-// Copyright 2001 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)
-//=======================================================================
-#include <boost/config.hpp>
-#include <iostream>
-#include <string>
-#include <boost/graph/edmunds_karp_max_flow.hpp>
-#include <boost/graph/adjacency_list.hpp>
-#include <boost/graph/read_dimacs.hpp>
-#include <boost/graph/graph_utility.hpp>
-
-// Use a DIMACS network flow file as stdin.
-// edmunds-karp-eg < max_flow.dat
-//
-// Sample output:
-// c The total flow:
-// s 13
-//
-// c flow values:
-// f 0 6 3
-// f 0 1 6
-// f 0 2 4
-// f 1 5 1
-// f 1 0 0
-// f 1 3 5
-// f 2 4 4
-// f 2 3 0
-// f 2 0 0
-// f 3 7 5
-// f 3 2 0
-// f 3 1 0
-// f 4 5 4
-// f 4 6 0
-// f 5 4 0
-// f 5 7 5
-// f 6 7 3
-// f 6 4 0
-// f 7 6 0
-// f 7 5 0
-
-int
-main()
-{
- using namespace boost;
-
- typedef adjacency_list_traits < vecS, vecS, directedS > Traits;
- typedef adjacency_list < listS, vecS, directedS,
- property < vertex_name_t, std::string >,
- property < edge_capacity_t, long,
- property < edge_residual_capacity_t, long,
- property < edge_reverse_t, Traits::edge_descriptor > > > > Graph;
-
- Graph g;
-
- property_map < Graph, edge_capacity_t >::type
- capacity = get(edge_capacity, g);
- property_map < Graph, edge_reverse_t >::type rev = get(edge_reverse, g);
- property_map < Graph, edge_residual_capacity_t >::type
- residual_capacity = get(edge_residual_capacity, g);
-
- Traits::vertex_descriptor s, t;
- read_dimacs_max_flow(g, capacity, rev, s, t);
-
-#if defined(BOOST_MSVC) && BOOST_MSVC <= 1300
- std::vector<default_color_type> color(num_vertices(g));
- std::vector<Traits::edge_descriptor> pred(num_vertices(g));
- long flow = edmunds_karp_max_flow
- (g, s, t, capacity, residual_capacity, rev, &color[0], &pred[0]);
-#else
- long flow = edmunds_karp_max_flow(g, s, t);
-#endif
-
- std::cout << "c The total flow:" << std::endl;
- std::cout << "s " << flow << std::endl << std::endl;
-
- std::cout << "c flow values:" << std::endl;
- graph_traits < Graph >::vertex_iterator u_iter, u_end;
- graph_traits < Graph >::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)
- if (capacity[*ei] > 0)
- std::cout << "f " << *u_iter << " " << target(*ei, g) << " "
- << (capacity[*ei] - residual_capacity[*ei]) << std::endl;
-
- return EXIT_SUCCESS;
-}
Modified: trunk/libs/graph/example/regression.cfg
==============================================================================
--- trunk/libs/graph/example/regression.cfg (original)
+++ trunk/libs/graph/example/regression.cfg 2008-01-26 13:35:59 EST (Sat, 26 Jan 2008)
@@ -44,7 +44,7 @@
compile libs/graph/example/edge_connectivity.cpp
compile libs/graph/example/edge_iterator_constructor.cpp
compile libs/graph/example/edge_property.cpp
-compile libs/graph/example/edmunds-karp-eg.cpp
+compile libs/graph/example/edmonds-karp-eg.cpp
compile libs/graph/example/exterior_properties.cpp
compile libs/graph/example/exterior_property_map.cpp
compile libs/graph/example/family-tree-eg.cpp
Modified: trunk/libs/graph/test/max_flow_test.cpp
==============================================================================
--- trunk/libs/graph/test/max_flow_test.cpp (original)
+++ trunk/libs/graph/test/max_flow_test.cpp 2008-01-26 13:35:59 EST (Sat, 26 Jan 2008)
@@ -39,7 +39,7 @@
//three max_flows we test here
#include <boost/graph/kolmogorov_max_flow.hpp>
#include <boost/graph/push_relabel_max_flow.hpp>
-#include <boost/graph/edmunds_karp_max_flow.hpp>
+#include <boost/graph/edmonds_karp_max_flow.hpp>
//boost utilities we use
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/random.hpp>
@@ -127,10 +127,10 @@
tEdgeVal kolmo = kolmogorov_max_flow(g,source_vertex,sink_vertex);
tEdgeVal push_relabel = push_relabel_max_flow(g,source_vertex,sink_vertex);
- tEdgeVal edmunds_karp = edmunds_karp_max_flow(g,source_vertex,sink_vertex);
+ tEdgeVal edmonds_karp = edmonds_karp_max_flow(g,source_vertex,sink_vertex);
BOOST_REQUIRE( kolmo == push_relabel );
- BOOST_REQUIRE( push_relabel == edmunds_karp );
+ BOOST_REQUIRE( push_relabel == edmonds_karp );
return 0;
}