Boost logo

Boost-Commit :

Date view Thread view Subject view Author view

Subject: [Boost-commit] svn:boost r50153 - in branches/release: . boost/graph libs/graph/doc libs/graph/example libs/graph/test
From: juergen.hunold_at_[hidden]
Date: 2008-12-06 04:10:24

Author: jhunold
Date: 2008-12-06 04:10:20 EST (Sat, 06 Dec 2008)
New Revision: 50153
URL: http://svn.boost.org/trac/boost/changeset/50153

Log:
Fix #416

Merged revisions 42984,50137 via svnmerge from
https://svn.boost.org/svn/boost/trunk

........
  r42984 | noel_belcourt | 2008-01-26 19:35:59 +0100 (Sat, 26 Jan 2008) | 7 lines
  
  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.
........
  r50137 | jhunold | 2008-12-05 18:53:22 +0100 (Fri, 05 Dec 2008) | 3 lines
  
  Add deprecation header for wrong-spelled Edmonds-Karp-Max-Flox.
  Preparaion to fix #416
........

Added:
   branches/release/boost/graph/edmonds_karp_max_flow.hpp
      - copied unchanged from r42984, /trunk/boost/graph/edmonds_karp_max_flow.hpp
   branches/release/boost/graph/edmunds_karp_max_flow.hpp
      - copied unchanged from r50137, /trunk/boost/graph/edmunds_karp_max_flow.hpp
   branches/release/libs/graph/doc/edmonds_karp_max_flow.html
      - copied unchanged from r42984, /trunk/libs/graph/doc/edmonds_karp_max_flow.html
   branches/release/libs/graph/example/edmonds-karp-eg.cpp
      - copied unchanged from r42984, /trunk/libs/graph/example/edmonds-karp-eg.cpp
Removed:
   branches/release/libs/graph/doc/edmunds_karp_max_flow.html
   branches/release/libs/graph/example/edmunds-karp-eg.cpp
Properties modified:
   branches/release/ (props changed)
Text files modified:
   branches/release/boost/graph/edge_connectivity.hpp | 4 ++--
   branches/release/libs/graph/doc/kolmogorov_max_flow.html | 2 +-
   branches/release/libs/graph/doc/push_relabel_max_flow.html | 2 +-
   branches/release/libs/graph/example/edge-connectivity.cpp | 4 ++--
   branches/release/libs/graph/example/regression.cfg | 2 +-
   branches/release/libs/graph/test/max_flow_test.cpp | 6 +++---
   6 files changed, 10 insertions(+), 10 deletions(-)

Modified: branches/release/boost/graph/edge_connectivity.hpp
==============================================================================
--- branches/release/boost/graph/edge_connectivity.hpp (original)
+++ branches/release/boost/graph/edge_connectivity.hpp 2008-12-06 04:10:20 EST (Sat, 06 Dec 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) {

Deleted: branches/release/libs/graph/doc/edmunds_karp_max_flow.html
==============================================================================
--- branches/release/libs/graph/doc/edmunds_karp_max_flow.html 2008-12-06 04:10:20 EST (Sat, 06 Dec 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="http://www.boost.org/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: branches/release/libs/graph/doc/kolmogorov_max_flow.html
==============================================================================
--- branches/release/libs/graph/doc/kolmogorov_max_flow.html (original)
+++ branches/release/libs/graph/doc/kolmogorov_max_flow.html 2008-12-06 04:10:20 EST (Sat, 06 Dec 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: branches/release/libs/graph/doc/push_relabel_max_flow.html
==============================================================================
--- branches/release/libs/graph/doc/push_relabel_max_flow.html (original)
+++ branches/release/libs/graph/doc/push_relabel_max_flow.html 2008-12-06 04:10:20 EST (Sat, 06 Dec 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: branches/release/libs/graph/example/edge-connectivity.cpp
==============================================================================
--- branches/release/libs/graph/example/edge-connectivity.cpp (original)
+++ branches/release/libs/graph/example/edge-connectivity.cpp 2008-12-06 04:10:20 EST (Sat, 06 Dec 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;

Deleted: branches/release/libs/graph/example/edmunds-karp-eg.cpp
==============================================================================
--- branches/release/libs/graph/example/edmunds-karp-eg.cpp 2008-12-06 04:10:20 EST (Sat, 06 Dec 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: branches/release/libs/graph/example/regression.cfg
==============================================================================
--- branches/release/libs/graph/example/regression.cfg (original)
+++ branches/release/libs/graph/example/regression.cfg 2008-12-06 04:10:20 EST (Sat, 06 Dec 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: branches/release/libs/graph/test/max_flow_test.cpp
==============================================================================
--- branches/release/libs/graph/test/max_flow_test.cpp (original)
+++ branches/release/libs/graph/test/max_flow_test.cpp 2008-12-06 04:10:20 EST (Sat, 06 Dec 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;
 }

Date view Thread view Subject view Author view

Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk