|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r63241 - in trunk: boost/graph libs/graph/doc libs/graph/example libs/graph/quickbook libs/graph/test status
From: jewillco_at_[hidden]
Date: 2010-06-22 11:38:04
Author: jewillco
Date: 2010-06-22 11:38:02 EDT (Tue, 22 Jun 2010)
New Revision: 63241
URL: http://svn.boost.org/trac/boost/changeset/63241
Log:
Boykov-Kolmogorov max-flow updates and some small typo fixes
Removed:
trunk/libs/graph/example/kolmogorov-eg.cpp
trunk/libs/graph/test/kolmogorov_max_flow_test.cpp
Text files modified:
trunk/boost/graph/boykov_kolmogorov_max_flow.hpp | 6 +++---
trunk/libs/graph/doc/bibliography.html | 2 +-
trunk/libs/graph/doc/edmonds_karp_max_flow.html | 6 +++---
trunk/libs/graph/doc/history.html | 2 +-
trunk/libs/graph/doc/kolmogorov_max_flow.html | 2 +-
trunk/libs/graph/doc/push_relabel_max_flow.html | 2 +-
trunk/libs/graph/quickbook/history.qbk | 4 ++--
trunk/libs/graph/test/Jamfile.v2 | 1 -
trunk/libs/graph/test/boykov_kolmogorov_max_flow_test.cpp | 2 +-
trunk/libs/graph/test/max_flow_test.cpp | 6 +++---
trunk/status/explicit-failures-markup.xml | 2 +-
11 files changed, 17 insertions(+), 18 deletions(-)
Modified: trunk/boost/graph/boykov_kolmogorov_max_flow.hpp
==============================================================================
--- trunk/boost/graph/boykov_kolmogorov_max_flow.hpp (original)
+++ trunk/boost/graph/boykov_kolmogorov_max_flow.hpp 2010-06-22 11:38:02 EDT (Tue, 22 Jun 2010)
@@ -29,8 +29,8 @@
// (See accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)
-#ifndef BOOST_KOLMOGOROV_MAX_FLOW_HPP
-#define BOOST_KOLMOGOROV_MAX_FLOW_HPP
+#ifndef BOOST_BOYKOV_KOLMOGOROV_MAX_FLOW_HPP
+#define BOOST_BOYKOV_KOLMOGOROV_MAX_FLOW_HPP
#include <boost/config.hpp>
#include <cassert>
@@ -155,7 +155,7 @@
}
// the complete class is protected, as we want access to members in
- // derived test-class (see test/kolmogorov_max_flow_test.cpp)
+ // derived test-class (see test/boykov_kolmogorov_max_flow_test.cpp)
protected:
void augment_direct_paths(){
// in a first step, we augment all direct paths from source->NODE->sink
Modified: trunk/libs/graph/doc/bibliography.html
==============================================================================
--- trunk/libs/graph/doc/bibliography.html (original)
+++ trunk/libs/graph/doc/bibliography.html 2010-06-22 11:38:02 EDT (Tue, 22 Jun 2010)
@@ -409,7 +409,7 @@
<p></p><dt><a name="boykov-kolmogorov04">69</a>
<dd>Yuri Boykov and Vladimir Kolmogorov<br>
<em>An Experimental Comparison of Min-Cut/Max-Flow Algorithms for Energy Minimization in Vision</em><br>
- In IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 26, no. 9, pp. 1124-1137, Sept. 2004.
+ In <em>IEEE Transactions on Pattern Analysis and Machine Intelligence</em>, vol. 26, no. 9, pp. 1124-1137, Sept. 2004.
<p></p><dt><a name="boyermyrvold04">70</a>
<dd>John M. Boyer and Wendy J. Myrvold<br>
Modified: trunk/libs/graph/doc/edmonds_karp_max_flow.html
==============================================================================
--- trunk/libs/graph/doc/edmonds_karp_max_flow.html (original)
+++ trunk/libs/graph/doc/edmonds_karp_max_flow.html 2010-06-22 11:38:02 EDT (Tue, 22 Jun 2010)
@@ -20,7 +20,7 @@
</H1>
<PRE>
-<i>// named paramter version</i>
+<i>// named parameter 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,
@@ -76,7 +76,7 @@
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>
+href="./boykov_kolmogorov_max_flow.html"><tt>boykov_kolmogorov_max_flow()</tt></a>
algorithm.
<ul>
@@ -217,7 +217,7 @@
<h3>See Also</h3>
<a href="./push_relabel_max_flow.html"><tt>push_relabel_max_flow()</tt></a><br>
-kolmogorov_max_flow().
+boykov_kolmogorov_max_flow().
<br>
<HR>
Modified: trunk/libs/graph/doc/history.html
==============================================================================
--- trunk/libs/graph/doc/history.html (original)
+++ trunk/libs/graph/doc/history.html 2010-06-22 11:38:02 EDT (Tue, 22 Jun 2010)
@@ -84,7 +84,7 @@
<a name="1.35.0"></a><li>Version 1.35.0<br><b>New algorithms and components</b>
<ul>
- <li>kolmogorov_max_flow, from Stephan Diederich as part of the 2006 Google Summer of Code.</li>
+ <li>boykov_kolmogorov_max_flow (formerly kolmogorov_max_flow), from Stephan Diederich as part of the 2006 Google Summer of Code.</li>
<li>read_dimacs_max_flow and write_dimacs_max_flow for max-flow problems, from Stephan Diederich.</li>
<li>read_graphml and write_graphml for GraphML input/output, from Tiago de Paula Peixoto.</li>
<li>minimum_cycle_ratio and maximum_cycle_ratio, from Dmitry Bufistov and Andrey Parfenov.</li>
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 2010-06-22 11:38:02 EDT (Tue, 22 Jun 2010)
@@ -2,7 +2,7 @@
<HTML>
<HEAD>
<META HTTP-EQUIV="CONTENT-TYPE" CONTENT="text/html; charset=iso-8859-15">
- <TITLE>Boost Graph Library: Kolmogorov Maximum Flow</TITLE>
+ <TITLE>Boost Graph Library: Boykov-Kolmogorov Maximum Flow</TITLE>
<META NAME="GENERATOR" CONTENT="OpenOffice.org 2.0 (Linux)">
<META NAME="CREATED" CONTENT="20060820;17315200">
<META NAME="CHANGEDBY" CONTENT="Stephan Diederich">
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 2010-06-22 11:38:02 EDT (Tue, 22 Jun 2010)
@@ -226,7 +226,7 @@
<h3>See Also</h3>
<a href="./edmonds_karp_max_flow.html"><tt>edmonds_karp_max_flow()</tt></a><br>
-kolmogorov_max_flow().
+boykov_kolmogorov_max_flow().
<br>
<HR>
Deleted: trunk/libs/graph/example/kolmogorov-eg.cpp
==============================================================================
--- trunk/libs/graph/example/kolmogorov-eg.cpp 2010-06-22 11:38:02 EDT (Tue, 22 Jun 2010)
+++ (empty file)
@@ -1,112 +0,0 @@
-// Copyright (c) 2006, Stephan Diederich
-//
-// This code may be used under either of the following two licences:
-//
-// Permission is hereby granted, free of charge, to any person
-// obtaining a copy of this software and associated documentation
-// files (the "Software"), to deal in the Software without
-// restriction, including without limitation the rights to use,
-// copy, modify, merge, publish, distribute, sublicense, and/or
-// sell copies of the Software, and to permit persons to whom the
-// Software is furnished to do so, subject to the following
-// conditions:
-//
-// The above copyright notice and this permission notice shall be
-// included in all copies or substantial portions of the Software.
-//
-// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
-// EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
-// OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
-// NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
-// HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
-// WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
-// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
-// OTHER DEALINGS IN THE SOFTWARE. OF SUCH DAMAGE.
-//
-// Or:
-//
-// 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/kolmogorov_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.
-// kolmogorov-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 0
-// f 4 6 4
-// f 5 4 0
-// f 5 7 1
-// f 6 7 7
-// 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 < vecS, vecS, directedS,
- property < vertex_name_t, std::string,
- property < vertex_index_t, long,
- property < vertex_color_t, boost::default_color_type,
- property < vertex_distance_t, long,
- property < vertex_predecessor_t, Traits::edge_descriptor > > > > >,
-
- 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_residual_capacity_t >::type
- residual_capacity = get(edge_residual_capacity, g);
- property_map < Graph, edge_reverse_t >::type rev = get(edge_reverse, g);
- Traits::vertex_descriptor s, t;
- read_dimacs_max_flow(g, capacity, rev, s, t);
-
- std::vector<default_color_type> color(num_vertices(g));
- std::vector<long> distance(num_vertices(g));
- long flow = kolmogorov_max_flow(g ,s, t);
-
- 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/quickbook/history.qbk
==============================================================================
--- trunk/libs/graph/quickbook/history.qbk (original)
+++ trunk/libs/graph/quickbook/history.qbk 2010-06-22 11:38:02 EDT (Tue, 22 Jun 2010)
@@ -56,7 +56,7 @@
* Version 1.35.0
* New algorithms and components
- * kolmogorov_max_flow, from Stephan Diederich as part of the 2006 Google Summer of Code.
+ * boykov_kolmogorov_max_flow (formerly kolmogorov_max_flow), from Stephan Diederich as part of the 2006 Google Summer of Code.
* read_dimacs_max_flow and write_dimacs_max_flow for max-flow problems, from Stephan Diederich.
* read_graphml and write_graphml for GraphML input/output, from Tiago de Paula Peixoto.
* Enhancements
@@ -117,4 +117,4 @@
* read_graphviz now accepts empty attribute lists.
* sequential_vertex_coloring has been updated, tested, and documented.
-[endsect]
\ No newline at end of file
+[endsect]
Modified: trunk/libs/graph/test/Jamfile.v2
==============================================================================
--- trunk/libs/graph/test/Jamfile.v2 (original)
+++ trunk/libs/graph/test/Jamfile.v2 2010-06-22 11:38:02 EDT (Tue, 22 Jun 2010)
@@ -85,7 +85,6 @@
[ run matching_test.cpp ]
[ run max_flow_test.cpp ]
[ run boykov_kolmogorov_max_flow_test.cpp ]
- [ run kolmogorov_max_flow_test.cpp ]
[ run cycle_ratio_tests.cpp ../build//boost_graph ../../regex/build//boost_regex : $(CYCLE_RATIO_INPUT_FILE) ]
[ run basic_planarity_test.cpp ]
[ run make_connected_test.cpp ]
Modified: trunk/libs/graph/test/boykov_kolmogorov_max_flow_test.cpp
==============================================================================
--- trunk/libs/graph/test/boykov_kolmogorov_max_flow_test.cpp (original)
+++ trunk/libs/graph/test/boykov_kolmogorov_max_flow_test.cpp 2010-06-22 11:38:02 EDT (Tue, 22 Jun 2010)
@@ -455,7 +455,7 @@
std::cout << "overloads flow: " << flow_overloads << std::endl;
BOOST_CHECK(flow_bundles == flow_overloads);
- // excessive test version where boykov-kolmogorov's algorithm invariants are
+ // excessive test version where Boykov-Kolmogorov's algorithm invariants are
// checked
long flow_invariants = test_algorithms_invariant(n_verts, n_edges, seed);
std::cout << "invariants flow: " << flow_invariants << std::endl;
Deleted: trunk/libs/graph/test/kolmogorov_max_flow_test.cpp
==============================================================================
--- trunk/libs/graph/test/kolmogorov_max_flow_test.cpp 2010-06-22 11:38:02 EDT (Tue, 22 Jun 2010)
+++ (empty file)
@@ -1,434 +0,0 @@
-// Copyright (c) 2006, Stephan Diederich
-//
-// This code may be used under either of the following two licences:
-//
-// Permission is hereby granted, free of charge, to any person
-// obtaining a copy of this software and associated documentation
-// files (the "Software"), to deal in the Software without
-// restriction, including without limitation the rights to use,
-// copy, modify, merge, publish, distribute, sublicense, and/or
-// sell copies of the Software, and to permit persons to whom the
-// Software is furnished to do so, subject to the following
-// conditions:
-//
-// The above copyright notice and this permission notice shall be
-// included in all copies or substantial portions of the Software.
-//
-// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
-// EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
-// OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
-// NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
-// HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
-// WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
-// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
-// OTHER DEALINGS IN THE SOFTWARE. OF SUCH DAMAGE.
-//
-// Or:
-//
-// 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 <vector>
-#include <iterator>
-#include <iostream>
-#include <algorithm>
-#include <fstream>
-
-#include <boost/test/minimal.hpp>
-#include <boost/graph/kolmogorov_max_flow.hpp>
-//boost utilities we use
-#include <boost/graph/adjacency_list.hpp>
-#include <boost/graph/adjacency_matrix.hpp>
-#include <boost/graph/random.hpp>
-#include <boost/property_map/property_map.hpp>
-#include <boost/random/linear_congruential.hpp>
-#include <boost/lexical_cast.hpp>
-
-using namespace boost;
-
-template <typename Graph, typename CapacityMap, typename ReverseEdgeMap>
-std::pair< typename graph_traits<Graph>::vertex_descriptor,typename graph_traits<Graph>::vertex_descriptor>
-fill_random_max_flow_graph(Graph& g, CapacityMap cap, ReverseEdgeMap rev, typename graph_traits<Graph>::vertices_size_type n_verts,
- typename graph_traits<Graph>::edges_size_type n_edges, std::size_t seed)
-{
- typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor;
- typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
- const int cap_low = 1;
- const int cap_high = 1000;
-
- //init random numer generator
- minstd_rand gen(seed);
- //generate graph
- generate_random_graph(g, n_verts, n_edges, gen);
-
- //init an uniform distribution int generator
- typedef variate_generator<minstd_rand, uniform_int<int> > tIntGen;
- tIntGen int_gen(gen, uniform_int<int>(cap_low, cap_high));
- //randomize edge-capacities
- //randomize_property<edge_capacity, Graph, tIntGen> (g,int_gen); //we cannot use this, as we have no idea how properties are stored, right?
- typename graph_traits<Graph>::edge_iterator ei, e_end;
- for(tie(ei,e_end) = edges(g); ei != e_end; ++ei)
- cap[*ei] = int_gen();
-
- //get source and sink node
- vertex_descriptor s = random_vertex(g, gen);
- vertex_descriptor t = graph_traits<Graph>::null_vertex();
- while(t == graph_traits<Graph>::null_vertex() || t == s)
- t = random_vertex(g, gen);
-
- //add reverse edges (ugly... how to do better?!)
- std::list<edge_descriptor> edges_copy;
- tie(ei, e_end) = edges(g);
- std::copy(ei, e_end, std::back_insert_iterator< std::list<edge_descriptor> >(edges_copy));
- while(!edges_copy.empty()){
- edge_descriptor old_edge = edges_copy.front();
- edges_copy.pop_front();
- vertex_descriptor source_vertex = target(old_edge, g);
- vertex_descriptor target_vertex = source(old_edge, g);
- bool inserted;
- edge_descriptor new_edge;
- tie(new_edge,inserted) = add_edge(source_vertex, target_vertex, g);
- assert(inserted);
- rev[old_edge] = new_edge;
- rev[new_edge] = old_edge ;
- cap[new_edge] = 0;
- }
- return std::make_pair(s,t);
-}
-
-long test_adjacency_list_vecS(int n_verts, int n_edges, std::size_t seed){
- typedef adjacency_list_traits<vecS, vecS, directedS> tVectorTraits;
- typedef adjacency_list<vecS, vecS, directedS,
- property<vertex_index_t, long,
- property<vertex_predecessor_t, tVectorTraits::edge_descriptor,
- property<vertex_color_t, boost::default_color_type,
- property<vertex_distance_t, long> > > >,
- property<edge_capacity_t, long,
- property<edge_residual_capacity_t, long,
- property<edge_reverse_t, tVectorTraits::edge_descriptor > > > > tVectorGraph;
-
- tVectorGraph g;
-
- graph_traits<tVectorGraph>::vertex_descriptor src,sink;
- tie(src,sink) = fill_random_max_flow_graph(g, get(edge_capacity,g), get(edge_reverse, g), n_verts, n_edges, seed);
-
- return kolmogorov_max_flow(g, get(edge_capacity, g),
- get(edge_residual_capacity, g),
- get(edge_reverse, g),
- get(vertex_predecessor, g),
- get(vertex_color, g),
- get(vertex_distance, g),
- get(vertex_index, g),
- src, sink);
-}
-
-long test_adjacency_list_listS(int n_verts, int n_edges, std::size_t seed){
- typedef adjacency_list_traits<listS, listS, directedS> tListTraits;
- typedef adjacency_list<listS, listS, directedS,
- property<vertex_index_t, long,
- property<vertex_predecessor_t, tListTraits::edge_descriptor,
- property<vertex_color_t, boost::default_color_type,
- property<vertex_distance_t, long> > > >,
- property<edge_capacity_t, long,
- property<edge_residual_capacity_t, long,
- property<edge_reverse_t, tListTraits::edge_descriptor > > > > tListGraph;
-
- tListGraph g;
-
- graph_traits<tListGraph>::vertex_descriptor src,sink;
- tie(src,sink) = fill_random_max_flow_graph(g, get(edge_capacity,g), get(edge_reverse, g), n_verts, n_edges, seed);
-
- //initialize vertex indices
- graph_traits<tListGraph>::vertex_iterator vi,v_end;
- graph_traits<tListGraph>::vertices_size_type index = 0;
- for(tie(vi, v_end) = vertices(g); vi != v_end; ++vi){
- put(vertex_index, g, *vi, index++);
- }
- return kolmogorov_max_flow(g, get(edge_capacity, g),
- get(edge_residual_capacity, g),
- get(edge_reverse, g),
- get(vertex_predecessor, g),
- get(vertex_color, g),
- get(vertex_distance, g),
- get(vertex_index, g),
- src, sink);
-}
-
-template<typename EdgeDescriptor>
- struct Node{
- boost::default_color_type vertex_color;
- long vertex_distance;
- EdgeDescriptor vertex_predecessor;
-};
-
-template<typename EdgeDescriptor>
- struct Link{
- long edge_capacity;
- long edge_residual_capacity;
- EdgeDescriptor edge_reverse;
-};
-
-long test_bundled_properties(int n_verts, int n_edges, std::size_t seed){
- typedef adjacency_list_traits<vecS, vecS, directedS> tTraits;
- typedef Node<tTraits::edge_descriptor> tVertex;
- typedef Link<tTraits::edge_descriptor> tEdge;
- typedef adjacency_list<vecS, vecS, directedS, tVertex, tEdge> tBundleGraph;
-
- tBundleGraph g;
-
- graph_traits<tBundleGraph>::vertex_descriptor src,sink;
- tie(src,sink) = fill_random_max_flow_graph(g, get(&tEdge::edge_capacity,g), get(&tEdge::edge_reverse, g), n_verts, n_edges, seed);
- return kolmogorov_max_flow(g, get(&tEdge::edge_capacity, g),
- get(&tEdge::edge_residual_capacity, g),
- get(&tEdge::edge_reverse, g),
- get(&tVertex::vertex_predecessor, g),
- get(&tVertex::vertex_color, g),
- get(&tVertex::vertex_distance, g),
- get(vertex_index, g),
- src, sink);
-}
-
-long test_overloads(int n_verts, int n_edges, std::size_t seed){
- typedef adjacency_list_traits<vecS, vecS, directedS> tTraits;
- typedef property <edge_capacity_t, long,
- property<edge_residual_capacity_t, long,
- property<edge_reverse_t, tTraits::edge_descriptor> > >tEdgeProperty;
- typedef adjacency_list<vecS, vecS, directedS, no_property, tEdgeProperty> tGraph;
-
- tGraph g;
-
- graph_traits<tGraph>::vertex_descriptor src,sink;
- tie(src,sink) = fill_random_max_flow_graph(g, get(edge_capacity,g), get(edge_reverse, g), n_verts, n_edges, seed);
-
- std::vector<graph_traits<tGraph>::edge_descriptor> predecessor_vec(n_verts);
- std::vector<default_color_type> color_vec(n_verts);
- std::vector<graph_traits<tGraph>::vertices_size_type> distance_vec(n_verts);
-
- long flow_overload_1 = kolmogorov_max_flow(g, get(edge_capacity,g), get(edge_residual_capacity,g), get(edge_reverse,g), get(vertex_index,g), src, sink);
-
- long flow_overload_2 = kolmogorov_max_flow(g, get(edge_capacity,g), get(edge_residual_capacity,g), get(edge_reverse,g),
- &(color_vec[0]), get(vertex_index,g), src, sink);
-
- BOOST_CHECK(flow_overload_1 == flow_overload_2);
- return flow_overload_1;
-}
-
-template <class Graph, class EdgeCapacityMap, class ResidualCapacityEdgeMap, class ReverseEdgeMap, class PredecessorMap, class ColorMap,
- class DistanceMap, class IndexMap>
-class kolmogorov_test:public detail::kolmogorov<Graph,EdgeCapacityMap,ResidualCapacityEdgeMap,ReverseEdgeMap,PredecessorMap,ColorMap,DistanceMap,IndexMap>
-{
-
- typedef typename graph_traits<Graph>::edge_descriptor tEdge;
- typedef typename graph_traits<Graph>::vertex_descriptor tVertex;
- typedef typename property_traits< typename property_map<Graph, edge_capacity_t>::const_type>::value_type tEdgeVal;
- typedef typename graph_traits<Graph>::vertex_iterator tVertexIterator;
- typedef typename graph_traits<Graph>::out_edge_iterator tOutEdgeIterator;
- typedef typename property_traits<ColorMap>::value_type tColorValue;
- typedef color_traits<tColorValue> tColorTraits;
- typedef typename property_traits<DistanceMap>::value_type tDistanceVal;
- typedef typename detail::kolmogorov<Graph,EdgeCapacityMap,ResidualCapacityEdgeMap,ReverseEdgeMap,PredecessorMap,ColorMap,DistanceMap,IndexMap> tSuper;
- public:
- kolmogorov_test(Graph& g, typename graph_traits<Graph>::vertex_descriptor src, typename graph_traits<Graph>::vertex_descriptor sink):
- detail::kolmogorov<Graph,EdgeCapacityMap,ResidualCapacityEdgeMap,ReverseEdgeMap,PredecessorMap,ColorMap,DistanceMap,IndexMap>
- (g, get(edge_capacity,g), get(edge_residual_capacity,g), get(edge_reverse, g), get(vertex_predecessor, g), get(vertex_color, g),
- get(vertex_distance, g), get(vertex_index, g), src, sink){
- }
-
- void invariant_four(tVertex v) const{
- //passive nodes in S or T
- if(v == tSuper::m_source || v == tSuper::m_sink)
- return;
- typename std::list<tVertex>::const_iterator it = find(tSuper::m_orphans.begin(), tSuper::m_orphans.end(), v);
- // a node is active, if its in the active_list AND (is has_a_parent, or its already in the orphans_list or its the sink, or its the source)
- bool is_active = (tSuper::m_in_active_list_map[v] && (tSuper::has_parent(v) || it != tSuper::m_orphans.end() ));
- if(this->get_tree(v) != tColorTraits::gray() && !is_active){
- typename graph_traits<Graph>::out_edge_iterator ei,e_end;
- for(tie(ei, e_end) = out_edges(v, tSuper::m_g); ei != e_end; ++ei){
- const tVertex& other_node = target(*ei, tSuper::m_g);
- if(this->get_tree(other_node) != this->get_tree(v)){
- if(this->get_tree(v) == tColorTraits::black())
- BOOST_CHECK(tSuper::m_res_cap_map[*ei] == 0);
- else
- BOOST_CHECK(tSuper::m_res_cap_map[tSuper::m_rev_edge_map[*ei]] == 0);
- }
- }
- }
- }
-
- void invariant_five(const tVertex& v) const{
- BOOST_CHECK(this->get_tree(v) != tColorTraits::gray() || tSuper::m_time_map[v] <= tSuper::m_time);
- }
-
- void invariant_six(const tVertex& v) const{
- if(this->get_tree(v) == tColorTraits::gray() || tSuper::m_time_map[v] != tSuper::m_time)
- return;
- else{
- tVertex current_node = v;
- tDistanceVal distance = 0;
- tColorValue color = this->get_tree(v);
- tVertex terminal = (color == tColorTraits::black()) ? tSuper::m_source : tSuper::m_sink;
- while(current_node != terminal){
- BOOST_CHECK(tSuper::has_parent(current_node));
- tEdge e = this->get_edge_to_parent(current_node);
- ++distance;
- current_node = (color == tColorTraits::black())? source(e, tSuper::m_g) : target(e, tSuper::m_g);
- if(distance > tSuper::m_dist_map[v])
- break;
- }
- BOOST_CHECK(distance == tSuper::m_dist_map[v]);
- }
- }
-
- void invariant_seven(const tVertex& v) const{
- if(this->get_tree(v) == tColorTraits::gray())
- return;
- else{
- tColorValue color = this->get_tree(v);
- long time = tSuper::m_time_map[v];
- tVertex current_node = v;
- while(tSuper::has_parent(current_node)){
- tEdge e = this->get_edge_to_parent(current_node);
- current_node = (color == tColorTraits::black()) ? source(e, tSuper::m_g) : target(e, tSuper::m_g);
- BOOST_CHECK(tSuper::m_time_map[current_node] >= time);
- }
- }
- }//invariant_seven
-
- void invariant_eight(const tVertex& v) const{
- if(this->get_tree(v) == tColorTraits::gray())
- return;
- else{
- tColorValue color = this->get_tree(v);
- long time = tSuper::m_time_map[v];
- tDistanceVal distance = tSuper::m_dist_map[v];
- tVertex current_node = v;
- while(tSuper::has_parent(current_node)){
- tEdge e = this->get_edge_to_parent(current_node);
- current_node = (color == tColorTraits::black()) ? source(e, tSuper::m_g) : target(e, tSuper::m_g);
- if(tSuper::m_time_map[current_node] == time)
- BOOST_CHECK(tSuper::m_dist_map[current_node] < distance);
- }
- }
- }//invariant_eight
-
- void check_invariants(){
- tVertexIterator vi, v_end;
- for(tie(vi, v_end) = vertices(tSuper::m_g); vi != v_end; ++vi){
- invariant_four(*vi);
- invariant_five(*vi);
- invariant_six(*vi);
- invariant_seven(*vi);
- invariant_eight(*vi);
- }
- }
-
- tEdgeVal test(){
- this->add_active_node(this->m_sink);
- this->augment_direct_paths();
- check_invariants();
- //start the main-loop
- while(true){
- bool path_found;
- tEdge connecting_edge;
- tie(connecting_edge, path_found) = this->grow(); //find a path from source to sink
- if(!path_found){
- //we're finished, no more paths were found
- break;
- }
- check_invariants();
- this->m_time++;
- this->augment(connecting_edge); //augment that path
- check_invariants();
- this->adopt(); //rebuild search tree structure
- check_invariants();
- }
-
- //check if flow is the sum of outgoing edges of src
- tOutEdgeIterator ei, e_end;
- tEdgeVal src_sum = 0;
- for(tie(ei, e_end) = out_edges(this->m_source, this->m_g); ei != e_end; ++ei){
- src_sum += this->m_cap_map[*ei] - this->m_res_cap_map[*ei];
- }
- BOOST_CHECK(this->m_flow == src_sum);
- //check if flow is the sum of ingoing edges of sink
- tEdgeVal sink_sum = 0;
- for(tie(ei, e_end) = out_edges(this->m_sink, this->m_g); ei != e_end; ++ei){
- tEdge in_edge = this->m_rev_edge_map[*ei];
- sink_sum += this->m_cap_map[in_edge] - this->m_res_cap_map[in_edge];
- }
- BOOST_CHECK(this->m_flow == sink_sum);
- return this->m_flow;
- }
-};
-
-long test_algorithms_invariant(int n_verts, int n_edges, std::size_t seed)
-{
- typedef adjacency_list_traits<vecS, vecS, directedS> tVectorTraits;
- typedef adjacency_list<vecS, vecS, directedS,
- property<vertex_index_t, long,
- property<vertex_predecessor_t, tVectorTraits::edge_descriptor,
- property<vertex_color_t, default_color_type,
- property<vertex_distance_t, long> > > >,
- property<edge_capacity_t, long,
- property<edge_residual_capacity_t, long,
- property<edge_reverse_t, tVectorTraits::edge_descriptor > > > > tVectorGraph;
-
- tVectorGraph g;
-
- graph_traits<tVectorGraph>::vertex_descriptor src, sink;
- tie(src,sink) = fill_random_max_flow_graph(g, get(edge_capacity,g), get(edge_reverse, g), n_verts, n_edges, seed);
-
- typedef property_map<tVectorGraph, edge_capacity_t>::type tEdgeCapMap;
- typedef property_map<tVectorGraph, edge_residual_capacity_t>::type tEdgeResCapMap;
- typedef property_map<tVectorGraph, edge_reverse_t>::type tRevEdgeMap;
- typedef property_map<tVectorGraph, vertex_predecessor_t>::type tVertexPredMap;
- typedef property_map<tVectorGraph, vertex_color_t>::type tVertexColorMap;
- typedef property_map<tVectorGraph, vertex_distance_t>::type tDistanceMap;
- typedef property_map<tVectorGraph, vertex_index_t>::type tIndexMap;
- typedef kolmogorov_test<tVectorGraph, tEdgeCapMap, tEdgeResCapMap, tRevEdgeMap, tVertexPredMap, tVertexColorMap, tDistanceMap, tIndexMap> tKolmo;
- tKolmo instance(g, src, sink);
- return instance.test();
-}
-
-int test_main(int argc, char* argv[])
-{
- int n_verts = 10;
- int n_edges = 500;
- std::size_t seed = 1;
-
- if (argc > 1) n_verts = lexical_cast<int>(argv[1]);
- if (argc > 2) n_edges = lexical_cast<int>(argv[2]);
- if (argc > 3) seed = lexical_cast<std::size_t>(argv[3]);
-
- //we need at least 2 vertices to create src and sink in random graphs
- //this case is also caught in kolmogorov_max_flow
- if (n_verts<2)
- n_verts = 2;
-
- /*
- * below are checks for different calls to kolmogorov_max_flow and different graph-types
- */
- //checks support of vecS storage
- long flow_vecS = test_adjacency_list_vecS(n_verts, n_edges, seed);
- std::cout << "vecS flow: " << flow_vecS << std::endl;
- //checks support of listS storage (especially problems with vertex indices)
- long flow_listS = test_adjacency_list_listS(n_verts, n_edges, seed);
- std::cout << "listS flow: " << flow_listS << std::endl;
- BOOST_CHECK(flow_vecS == flow_listS);
- //checks bundled properties
- long flow_bundles = test_bundled_properties(n_verts, n_edges, seed);
- std::cout << "bundles flow: " << flow_bundles << std::endl;
- BOOST_CHECK(flow_listS == flow_bundles);
- //checks overloads
- long flow_overloads = test_overloads(n_verts, n_edges, seed);
- std::cout << "overloads flow: " << flow_overloads << std::endl;
- BOOST_CHECK(flow_bundles == flow_overloads);
- /*
- * excessive test version where kolmogorov's algorithm invariants are checked
- */
- long flow_invariants = test_algorithms_invariant(n_verts, n_edges, seed);
- std::cout << "invariants flow: " << flow_invariants << std::endl;
- BOOST_CHECK(flow_overloads == flow_invariants);
- return 0;
-}
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 2010-06-22 11:38:02 EDT (Tue, 22 Jun 2010)
@@ -37,7 +37,7 @@
#include <boost/test/minimal.hpp>
//three max_flows we test here
-#include <boost/graph/kolmogorov_max_flow.hpp>
+#include <boost/graph/boykov_kolmogorov_max_flow.hpp>
#include <boost/graph/push_relabel_max_flow.hpp>
#include <boost/graph/edmonds_karp_max_flow.hpp>
//boost utilities we use
@@ -125,11 +125,11 @@
typedef property_traits< property_map<Graph, edge_capacity_t>::const_type>::value_type tEdgeVal;
- tEdgeVal kolmo = kolmogorov_max_flow(g,source_vertex,sink_vertex);
+ tEdgeVal bk = boykov_kolmogorov_max_flow(g,source_vertex,sink_vertex);
tEdgeVal push_relabel = push_relabel_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( bk == push_relabel );
BOOST_REQUIRE( push_relabel == edmonds_karp );
return 0;
Modified: trunk/status/explicit-failures-markup.xml
==============================================================================
--- trunk/status/explicit-failures-markup.xml (original)
+++ trunk/status/explicit-failures-markup.xml 2010-06-22 11:38:02 EDT (Tue, 22 Jun 2010)
@@ -1864,7 +1864,7 @@
<note author="Jeremiah Willcock" refid="2"/>
</mark-expected-failures>
<mark-expected-failures>
- <test name="kolmogorov_max_flow_test"/>
+ <test name="boykov_kolmogorov_max_flow_test"/>
<test name="max_flow_test"/>
<toolset name="acc*"/>
<note author="Markus Schoepflin" refid="45"/>
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