[Boost-commit] svn:boost r42984 - in trunk: boost/graph libs/graph/doc libs/graph/example libs/graph/test

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 &lt;class Graph, class P, class T, class R&gt;
+typename detail::edge_capacity_value&lt;Graph, P, T, R&gt;::value_type
+edmonds_karp_max_flow(Graph& g, 
+   typename graph_traits&lt;Graph&gt;::vertex_descriptor src,
+   typename graph_traits&lt;Graph&gt;::vertex_descriptor sink,
+   const bgl_named_params&lt;P, T, R&gt;&amp; params = <i>all defaults</i>)
+
+<i>// non-named parameter version</i>
+template &lt;class Graph, 
+	  class CapacityEdgeMap, class ResidualCapacityEdgeMap,
+	  class ReverseEdgeMap, class ColorMap, class PredEdgeMap&gt;
+typename property_traits&lt;CapacityEdgeMap&gt;::value_type
+edmonds_karp_max_flow(Graph&amp; g, 
+   typename graph_traits&lt;Graph&gt;::vertex_descriptor src,
+   typename graph_traits&lt;Graph&gt;::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&amp; 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 &copy 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 &lt;class Graph, class P, class T, class R&gt;
-typename detail::edge_capacity_value&lt;Graph, P, T, R&gt;::value_type
-edmunds_karp_max_flow(Graph& g, 
-   typename graph_traits&lt;Graph&gt;::vertex_descriptor src,
-   typename graph_traits&lt;Graph&gt;::vertex_descriptor sink,
-   const bgl_named_params&lt;P, T, R&gt;&amp; params = <i>all defaults</i>)
-
-<i>// non-named parameter version</i>
-template &lt;class Graph, 
-	  class CapacityEdgeMap, class ResidualCapacityEdgeMap,
-	  class ReverseEdgeMap, class ColorMap, class PredEdgeMap&gt;
-typename property_traits&lt;CapacityEdgeMap&gt;::value_type
-edmunds_karp_max_flow(Graph&amp; g, 
-   typename graph_traits&lt;Graph&gt;::vertex_descriptor src,
-   typename graph_traits&lt;Graph&gt;::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&amp; 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 &copy 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;
 }