Subject: [Boost-commit] svn:boost r70703 - in branches/release: . boost boost/algorithm/string boost/archive boost/bimap boost/config boost/detail boost/filesystem boost/fusion boost/fusion/container/list/detail boost/gil boost/graph boost/graph/detail boost/graph/distributed boost/icl boost/integer boost/interprocess boost/intrusive boost/io boost/iostreams boost/iterator boost/math boost/msm boost/numeric/ublas boost/pool boost/program_options boost/program_options/detail boost/property_tree boost/range boost/regex boost/serialization boost/signals boost/signals2 boost/spirit boost/spirit/home boost/spirit/home/karma boost/spirit/home/support boost/statechart boost/system boost/tr1 boost/type_traits boost/typeof boost/utility boost/uuid boost/variant boost/wave doc libs libs/algorithm/string libs/array libs/array/doc libs/array/test libs/bimap libs/config libs/date_time libs/filesystem libs/fusion libs/graph/doc libs/graph/test libs/graph_parallel libs/icl libs/icl/doc libs/icl/doc/html libs/icl/doc/html/header/boost/icl libs/icl/test libs/icl/test/test_doc_code_ libs/integer libs/interprocess libs/intrusive libs/io libs/io/doc libs/math libs/math/doc/sf_and_dist libs/math/doc/sf_and_dist/html/math_toolkit/main_overview libs/mpi/build libs/mpl/doc/refmanual libs/mpl/doc/src/refmanual libs/msm libs/numeric/ublas libs/numeric/ublas/doc libs/parameter/doc/html libs/pool libs/program_options libs/program_options/test libs/property_tree libs/range libs/regex libs/serialization libs/serialization/doc libs/serialization/example libs/serialization/src libs/serialization/test libs/serialization/vc7ide libs/signals libs/signals2 libs/spirit libs/spirit/classic/example libs/spirit/doc libs/spirit/example libs/spirit/phoenix libs/spirit/test libs/spirit/test/qi libs/statechart libs/static_assert libs/system libs/timer libs/tr1 libs/type_traits libs/type_traits/doc libs/typeof/doc libs/units/test libs/utility libs/utility/swap/test libs/uuid libs/wave more status tools tools/bcp tools/build/v2 tools/quickbook tools/quickbook/doc tools/quickbook/src tools/quickbook/test tools/regression tools/regression/src tools/release tools/wave
From: jewillco_at_[hidden]
Date: 2011-03-29 14:56:58
Author: jewillco
Date: 2011-03-29 14:56:56 EDT (Tue, 29 Mar 2011)
New Revision: 70703
URL: http://svn.boost.org/trac/boost/changeset/70703
Log:
Merged r67703-67704,68155,69263,69629,69726 from trunk
Removed:
branches/release/boost/graph/detail/is_same.hpp
branches/release/boost/graph/kolmogorov_max_flow.hpp
branches/release/libs/graph/doc/kolmogorov_max_flow.html
Properties modified:
branches/release/ (props changed)
branches/release/INSTALL (props changed)
branches/release/Jamroot (props changed)
branches/release/LICENSE_1_0.txt (props changed)
branches/release/boost/ (props changed)
branches/release/boost-build.jam (props changed)
branches/release/boost.css (props changed)
branches/release/boost.png (props changed)
branches/release/boost/algorithm/string/ (props changed)
branches/release/boost/archive/ (props changed)
branches/release/boost/archive/basic_binary_iarchive.hpp (props changed)
branches/release/boost/bimap/ (props changed)
branches/release/boost/concept_check.hpp (props changed)
branches/release/boost/config/ (props changed)
branches/release/boost/config.hpp (props changed)
branches/release/boost/detail/ (props changed)
branches/release/boost/detail/endian.hpp (props changed)
branches/release/boost/filesystem/ (props changed)
branches/release/boost/filesystem.hpp (props changed)
branches/release/boost/fusion/ (props changed)
branches/release/boost/fusion/container/list/detail/build_cons.hpp (props changed)
branches/release/boost/gil/ (props changed)
branches/release/boost/graph/ (props changed)
branches/release/boost/icl/ (props changed)
branches/release/boost/integer/ (props changed)
branches/release/boost/interprocess/ (props changed)
branches/release/boost/intrusive/ (props changed)
branches/release/boost/io/ (props changed)
branches/release/boost/iostreams/ (props changed)
branches/release/boost/iterator/iterator_facade.hpp (props changed)
branches/release/boost/math/ (props changed)
branches/release/boost/math_fwd.hpp (props changed)
branches/release/boost/msm/ (props changed)
branches/release/boost/numeric/ublas/ (props changed)
branches/release/boost/numeric/ublas/functional.hpp (props changed)
branches/release/boost/pool/ (props changed)
branches/release/boost/program_options/ (props changed)
branches/release/boost/program_options/detail/parsers.hpp (props changed)
branches/release/boost/program_options/parsers.hpp (props changed)
branches/release/boost/property_tree/ (props changed)
branches/release/boost/range/ (props changed)
branches/release/boost/regex/ (props changed)
branches/release/boost/serialization/ (props changed)
branches/release/boost/signals/ (props changed)
branches/release/boost/signals2/ (props changed)
branches/release/boost/signals2.hpp (props changed)
branches/release/boost/spirit/ (props changed)
branches/release/boost/spirit/home/ (props changed)
branches/release/boost/spirit/home/karma/ (props changed)
branches/release/boost/spirit/home/support/attributes.hpp (props changed)
branches/release/boost/statechart/ (props changed)
branches/release/boost/static_assert.hpp (props changed)
branches/release/boost/system/ (props changed)
branches/release/boost/token_functions.hpp (props changed)
branches/release/boost/tr1/ (props changed)
branches/release/boost/type_traits/ (props changed)
branches/release/boost/typeof/message.hpp (props changed)
branches/release/boost/typeof/register_functions.hpp (props changed)
branches/release/boost/typeof/register_functions_iterate.hpp (props changed)
branches/release/boost/typeof/typeof.hpp (props changed)
branches/release/boost/typeof/unsupported.hpp (props changed)
branches/release/boost/utility/ (props changed)
branches/release/boost/utility/value_init.hpp (props changed)
branches/release/boost/uuid/ (props changed)
branches/release/boost/variant/ (props changed)
branches/release/boost/version.hpp (props changed)
branches/release/boost/wave/ (props changed)
branches/release/bootstrap.bat (props changed)
branches/release/bootstrap.sh (props changed)
branches/release/doc/ (props changed)
branches/release/index.htm (props changed)
branches/release/index.html (props changed)
branches/release/libs/ (props changed)
branches/release/libs/algorithm/string/ (props changed)
branches/release/libs/array/ (props changed)
branches/release/libs/array/doc/array.xml (props changed)
branches/release/libs/array/test/Jamfile.v2 (props changed)
branches/release/libs/array/test/array0.cpp (props changed)
branches/release/libs/array/test/array6.cpp (props changed)
branches/release/libs/bimap/ (props changed)
branches/release/libs/config/ (props changed)
branches/release/libs/date_time/ (props changed)
branches/release/libs/filesystem/ (props changed)
branches/release/libs/fusion/ (props changed)
branches/release/libs/graph_parallel/ (props changed)
branches/release/libs/icl/ (props changed)
branches/release/libs/icl/doc/ (props changed)
branches/release/libs/icl/doc/html/ (props changed)
branches/release/libs/icl/doc/html/header/boost/icl/ (props changed)
branches/release/libs/icl/test/ (props changed)
branches/release/libs/icl/test/test_doc_code_/ (props changed)
branches/release/libs/integer/ (props changed)
branches/release/libs/interprocess/ (props changed)
branches/release/libs/intrusive/ (props changed)
branches/release/libs/io/ (props changed)
branches/release/libs/io/doc/ (props changed)
branches/release/libs/libraries.htm (props changed)
branches/release/libs/maintainers.txt (props changed)
branches/release/libs/math/ (props changed)
branches/release/libs/math/doc/sf_and_dist/faq.qbk (props changed)
branches/release/libs/math/doc/sf_and_dist/html/math_toolkit/main_overview/faq.html (props changed)
branches/release/libs/mpi/build/ (props changed)
branches/release/libs/mpl/doc/refmanual/broken-compiler-workarounds.html (props changed)
branches/release/libs/mpl/doc/refmanual/categorized-index-concepts.html (props changed)
branches/release/libs/mpl/doc/refmanual/cfg-no-preprocessed-headers.html (props changed)
branches/release/libs/mpl/doc/refmanual/composition-and-argument-binding.html (props changed)
branches/release/libs/mpl/doc/refmanual/data-types-concepts.html (props changed)
branches/release/libs/mpl/doc/refmanual/data-types-miscellaneous.html (props changed)
branches/release/libs/mpl/doc/refmanual/extensible-associative-sequence.html (props changed)
branches/release/libs/mpl/doc/refmanual/inserter-class.html (props changed)
branches/release/libs/mpl/doc/refmanual/tag-dispatched-metafunction.html (props changed)
branches/release/libs/mpl/doc/refmanual/trivial-metafunctions-summary.html (props changed)
branches/release/libs/mpl/doc/src/refmanual/Iterators-Iterator.rst (props changed)
branches/release/libs/msm/ (props changed)
branches/release/libs/numeric/ublas/ (props changed)
branches/release/libs/numeric/ublas/doc/ (props changed)
branches/release/libs/parameter/doc/html/index.html (props changed)
branches/release/libs/pool/ (props changed)
branches/release/libs/program_options/ (props changed)
branches/release/libs/program_options/test/parsers_test.cpp (props changed)
branches/release/libs/property_tree/ (props changed)
branches/release/libs/range/ (props changed)
branches/release/libs/regex/ (props changed)
branches/release/libs/serialization/ (props changed)
branches/release/libs/serialization/doc/ (props changed)
branches/release/libs/serialization/example/ (props changed)
branches/release/libs/serialization/src/ (props changed)
branches/release/libs/serialization/test/test_diamond_complex.cpp (props changed)
branches/release/libs/serialization/vc7ide/ (props changed)
branches/release/libs/signals/ (props changed)
branches/release/libs/signals2/ (props changed)
branches/release/libs/spirit/ (props changed)
branches/release/libs/spirit/classic/example/ (props changed)
branches/release/libs/spirit/doc/ (props changed)
branches/release/libs/spirit/example/ (props changed)
branches/release/libs/spirit/phoenix/ (props changed)
branches/release/libs/spirit/test/ (props changed)
branches/release/libs/spirit/test/qi/optional.cpp (props changed)
branches/release/libs/statechart/ (props changed)
branches/release/libs/static_assert/ (props changed)
branches/release/libs/system/ (props changed)
branches/release/libs/timer/ (props changed)
branches/release/libs/tr1/ (props changed)
branches/release/libs/type_traits/ (props changed)
branches/release/libs/type_traits/doc/ (props changed)
branches/release/libs/typeof/doc/typeof.qbk (props changed)
branches/release/libs/units/test/ (props changed)
branches/release/libs/utility/ (props changed)
branches/release/libs/utility/assert.html (props changed)
branches/release/libs/utility/assert_test.cpp (props changed)
branches/release/libs/utility/swap.html (props changed)
branches/release/libs/utility/swap/test/std_bitset.cpp (props changed)
branches/release/libs/utility/value_init.htm (props changed)
branches/release/libs/utility/value_init_test.cpp (props changed)
branches/release/libs/uuid/ (props changed)
branches/release/libs/wave/ (props changed)
branches/release/more/ (props changed)
branches/release/rst.css (props changed)
branches/release/status/ (props changed)
branches/release/status/Jamfile.v2 (props changed)
branches/release/status/explicit-failures-markup.xml (props changed)
branches/release/tools/ (props changed)
branches/release/tools/bcp/ (props changed)
branches/release/tools/build/v2/ (props changed)
branches/release/tools/quickbook/ (props changed)
branches/release/tools/quickbook/doc/ (props changed)
branches/release/tools/quickbook/src/ (props changed)
branches/release/tools/quickbook/test/ (props changed)
branches/release/tools/regression/ (props changed)
branches/release/tools/regression/src/library_status.cpp (props changed)
branches/release/tools/release/ (props changed)
branches/release/tools/wave/ (props changed)
Text files modified:
branches/release/boost/graph/distributed/connected_components.hpp | 8 ++++----
branches/release/boost/graph/graph_concepts.hpp | 4 ++--
branches/release/boost/graph/graph_traits.hpp | 1 +
branches/release/libs/graph/doc/table_of_contents.html | 5 -----
branches/release/libs/graph/test/astar_search_test.cpp | 1 +
5 files changed, 8 insertions(+), 11 deletions(-)
Deleted: branches/release/boost/graph/detail/is_same.hpp
==============================================================================
--- branches/release/boost/graph/detail/is_same.hpp 2011-03-29 14:56:56 EDT (Tue, 29 Mar 2011)
+++ (empty file)
@@ -1,48 +0,0 @@
-//=======================================================================
-// Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
-// Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
-//
-// 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 BOOST_GRAPH_DETAIL_IS_SAME_HPP
-#define BOOST_GRAPH_DETAIL_IS_SAME_HPP
-
-// Deprecate the use of this header.
-// TODO: Remove this file from trunk/release in 1.41/1.42.
-#if defined(_MSC_VER) || defined(__BORLANDC__) || defined(__DMC__)
-# pragma message ("Warning: This header is deprecated. Please use: boost/type_traits/is_same.hpp")
-#elif defined(__GNUC__) || defined(__HP_aCC) || defined(__SUNPRO_CC) || defined(__IBMCPP__)
-# warning "This header is deprecated. Please use: boost/type_traits/is_same.hpp"
-#endif
-
-#include <boost/mpl/if.hpp>
-
-namespace boost {
- struct false_tag;
- struct true_tag;
-
- namespace graph_detail {
-
-#if !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
- template <class U, class V>
- struct is_same {
- typedef boost::false_tag is_same_tag;
- };
- template <class U>
- struct is_same<U, U> {
- typedef boost::true_tag is_same_tag;
- };
-#else
- template <class U, class V>
- struct is_same {
- enum { Unum = U::num, Vnum = V::num };
- typedef typename mpl::if_c< (Unum == Vnum),
- boost::true_tag, boost::false_tag>::type is_same_tag;
- };
-#endif
- } // namespace graph_detail
-} // namespace boost
-
-#endif
Modified: branches/release/boost/graph/distributed/connected_components.hpp
==============================================================================
--- branches/release/boost/graph/distributed/connected_components.hpp (original)
+++ branches/release/boost/graph/distributed/connected_components.hpp 2011-03-29 14:56:56 EDT (Tue, 29 Mar 2011)
@@ -555,10 +555,10 @@
adj[*liter].begin(), adj[*liter].end() );
#ifdef PBGL_IN_PLACE_MERGE
#ifdef PBGL_SORT_ASSERT
- BOOST_ASSERT(__gnu_cxx::is_sorted(my_adj.begin(),
+ BOOST_ASSERT(::boost::detail::is_sorted(my_adj.begin(),
my_adj.end() - adj[*liter].size(),
std::less<vertex_descriptor>()));
- BOOST_ASSERT(__gnu_cxx::is_sorted(my_adj.end() - adj[*liter].size(),
+ BOOST_ASSERT(::boost::detail::is_sorted(my_adj.end() - adj[*liter].size(),
my_adj.end(),
std::less<vertex_descriptor>()));
#endif
@@ -603,10 +603,10 @@
#ifdef PBGL_IN_PLACE_MERGE
std::size_t num_incoming_edges = incoming_edges.size();
#ifdef PBGL_SORT_ASSERT
- BOOST_ASSERT(__gnu_cxx::is_sorted(my_adj.begin(),
+ BOOST_ASSERT(::boost::detail::is_sorted(my_adj.begin(),
my_adj.end() - (num_incoming_edges-1),
std::less<vertex_descriptor>()));
- BOOST_ASSERT(__gnu_cxx::is_sorted(my_adj.end() - (num_incoming_edges-1),
+ BOOST_ASSERT(::boost::detail::is_sorted(my_adj.end() - (num_incoming_edges-1),
my_adj.end(),
std::less<vertex_descriptor>()));
#endif
Modified: branches/release/boost/graph/graph_concepts.hpp
==============================================================================
--- branches/release/boost/graph/graph_concepts.hpp (original)
+++ branches/release/boost/graph/graph_concepts.hpp 2011-03-29 14:56:56 EDT (Tue, 29 Mar 2011)
@@ -342,7 +342,7 @@
}
G g;
typename graph_traits<G>::vertex_descriptor v;
- typename vertex_property<G>::type vp;
+ typename vertex_property_type<G>::type vp;
};
BOOST_concept(EdgeMutablePropertyGraph,(G))
@@ -356,7 +356,7 @@
G g;
std::pair<edge_descriptor, bool> p;
typename graph_traits<G>::vertex_descriptor u, v;
- typename edge_property<G>::type ep;
+ typename edge_property_type<G>::type ep;
};
BOOST_concept(AdjacencyMatrix,(G))
Modified: branches/release/boost/graph/graph_traits.hpp
==============================================================================
--- branches/release/boost/graph/graph_traits.hpp (original)
+++ branches/release/boost/graph/graph_traits.hpp 2011-03-29 14:56:56 EDT (Tue, 29 Mar 2011)
@@ -12,6 +12,7 @@
#include <boost/config.hpp>
#include <iterator>
+#include <utility> /* Primarily for std::pair */
#include <boost/tuple/tuple.hpp>
#include <boost/mpl/if.hpp>
#include <boost/mpl/bool.hpp>
Deleted: branches/release/boost/graph/kolmogorov_max_flow.hpp
==============================================================================
--- branches/release/boost/graph/kolmogorov_max_flow.hpp 2011-03-29 14:56:56 EDT (Tue, 29 Mar 2011)
+++ (empty file)
@@ -1,814 +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)
-
-#ifndef BOOST_KOLMOGOROV_MAX_FLOW_HPP
-#define BOOST_KOLMOGOROV_MAX_FLOW_HPP
-
-#if defined(_MSC_VER) || defined(__BORLANDC__) || defined(__DMC__)
-# pragma message ("The kolmogorov_max_flow.hpp header is deprecated and will be removed in Boost 1.47. Use boykov_kolmogorov_max_flow.hpp instead.")
-#elif defined(__GNUC__) || defined(__HP_aCC) || defined(__SUNPRO_CC) || defined(__IBMCPP__)
-# warning "The kolmogorov_max_flow.hpp header is deprecated and will be removed in Boost 1.47. Use boykov_kolmogorov_max_flow.hpp instead."
-#endif
-
-#include <boost/config.hpp>
-#include <cassert>
-#include <vector>
-#include <list>
-#include <utility>
-#include <iosfwd>
-#include <algorithm> // for std::min and std::max
-
-#include <boost/pending/queue.hpp>
-#include <boost/limits.hpp>
-#include <boost/property_map/property_map.hpp>
-#include <boost/none_t.hpp>
-#include <boost/graph/graph_concepts.hpp>
-#include <boost/graph/named_function_params.hpp>
-#include <boost/graph/lookup_edge.hpp>
-
-namespace boost {
- namespace detail {
-
- template <class Graph,
- class EdgeCapacityMap,
- class ResidualCapacityEdgeMap,
- class ReverseEdgeMap,
- class PredecessorMap,
- class ColorMap,
- class DistanceMap,
- class IndexMap>
- class kolmogorov{
- typedef typename property_traits<EdgeCapacityMap>::value_type tEdgeVal;
- typedef graph_traits<Graph> tGraphTraits;
- typedef typename tGraphTraits::vertex_iterator vertex_iterator;
- typedef typename tGraphTraits::vertex_descriptor vertex_descriptor;
- typedef typename tGraphTraits::edge_descriptor edge_descriptor;
- typedef typename tGraphTraits::edge_iterator edge_iterator;
- typedef typename tGraphTraits::out_edge_iterator out_edge_iterator;
- typedef boost::queue<vertex_descriptor> tQueue; //queue of vertices, used in adoption-stage
- typedef typename property_traits<ColorMap>::value_type tColorValue;
- typedef color_traits<tColorValue> tColorTraits;
- typedef typename property_traits<DistanceMap>::value_type tDistanceVal;
-
- public:
- kolmogorov(Graph& g,
- EdgeCapacityMap cap,
- ResidualCapacityEdgeMap res,
- ReverseEdgeMap rev,
- PredecessorMap pre,
- ColorMap color,
- DistanceMap dist,
- IndexMap idx,
- vertex_descriptor src,
- vertex_descriptor sink):
- m_g(g),
- m_index_map(idx),
- m_cap_map(cap),
- m_res_cap_map(res),
- m_rev_edge_map(rev),
- m_pre_map(pre),
- m_tree_map(color),
- m_dist_map(dist),
- m_source(src),
- m_sink(sink),
- m_active_nodes(),
- m_in_active_list_vec(num_vertices(g), false),
- m_in_active_list_map(make_iterator_property_map(m_in_active_list_vec.begin(), m_index_map)),
- m_has_parent_vec(num_vertices(g), false),
- m_has_parent_map(make_iterator_property_map(m_has_parent_vec.begin(), m_index_map)),
- m_time_vec(num_vertices(g), 0),
- m_time_map(make_iterator_property_map(m_time_vec.begin(), m_index_map)),
- m_flow(0),
- m_time(1),
- m_last_grow_vertex(graph_traits<Graph>::null_vertex()){
- // initialize the color-map with gray-values
- vertex_iterator vi, v_end;
- for(boost::tie(vi, v_end) = vertices(m_g); vi != v_end; ++vi){
- set_tree(*vi, tColorTraits::gray());
- }
- // Initialize flow to zero which means initializing
- // the residual capacity equal to the capacity
- edge_iterator ei, e_end;
- for(boost::tie(ei, e_end) = edges(m_g); ei != e_end; ++ei) {
- m_res_cap_map[*ei] = m_cap_map[*ei];
- assert(m_rev_edge_map[m_rev_edge_map[*ei]] == *ei); //check if the reverse edge map is build up properly
- }
- //init the search trees with the two terminals
- set_tree(m_source, tColorTraits::black());
- set_tree(m_sink, tColorTraits::white());
- m_time_map[m_source] = 1;
- m_time_map[m_sink] = 1;
- }
-
- ~kolmogorov(){}
-
- tEdgeVal max_flow(){
- //augment direct paths from SOURCE->SINK and SOURCE->VERTEX->SINK
- augment_direct_paths();
- //start the main-loop
- while(true){
- bool path_found;
- edge_descriptor connecting_edge;
- boost::tie(connecting_edge, path_found) = grow(); //find a path from source to sink
- if(!path_found){
- //we're finished, no more paths were found
- break;
- }
- ++m_time;
- augment(connecting_edge); //augment that path
- adopt(); //rebuild search tree structure
- }
- return m_flow;
- }
-
- //the complete class is protected, as we want access to members in derived test-class (see $(BOOST_ROOT)/libs/graph/test/kolmogorov_max_flow_test.cpp)
- protected:
- void augment_direct_paths(){
- //in a first step, we augment all direct paths from source->NODE->sink
- //and additionally paths from source->sink
- //this improves especially graphcuts for segmentation, as most of the nodes have source/sink connects
- //but shouldn't have an impact on other maxflow problems (this is done in grow() anyway)
- out_edge_iterator ei, e_end;
- for(boost::tie(ei, e_end) = out_edges(m_source, m_g); ei != e_end; ++ei){
- edge_descriptor from_source = *ei;
- vertex_descriptor current_node = target(from_source, m_g);
- if(current_node == m_sink){
- tEdgeVal cap = m_res_cap_map[from_source];
- m_res_cap_map[from_source] = 0;
- m_flow += cap;
- continue;
- }
- edge_descriptor to_sink;
- bool is_there;
- boost::tie(to_sink, is_there) = lookup_edge(current_node, m_sink, m_g);
- if(is_there){
- tEdgeVal cap_from_source = m_res_cap_map[from_source];
- tEdgeVal cap_to_sink = m_res_cap_map[to_sink];
- if(cap_from_source > cap_to_sink){
- set_tree(current_node, tColorTraits::black());
- add_active_node(current_node);
- set_edge_to_parent(current_node, from_source);
- m_dist_map[current_node] = 1;
- m_time_map[current_node] = 1;
- //add stuff to flow and update residuals
- //we dont need to update reverse_edges, as incoming/outgoing edges to/from source/sink don't count for max-flow
- m_res_cap_map[from_source] -= cap_to_sink;
- m_res_cap_map[to_sink] = 0;
- m_flow += cap_to_sink;
- } else if(cap_to_sink > 0){
- set_tree(current_node, tColorTraits::white());
- add_active_node(current_node);
- set_edge_to_parent(current_node, to_sink);
- m_dist_map[current_node] = 1;
- m_time_map[current_node] = 1;
- //add stuff to flow and update residuals
- //we dont need to update reverse_edges, as incoming/outgoing edges to/from source/sink don't count for max-flow
- m_res_cap_map[to_sink] -= cap_from_source;
- m_res_cap_map[from_source] = 0;
- m_flow += cap_from_source;
- }
- } else if(m_res_cap_map[from_source]){
- //there is no sink connect, so we can't augment this path
- //but to avoid adding m_source to the active nodes, we just activate this node and set the approciate things
- set_tree(current_node, tColorTraits::black());
- set_edge_to_parent(current_node, from_source);
- m_dist_map[current_node] = 1;
- m_time_map[current_node] = 1;
- add_active_node(current_node);
- }
- }
- for(boost::tie(ei, e_end) = out_edges(m_sink, m_g); ei != e_end; ++ei){
- edge_descriptor to_sink = m_rev_edge_map[*ei];
- vertex_descriptor current_node = source(to_sink, m_g);
- if(m_res_cap_map[to_sink]){
- set_tree(current_node, tColorTraits::white());
- set_edge_to_parent(current_node, to_sink);
- m_dist_map[current_node] = 1;
- m_time_map[current_node] = 1;
- add_active_node(current_node);
- }
- }
- }
-
- /**
- * returns a pair of an edge and a boolean. if the bool is true, the edge is a connection of a found path from s->t , read "the link" and
- * source(returnVal, m_g) is the end of the path found in the source-tree
- * target(returnVal, m_g) is the beginning of the path found in the sink-tree
- */
- std::pair<edge_descriptor, bool> grow(){
- assert(m_orphans.empty());
- vertex_descriptor current_node;
- while((current_node = get_next_active_node()) != graph_traits<Graph>::null_vertex()){ //if there is one
- assert(get_tree(current_node) != tColorTraits::gray() && (has_parent(current_node) || current_node==m_source || current_node==m_sink));
- if(get_tree(current_node) == tColorTraits::black()){
- //source tree growing
- out_edge_iterator ei, e_end;
- if(current_node != m_last_grow_vertex){
- m_last_grow_vertex = current_node;
- boost::tie(m_last_grow_edge_it, m_last_grow_edge_end) = out_edges(current_node, m_g);
- }
- for(; m_last_grow_edge_it != m_last_grow_edge_end; ++m_last_grow_edge_it){
- edge_descriptor out_edge = *m_last_grow_edge_it;
- if(m_res_cap_map[out_edge] > 0){ //check if we have capacity left on this edge
- vertex_descriptor other_node = target(out_edge, m_g);
- if(get_tree(other_node) == tColorTraits::gray()){ //it's a free node
- set_tree(other_node, tColorTraits::black()); //aquire other node to our search tree
- set_edge_to_parent(other_node, out_edge); //set us as parent
- m_dist_map[other_node] = m_dist_map[current_node] + 1; //and update the distance-heuristic
- m_time_map[other_node] = m_time_map[current_node];
- add_active_node(other_node);
- } else if(get_tree(other_node) == tColorTraits::black()){
- if(is_closer_to_terminal(current_node, other_node)){ //we do this to get shorter paths. check if we are nearer to the source as its parent is
- set_edge_to_parent(other_node, out_edge);
- m_dist_map[other_node] = m_dist_map[current_node] + 1;
- m_time_map[other_node] = m_time_map[current_node];
- }
- } else{
- assert(get_tree(other_node)==tColorTraits::white());
- //kewl, found a path from one to the other search tree, return the connecting edge in src->sink dir
- return std::make_pair(out_edge, true);
- }
- }
- } //for all out-edges
- } //source-tree-growing
- else{
- assert(get_tree(current_node) == tColorTraits::white());
- out_edge_iterator ei, e_end;
- if(current_node != m_last_grow_vertex){
- m_last_grow_vertex = current_node;
- boost::tie(m_last_grow_edge_it, m_last_grow_edge_end) = out_edges(current_node, m_g);
- }
- for(; m_last_grow_edge_it != m_last_grow_edge_end; ++m_last_grow_edge_it){
- edge_descriptor in_edge = m_rev_edge_map[*m_last_grow_edge_it];
- if(m_res_cap_map[in_edge] > 0){ //check if there is capacity left
- vertex_descriptor other_node = source(in_edge, m_g);
- if(get_tree(other_node) == tColorTraits::gray()){ //it's a free node
- set_tree(other_node, tColorTraits::white()); //aquire that node to our search tree
- set_edge_to_parent(other_node, in_edge); //set us as parent
- add_active_node(other_node); //activate that node
- m_dist_map[other_node] = m_dist_map[current_node] + 1; //set its distance
- m_time_map[other_node] = m_time_map[current_node]; //and time
- } else if(get_tree(other_node) == tColorTraits::white()){
- if(is_closer_to_terminal(current_node, other_node)){
- //we are closer to the sink than its parent is, so we "adopt" him
- set_edge_to_parent(other_node, in_edge);
- m_dist_map[other_node] = m_dist_map[current_node] + 1;
- m_time_map[other_node] = m_time_map[current_node];
- }
- } else{
- assert(get_tree(other_node)==tColorTraits::black());
- //kewl, found a path from one to the other search tree, return the connecting edge in src->sink dir
- return std::make_pair(in_edge, true);
- }
- }
- } //for all out-edges
- } //sink-tree growing
- //all edges of that node are processed, and no more paths were found. so remove if from the front of the active queue
- finish_node(current_node);
- } //while active_nodes not empty
- return std::make_pair(edge_descriptor(), false); //no active nodes anymore and no path found, we're done
- }
-
- /**
- * augments path from s->t and updates residual graph
- * source(e, m_g) is the end of the path found in the source-tree
- * target(e, m_g) is the beginning of the path found in the sink-tree
- * this phase generates orphans on satured edges, if the attached verts are from different search-trees
- * orphans are ordered in distance to sink/source. first the farest from the source are front_inserted into the orphans list,
- * and after that the sink-tree-orphans are front_inserted. when going to adoption stage the orphans are popped_front, and so we process the nearest
- * verts to the terminals first
- */
- void augment(edge_descriptor e){
- assert(get_tree(target(e, m_g)) == tColorTraits::white());
- assert(get_tree(source(e, m_g)) == tColorTraits::black());
- assert(m_orphans.empty());
-
- const tEdgeVal bottleneck = find_bottleneck(e);
- //now we push the found flow through the path
- //for each edge we saturate we have to look for the verts that belong to that edge, one of them becomes an orphans
- //now process the connecting edge
- m_res_cap_map[e] -= bottleneck;
- assert(m_res_cap_map[e] >= 0);
- m_res_cap_map[m_rev_edge_map[e]] += bottleneck;
-
- //now we follow the path back to the source
- vertex_descriptor current_node = source(e, m_g);
- while(current_node != m_source){
- edge_descriptor pred = get_edge_to_parent(current_node);
- m_res_cap_map[pred] -= bottleneck;
- assert(m_res_cap_map[pred] >= 0);
- m_res_cap_map[m_rev_edge_map[pred]] += bottleneck;
- if(m_res_cap_map[pred] == 0){
- set_no_parent(current_node);
- m_orphans.push_front(current_node);
- }
- current_node = source(pred, m_g);
- }
- //then go forward in the sink-tree
- current_node = target(e, m_g);
- while(current_node != m_sink){
- edge_descriptor pred = get_edge_to_parent(current_node);
- m_res_cap_map[pred] -= bottleneck;
- assert(m_res_cap_map[pred] >= 0);
- m_res_cap_map[m_rev_edge_map[pred]] += bottleneck;
- if(m_res_cap_map[pred] == 0){
- set_no_parent(current_node);
- m_orphans.push_front(current_node);
- }
- current_node = target(pred, m_g);
- }
- //and add it to the max-flow
- m_flow += bottleneck;
- }
-
- /**
- * returns the bottleneck of a s->t path (end_of_path is last vertex in source-tree, begin_of_path is first vertex in sink-tree)
- */
- inline tEdgeVal find_bottleneck(edge_descriptor e){
- BOOST_USING_STD_MIN();
- tEdgeVal minimum_cap = m_res_cap_map[e];
- vertex_descriptor current_node = source(e, m_g);
- //first go back in the source tree
- while(current_node != m_source){
- edge_descriptor pred = get_edge_to_parent(current_node);
- minimum_cap = min BOOST_PREVENT_MACRO_SUBSTITUTION(minimum_cap, m_res_cap_map[pred]);
- current_node = source(pred, m_g);
- }
- //then go forward in the sink-tree
- current_node = target(e, m_g);
- while(current_node != m_sink){
- edge_descriptor pred = get_edge_to_parent(current_node);
- minimum_cap = min BOOST_PREVENT_MACRO_SUBSTITUTION(minimum_cap, m_res_cap_map[pred]);
- current_node = target(pred, m_g);
- }
- return minimum_cap;
- }
-
- /**
- * rebuild search trees
- * empty the queue of orphans, and find new parents for them or just drop them from the search trees
- */
- void adopt(){
- while(!m_orphans.empty() || !m_child_orphans.empty()){
- vertex_descriptor current_node;
- if(m_child_orphans.empty()){
- //get the next orphan from the main-queue and remove it
- current_node = m_orphans.front();
- m_orphans.pop_front();
- } else{
- current_node = m_child_orphans.front();
- m_child_orphans.pop();
- }
- if(get_tree(current_node) == tColorTraits::black()){
- //we're in the source-tree
- tDistanceVal min_distance = (std::numeric_limits<tDistanceVal>::max)();
- edge_descriptor new_parent_edge;
- out_edge_iterator ei, e_end;
- for(boost::tie(ei, e_end) = out_edges(current_node, m_g); ei != e_end; ++ei){
- const edge_descriptor in_edge = m_rev_edge_map[*ei];
- assert(target(in_edge, m_g) == current_node); //we should be the target of this edge
- if(m_res_cap_map[in_edge] > 0){
- vertex_descriptor other_node = source(in_edge, m_g);
- if(get_tree(other_node) == tColorTraits::black() && has_source_connect(other_node)){
- if(m_dist_map[other_node] < min_distance){
- min_distance = m_dist_map[other_node];
- new_parent_edge = in_edge;
- }
- }
- }
- }
- if(min_distance != (std::numeric_limits<tDistanceVal>::max)()){
- set_edge_to_parent(current_node, new_parent_edge);
- m_dist_map[current_node] = min_distance + 1;
- m_time_map[current_node] = m_time;
- } else{
- m_time_map[current_node] = 0;
- for(boost::tie(ei, e_end) = out_edges(current_node, m_g); ei != e_end; ++ei){
- edge_descriptor in_edge = m_rev_edge_map[*ei];
- vertex_descriptor other_node = source(in_edge, m_g);
- if(get_tree(other_node) == tColorTraits::black() && has_parent(other_node)){
- if(m_res_cap_map[in_edge] > 0){
- add_active_node(other_node);
- }
- if(source(get_edge_to_parent(other_node), m_g) == current_node){
- //we are the parent of that node
- //it has to find a new parent, too
- set_no_parent(other_node);
- m_child_orphans.push(other_node);
- }
- }
- }
- set_tree(current_node, tColorTraits::gray());
- } //no parent found
- } //source-tree-adoption
- else{
- //now we should be in the sink-tree, check that...
- assert(get_tree(current_node) == tColorTraits::white());
- out_edge_iterator ei, e_end;
- edge_descriptor new_parent_edge;
- tDistanceVal min_distance = (std::numeric_limits<tDistanceVal>::max)();
- for(boost::tie(ei, e_end) = out_edges(current_node, m_g); ei != e_end; ++ei){
- const edge_descriptor out_edge = *ei;
- if(m_res_cap_map[out_edge] > 0){
- const vertex_descriptor other_node = target(out_edge, m_g);
- if(get_tree(other_node) == tColorTraits::white() && has_sink_connect(other_node))
- if(m_dist_map[other_node] < min_distance){
- min_distance = m_dist_map[other_node];
- new_parent_edge = out_edge;
- }
- }
- }
- if(min_distance != (std::numeric_limits<tDistanceVal>::max)()){
- set_edge_to_parent(current_node, new_parent_edge);
- m_dist_map[current_node] = min_distance + 1;
- m_time_map[current_node] = m_time;
- } else{
- m_time_map[current_node] = 0;
- for(boost::tie(ei, e_end) = out_edges(current_node, m_g); ei != e_end; ++ei){
- const edge_descriptor out_edge = *ei;
- const vertex_descriptor other_node = target(out_edge, m_g);
- if(get_tree(other_node) == tColorTraits::white() && has_parent(other_node)){
- if(m_res_cap_map[out_edge] > 0){
- add_active_node(other_node);
- }
- if(target(get_edge_to_parent(other_node), m_g) == current_node){
- //we were it's parent, so it has to find a new one, too
- set_no_parent(other_node);
- m_child_orphans.push(other_node);
- }
- }
- }
- set_tree(current_node, tColorTraits::gray());
- } //no parent found
- } //sink-tree adoption
- } //while !orphans.empty()
- } //adopt
-
- /**
- * return next active vertex if there is one, otherwise a null_vertex
- */
- inline vertex_descriptor get_next_active_node(){
- while(true){
- if(m_active_nodes.empty())
- return graph_traits<Graph>::null_vertex();
- vertex_descriptor v = m_active_nodes.front();
-
- if(!has_parent(v) && v != m_source && v != m_sink){ //if it has no parent, this node can't be active(if its not source or sink)
- m_active_nodes.pop();
- m_in_active_list_map[v] = false;
- } else{
- assert(get_tree(v) == tColorTraits::black() || get_tree(v) == tColorTraits::white());
- return v;
- }
- }
- }
-
- /**
- * adds v as an active vertex, but only if its not in the list already
- */
- inline void add_active_node(vertex_descriptor v){
- assert(get_tree(v) != tColorTraits::gray());
- if(m_in_active_list_map[v]){
- return;
- } else{
- m_in_active_list_map[v] = true;
- m_active_nodes.push(v);
- }
- }
-
- /**
- * finish_node removes a node from the front of the active queue (its called in grow phase, if no more paths can be found using this node)
- */
- inline void finish_node(vertex_descriptor v){
- assert(m_active_nodes.front() == v);
- m_active_nodes.pop();
- m_in_active_list_map[v] = false;
- m_last_grow_vertex = graph_traits<Graph>::null_vertex();
- }
-
- /**
- * removes a vertex from the queue of active nodes (actually this does nothing,
- * but checks if this node has no parent edge, as this is the criteria for beeing no more active)
- */
- inline void remove_active_node(vertex_descriptor v){
- assert(!has_parent(v));
- }
-
- /**
- * returns the search tree of v; tColorValue::black() for source tree, white() for sink tree, gray() for no tree
- */
- inline tColorValue get_tree(vertex_descriptor v) const {
- return m_tree_map[v];
- }
-
- /**
- * sets search tree of v; tColorValue::black() for source tree, white() for sink tree, gray() for no tree
- */
- inline void set_tree(vertex_descriptor v, tColorValue t){
- m_tree_map[v] = t;
- }
-
- /**
- * returns edge to parent vertex of v;
- */
- inline edge_descriptor get_edge_to_parent(vertex_descriptor v) const{
- return m_pre_map[v];
- }
-
- /**
- * returns true if the edge stored in m_pre_map[v] is a valid entry
- */
- inline bool has_parent(vertex_descriptor v) const{
- return m_has_parent_map[v];
- }
-
- /**
- * sets edge to parent vertex of v;
- */
- inline void set_edge_to_parent(vertex_descriptor v, edge_descriptor f_edge_to_parent){
- assert(m_res_cap_map[f_edge_to_parent] > 0);
- m_pre_map[v] = f_edge_to_parent;
- m_has_parent_map[v] = true;
- }
-
- /**
- * removes the edge to parent of v (this is done by invalidating the entry an additional map)
- */
- inline void set_no_parent(vertex_descriptor v){
- m_has_parent_map[v] = false;
- }
-
- /**
- * checks if vertex v has a connect to the sink-vertex (@var m_sink)
- * @param v the vertex which is checked
- * @return true if a path to the sink was found, false if not
- */
- inline bool has_sink_connect(vertex_descriptor v){
- tDistanceVal current_distance = 0;
- vertex_descriptor current_vertex = v;
- while(true){
- if(m_time_map[current_vertex] == m_time){
- //we found a node which was already checked this round. use it for distance calculations
- current_distance += m_dist_map[current_vertex];
- break;
- }
- if(current_vertex == m_sink){
- m_time_map[m_sink] = m_time;
- break;
- }
- if(has_parent(current_vertex)){
- //it has a parent, so get it
- current_vertex = target(get_edge_to_parent(current_vertex), m_g);
- ++current_distance;
- } else{
- //no path found
- return false;
- }
- }
- current_vertex=v;
- while(m_time_map[current_vertex] != m_time){
- m_dist_map[current_vertex] = current_distance--;
- m_time_map[current_vertex] = m_time;
- current_vertex = target(get_edge_to_parent(current_vertex), m_g);
- }
- return true;
- }
-
- /**
- * checks if vertex v has a connect to the source-vertex (@var m_source)
- * @param v the vertex which is checked
- * @return true if a path to the source was found, false if not
- */
- inline bool has_source_connect(vertex_descriptor v){
- tDistanceVal current_distance = 0;
- vertex_descriptor current_vertex = v;
- while(true){
- if(m_time_map[current_vertex] == m_time){
- //we found a node which was already checked this round. use it for distance calculations
- current_distance += m_dist_map[current_vertex];
- break;
- }
- if(current_vertex == m_source){
- m_time_map[m_source] = m_time;
- break;
- }
- if(has_parent(current_vertex)){
- //it has a parent, so get it
- current_vertex = source(get_edge_to_parent(current_vertex), m_g);
- ++current_distance;
- } else{
- //no path found
- return false;
- }
- }
- current_vertex=v;
- while(m_time_map[current_vertex] != m_time){
- m_dist_map[current_vertex] = current_distance-- ;
- m_time_map[current_vertex] = m_time;
- current_vertex = source(get_edge_to_parent(current_vertex), m_g);
- }
- return true;
- }
-
- /**
- * returns true, if p is closer to a terminal than q
- */
- inline bool is_closer_to_terminal(vertex_descriptor p, vertex_descriptor q){
- //checks the timestamps first, to build no cycles, and after that the real distance
- return (m_time_map[q] <= m_time_map[p] && m_dist_map[q] > m_dist_map[p]+1);
- }
-
- ////////
- // member vars
- ////////
- Graph& m_g;
- IndexMap m_index_map;
- EdgeCapacityMap m_cap_map;
- ResidualCapacityEdgeMap m_res_cap_map;
- ReverseEdgeMap m_rev_edge_map;
- PredecessorMap m_pre_map; //stores paths found in the growth stage
- ColorMap m_tree_map; //maps each vertex into one of the two search tree or none (gray())
- DistanceMap m_dist_map; //stores distance to source/sink nodes
- vertex_descriptor m_source;
- vertex_descriptor m_sink;
-
- tQueue m_active_nodes;
- std::vector<bool> m_in_active_list_vec;
- iterator_property_map<std::vector<bool>::iterator, IndexMap> m_in_active_list_map;
-
- std::list<vertex_descriptor> m_orphans;
- tQueue m_child_orphans; // we use a second queuqe for child orphans, as they are FIFO processed
-
- std::vector<bool> m_has_parent_vec;
- iterator_property_map<std::vector<bool>::iterator, IndexMap> m_has_parent_map;
-
- std::vector<long> m_time_vec; //timestamp of each node, used for sink/source-path calculations
- iterator_property_map<std::vector<long>::iterator, IndexMap> m_time_map;
- tEdgeVal m_flow;
- long m_time;
- vertex_descriptor m_last_grow_vertex;
- out_edge_iterator m_last_grow_edge_it;
- out_edge_iterator m_last_grow_edge_end;
- };
- } //namespace detail
-
- /**
- * non-named-parameter version, given everything
- * this is the catch all version
- */
- template <class Graph, class CapacityEdgeMap, class ResidualCapacityEdgeMap, class ReverseEdgeMap,
- class PredecessorMap, class ColorMap, class DistanceMap, class IndexMap>
- typename property_traits<CapacityEdgeMap>::value_type
- kolmogorov_max_flow
- (Graph& g,
- CapacityEdgeMap cap,
- ResidualCapacityEdgeMap res_cap,
- ReverseEdgeMap rev_map,
- PredecessorMap pre_map,
- ColorMap color,
- DistanceMap dist,
- IndexMap idx,
- typename graph_traits<Graph>::vertex_descriptor src,
- typename graph_traits<Graph>::vertex_descriptor sink
- )
- {
- typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
- typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor;
- //as this method is the last one before we instantiate the solver, we do the concept checks here
- function_requires<VertexListGraphConcept<Graph> >(); //to have vertices(), num_vertices(),
- function_requires<EdgeListGraphConcept<Graph> >(); //to have edges()
- function_requires<IncidenceGraphConcept<Graph> >(); //to have source(), target() and out_edges()
- function_requires<LvaluePropertyMapConcept<CapacityEdgeMap, edge_descriptor> >(); //read flow-values from edges
- function_requires<Mutable_LvaluePropertyMapConcept<ResidualCapacityEdgeMap, edge_descriptor> >(); //write flow-values to residuals
- function_requires<LvaluePropertyMapConcept<ReverseEdgeMap, edge_descriptor> >(); //read out reverse edges
- function_requires<Mutable_LvaluePropertyMapConcept<PredecessorMap, vertex_descriptor> >(); //store predecessor there
- function_requires<Mutable_LvaluePropertyMapConcept<ColorMap, vertex_descriptor> >(); //write corresponding tree
- function_requires<Mutable_LvaluePropertyMapConcept<DistanceMap, vertex_descriptor> >(); //write distance to source/sink
- function_requires<ReadablePropertyMapConcept<IndexMap, vertex_descriptor> >(); //get index 0...|V|-1
- assert(num_vertices(g) >= 2 && src != sink);
- detail::kolmogorov<Graph, CapacityEdgeMap, ResidualCapacityEdgeMap, ReverseEdgeMap, PredecessorMap, ColorMap, DistanceMap, IndexMap>
- algo(g, cap, res_cap, rev_map, pre_map, color, dist, idx, src, sink);
- return algo.max_flow();
- }
-
- /**
- * non-named-parameter version, given: capacity, residucal_capacity, reverse_edges, and an index map.
- */
- template <class Graph, class CapacityEdgeMap, class ResidualCapacityEdgeMap, class ReverseEdgeMap, class IndexMap>
- typename property_traits<CapacityEdgeMap>::value_type
- kolmogorov_max_flow
- (Graph& g,
- CapacityEdgeMap cap,
- ResidualCapacityEdgeMap res_cap,
- ReverseEdgeMap rev,
- IndexMap idx,
- typename graph_traits<Graph>::vertex_descriptor src,
- typename graph_traits<Graph>::vertex_descriptor sink)
- {
- typename graph_traits<Graph>::vertices_size_type n_verts = num_vertices(g);
- std::vector<typename graph_traits<Graph>::edge_descriptor> predecessor_vec(n_verts);
- std::vector<default_color_type> color_vec(n_verts);
- std::vector<typename graph_traits<Graph>::vertices_size_type> distance_vec(n_verts);
- return kolmogorov_max_flow
- (g, cap, res_cap, rev,
- make_iterator_property_map(predecessor_vec.begin(), idx),
- make_iterator_property_map(color_vec.begin(), idx),
- make_iterator_property_map(distance_vec.begin(), idx),
- idx, src, sink);
- }
-
- /**
- * non-named-parameter version, some given: capacity, residual_capacity, reverse_edges, color_map and an index map.
- * Use this if you are interested in the minimum cut, as the color map provides that info
- */
- template <class Graph, class CapacityEdgeMap, class ResidualCapacityEdgeMap, class ReverseEdgeMap, class ColorMap, class IndexMap>
- typename property_traits<CapacityEdgeMap>::value_type
- kolmogorov_max_flow
- (Graph& g,
- CapacityEdgeMap cap,
- ResidualCapacityEdgeMap res_cap,
- ReverseEdgeMap rev,
- ColorMap color,
- IndexMap idx,
- typename graph_traits<Graph>::vertex_descriptor src,
- typename graph_traits<Graph>::vertex_descriptor sink)
- {
- typename graph_traits<Graph>::vertices_size_type n_verts = num_vertices(g);
- std::vector<typename graph_traits<Graph>::edge_descriptor> predecessor_vec(n_verts);
- std::vector<typename graph_traits<Graph>::vertices_size_type> distance_vec(n_verts);
-
- return kolmogorov_max_flow
- (g, cap, res_cap, rev,
- make_iterator_property_map(predecessor_vec.begin(), idx),
- color,
- make_iterator_property_map(distance_vec.begin(), idx),
- idx, src, sink);
- }
-
- /**
- * named-parameter version, some given
- */
- template <class Graph, class P, class T, class R>
- typename property_traits<typename property_map<Graph, edge_capacity_t>::const_type>::value_type
- kolmogorov_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)
- {
- return kolmogorov_max_flow(g,
- 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),
- choose_pmap(get_param(params, vertex_predecessor), g, vertex_predecessor),
- choose_pmap(get_param(params, vertex_color), g, vertex_color),
- choose_pmap(get_param(params, vertex_distance), g, vertex_distance),
- choose_const_pmap(get_param(params, vertex_index), g, vertex_index),
- src, sink);
- }
-
- /**
- * named-parameter version, none given
- */
- template <class Graph>
- typename property_traits<typename property_map<Graph, edge_capacity_t>::const_type>::value_type
- kolmogorov_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); // bogus empty param
- return kolmogorov_max_flow(g, src, sink, params);
- }
-} // namespace boost
-
-#endif // BOOST_KOLMOGOROV_MAX_FLOW_HPP
-
Deleted: branches/release/libs/graph/doc/kolmogorov_max_flow.html
==============================================================================
--- branches/release/libs/graph/doc/kolmogorov_max_flow.html 2011-03-29 14:56:56 EDT (Tue, 29 Mar 2011)
+++ (empty file)
@@ -1,407 +0,0 @@
-<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
-<HTML>
-<HEAD>
- <META HTTP-EQUIV="CONTENT-TYPE" CONTENT="text/html; charset=iso-8859-15">
- <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">
- <META NAME="CHANGED" CONTENT="20060820;23125100">
-<!--
-// Copyright (c) 2006, Stephan Diederich
-//
-// This documentation 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)
- -->
- <STYLE>
- <!--
- TD P { color: #000000 }
- H1 { color: #000000 }
- P { color: #000000 }
- PRE { color: #000000 }
- H3 { color: #000000 }
- BLOCKQUOTE { color: #000000 }
- A:link { color: #0000ee }
- A:visited { color: #551a8b }
- -->
- </STYLE>
-</HEAD>
-<BODY LANG="de-DE" TEXT="#000000" LINK="#0000ee" VLINK="#551a8b" BGCOLOR="#ffffff" DIR="LTR">
-
-<P>
-<IMG SRC="../../../boost.png" NAME="Grafik1" ALT="C++ Boost" ALIGN=BOTTOM WIDTH=277 HEIGHT=86 BORDER=0>
-</P>
-
-<table align="center" width="75%" style="border:1px solid; border-spacing: 10pt">
-<tr>
- <td style="vertical-align: top"><img src="figs/warning.png"></td>
- <td>
- <b>Warning!</b> This header and its contents are <em>deprecated</em> and
- will be removed in a future release. Please update your program to use
- boykov_kolmogorov_max_flow
- instead. Note that only the name of the algorithm has changed. The template
- and function parameters will remain the same.
- </td>
-</tr>
-</table>
-
-
-<H1><A NAME="sec:kolmogorov_max_flow"></A><TT>kolmogorov_max_flow</TT>
-</H1>
-<PRE><I>// named parameter version</I>
-template <class Graph, class P, class T, class R>
-typename property_traits<typename property_map<Graph, edge_capacity_t>::const_type>::value_type
-kolmogorov_max_flow(Graph& g,
- typename graph_traits<Graph>::vertex_descriptor src,
- typename graph_traits<Graph>::vertex_descriptor sink,
- const bgl_named_params<P, T, R>& params = <I>all defaults</I>)
-
-<I>// non-named parameter version</I>
-template <class Graph, class CapacityEdgeMap, class ResidualCapacityEdgeMap, class ReverseEdgeMap,
- class PredecessorMap, class ColorMap, class DistanceMap, class IndexMap>
-typename property_traits<CapacityEdgeMap>::value_type
-kolmogorov_max_flow(Graph& g,
- CapacityEdgeMap cap,
- ResidualCapacityEdgeMap res_cap,
- ReverseEdgeMap rev_map,
- PredecessorMap pre_map,
- ColorMap color,
- DistanceMap dist,
- IndexMap idx,
- typename graph_traits <Graph>::vertex_descriptor src,
- typename graph_traits <Graph >::vertex_descriptor sink)</PRE><P>
-<FONT SIZE=3>Additional overloaded versions for non-named parameters
-are provided (without DistanceMap/ColorMap/DistanceMap; for those
-iterator_property_maps with the provided index map are used)</FONT></P>
-<P>The <TT>kolmogorov_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>
-<P><B>Requirements:</B><BR>The directed graph <I>G=(V,E)</I> that
-represents the network must include a 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>.
-</P>
-<P>Remarks: While the push-relabel method states that each edge in <I>E<SUP>T</SUP></I>
-has to have capacity of 0, the reverse edges for this algorithm ARE
-allowed to carry capacities. If there are already reverse edges in
-the input Graph <I><FONT FACE="Courier New, monospace">G</FONT></I>,
-those can be used. This can halve the amount of edges and will
-noticeably increase the performance.<BR><BR><B>Algorithm
-description:</B><BR>Kolmogorov's algorithm is a variety of the
-augmenting-path algorithm. Standard augmenting path algorithms find
-shortest paths from source to sink vertex and augment them by
-substracting the bottleneck capacity found on that path from the
-residual capacities of each edge and adding it to the total flow.
-Additionally the minimum capacity is added to the residual capacity
-of the reverse edges. If no more paths in the residual-edge tree are
-found, the algorithm terminates. Instead of finding a new shortest
-path from source to sink in the graph in each iteration, Kolmogorov's
-version keeps the already found paths as follows:</P>
-<P>The algorithm builds up two search trees, a source-tree and a
-sink-tree. Each vertex has a label (stored in <I>ColorMap</I>) to
-which tree it belongs and a status-flag if this vertex is active or
-passive. In the beginning of the algorithm only the source and the
-sink are colored (source==black, sink==white) and have active status.
-All other vertices are colored gray. The algorithm consists of three
-phases:</P>
-<P><I>grow-phase</I>: In this phase active vertices are allowed to
-acquire neighbor vertices that are connected through an edge that has
-a capacity-value greater than zero. Acquiring means that those vertices
-become active and belong now to the search tree of the current
-active vertex. If there are no more valid connections to neighbor
-vertices, the current vertex becomes passive and the grow phase
-continues with the next active vertex. The grow phase terminates if
-there are no more active vertices left or a vertex discovers a vertex
-from the other search tree through an unsaturated edge. In this case
-a path from source to sink is found.</P>
-<P><I>augment-phase</I>: This phase augments the path that was found
-in the grow phase. First it finds the bottleneck capacity of the
-found path, and then it updates the residual-capacity of the edges
-from this path by substracting the bottleneck capacity from the
-residual capacity. Furthermore the residual capacity of the reverse
-edges are updated by adding the bottleneck capacity. This phase can
-destroy the built up search trees, as it creates at least one
-saturated edge. That means, that the search trees collapse to
-forests, because a condition for the search trees is, that each
-vertex in them has a valid (=non-saturated) connection to a terminal.</P>
-<P><I>adoption-phase</I>: Here the search trees are reconstructed. A
-simple solution would be to mark all vertices coming after the first
-orphan in the found path free vertices (gray). A more sophisticated
-solution is to give those orphans new parents: The neighbor vertices
-are checked if they have a valid connection to the same terminal like
-this vertex had (a path with unsaturated edges). If there is one,
-this vertex becomes the new parent of the current orphan and this
-forest is re-included into the search tree. If no new valid parent is
-found, this vertex becomes a free vertex (marked gray), and it's
-children become orphans. The adoption phase terminates if there are
-no more orphans.</P>
-<P><IMG SRC="figs/kolmogorov_max_flow.gif" NAME="Grafik2" ALIGN=LEFT WIDTH=827 HEIGHT=311 BORDER=0><BR CLEAR=LEFT><B>Details:</B></P>
-<UL>
- <LI><P>Marking heuristics: A timestamp is stored for each vertex
- which shows in which iteration of the algorithm the distance to the
- corresponding terminal was calculated.
- </P>
- <UL>
- <LI><P>This distance is used and gets calculated in the
- adoption-phase. In order to find a valid new parent for an orphan,
- the possible parent is checked for a connection to the terminal to
- which tree it belongs. If there is such a connection, the path is
- tagged with the current time-stamp, and the distance value. If
- another orphan has to find a parent and it comes across a vertex
- with a current timestamp, this information is used.</P>
- <LI><P>The distance is also used in the grow-phase. If a vertex
- comes across another vertex of the same tree while searching for
- new vertices, the other's distance is compared to its distance. If
- it is smaller, that other vertex becomes the new parent of the
- current. This can decrease the length of the search paths, and so
- amount of adoptions.</P>
- </UL>
- <LI><P>Ordering of orphans: As described above, the augment-phase
- and the adoption phase can create orphans. The orphans the
- augment-phase generates, are ordered according to their distance to
- the terminals (smallest first). This combined with the
- distance/timestamp heuristics results in the possibility for not
- having to recheck terminal-connections too often. New orphans which
- are generated in adoption phase are processed before orphans from
- the main queue for the same reason.</P>
-</UL>
-<P><BR><B>Implementation notes:</B></P>
-<P>The algorithm is mainly implemented as described in the PhD thesis
-of Kolmogorov. Few changes were made for increasing performance:</P>
-<UL>
- <LI><P>initialization: the algorithm first augments all paths from
- source->sink and all paths from source->VERTEX->sink. This
- improves especially graph-cuts used in image vision where nearly
- each vertex has a source and sink connect. During this step, all
- vertices that have an unsaturated connection from source are added
- to the active vertex list and so the source is not.
- </P>
- <LI><P>active vertices: Kolmogorov uses two lists for active nodes
- and states that new active vertices are added to the rear of the
- second. Fetching an active vertex is done from the beginning of the
- first list. If the first list is empty, it is exchanged by the
- second. This implementation uses just one list.</P>
- <LI><P>grow-phase: In the grow phase the first vertex in the
- active-list is taken and all outgoing edges are checked if they are
- unsaturated. This decreases performance for graphs with high-edge
- density. This implementation stores the last accessed edge and
- continues with it, if the first vertex in the active-list is the
- same one as during the last grow-phase.</P>
-</UL>
-<P>This algorithm [68, 69] was developed by Boykov and Kolmogorov.
-</P>
-<H3>Where Defined</H3>
-<P><TT>boost/graph/kolmogorov_max_flow.hpp</TT>
-</P>
-<H3>Parameters</H3>
-<P>IN: <TT>Graph& g</TT>
-</P>
-<BLOCKQUOTE>A directed graph. The graph's type must be a model of
-Vertex List Graph, <A HREF="EdgeListGraph.html">Edge
-List Graph</A> and Incidence Graph.
-For each edge <I>(u,v)</I> in the graph, the reverse edge <I>(v,u)</I>
-must also be in the graph. Performance of the algorithm will be slightly
-improved if the graph type also models <a href="AdjacencyMatrix.html">Adjacency
-Matrix</a>.
-</BLOCKQUOTE>
-<P>IN: <TT>vertex_descriptor src</TT>
-</P>
-<BLOCKQUOTE>The source vertex for the flow network graph.
-</BLOCKQUOTE>
-<P>IN: <TT>vertex_descriptor sink</TT>
-</P>
-<BLOCKQUOTE>The sink vertex for the flow network graph.
-</BLOCKQUOTE>
-<H3>Named Parameters</H3>
-<P>IN: <TT>edge_capacity(EdgeCapacityMap cap)</TT>
-</P>
-<BLOCKQUOTE>The edge capacity property map. The type must be a model
-of a constant <A HREF="../../property_map/doc/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>
-<P>OUT: <TT>edge_residual_capacity(ResidualCapacityEdgeMap res)</TT>
-</P>
-<BLOCKQUOTE>The edge residual capacity property map. The type must be
-a model of a mutable <A HREF="../../property_map/doc/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>
-<P>IN: <TT>edge_reverse(ReverseEdgeMap rev)</TT>
-</P>
-<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/doc/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>
-<P>UTIL: <TT>vertex_predecessor(PredecessorMap pre_map)</TT>
-</P>
-<BLOCKQUOTE>A vertex property map that stores the edge to the vertex'
-predecessor. The map must be a model of mutable <A HREF="../../property_map/doc/LvaluePropertyMap.html">Lvalue
-Property Map</A>. The key type of the map must be the graph's vertex
-descriptor type.<BR><B>Default:</B> <TT>get(vertex_predecessor, g)</TT>
-</BLOCKQUOTE>
-<P>OUT/UTIL: <TT>vertex_color(ColorMap color)</TT>
-</P>
-<BLOCKQUOTE>A vertex property map that stores a color for edge
-vertex. If the color of a vertex after running the algorithm is black
-the vertex belongs to the source tree else it belongs to the
-sink-tree (used for minimum cuts). The map must be a model of mutable
-<A HREF="../../property_map/doc/LvaluePropertyMap.html">Lvalue Property
-Map</A>. The key type of the map must be the graph's vertex
-descriptor type.<BR><B>Default:</B> <TT>get(vertex_color, g)</TT>
-</BLOCKQUOTE>
-<P>UTIL: <TT>vertex_distance(DistanceMap dist)</TT>
-</P>
-<BLOCKQUOTE>A vertex property map that stores the distance to the
-corresponding terminal. It's a utility-map for speeding up the
-algorithm. The map must be a model of mutable <A HREF="../../property_map/doc/LvaluePropertyMap.html">Lvalue
-Property Map</A>. The key type of the map must be the graph's vertex
-descriptor type.<BR><B>Default:</B> <TT>get(vertex_distance, g)</TT>
-</BLOCKQUOTE>
-<P>IN: <TT>vertex_index(VertexIndexMap index_map)</TT>
-</P>
-<BLOCKQUOTE>Maps each vertex of the graph to a unique integer in the
-range <TT>[0, num_vertices(g))</TT>. The map must be a model of
-constant LvaluePropertyMap.
-The key type of the map must be the graph's vertex descriptor
-type.<BR><B>Default:</B> <TT>get(vertex_index, g)</TT>
-</BLOCKQUOTE>
-<H3>Example</H3>
-<P>This reads an example maximum flow problem (a graph with edge
-capacities) from a file in the DIMACS format (<TT>example/max_flow.dat</TT>).
-The source for this example can be found in
-<TT>example/boykov_kolmogorov-eg.cpp</TT>.
-</P>
-<PRE>#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>
-
-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;
-}</PRE><P>
-The output is:
-</P>
-<PRE>c The total flow:
-s 13
-
-c flow values:
-f 0 6 3
-f 0 1 0
-f 0 2 10
-f 1 5 1
-f 1 0 0
-f 1 3 0
-f 2 4 4
-f 2 3 6
-f 2 0 0
-f 3 7 5
-f 3 2 0
-f 3 1 1
-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</PRE><H3>
-See Also</H3>
-<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>
- <TR VALIGN=TOP>
- <TD>
- <P>Copyright © 2006</P>
- </TD>
- <TD>
- <P>Stephan Diederich, University
- Mannheim(<A HREF="mailto:diederich_at_[hidden]">diederich_at_[hidden]</A>)</P>
- </TD>
- </TR>
-</TABLE>
-<P><BR><BR>
-</P>
-</BODY>
-</HTML>
Modified: branches/release/libs/graph/doc/table_of_contents.html
==============================================================================
--- branches/release/libs/graph/doc/table_of_contents.html (original)
+++ branches/release/libs/graph/doc/table_of_contents.html 2011-03-29 14:56:56 EDT (Tue, 29 Mar 2011)
@@ -201,11 +201,6 @@
<OL>
<LI>edmonds_karp_max_flow
<LI>push_relabel_max_flow
- <li>
- kolmogorov_max_flow (<em>Deprecated</em>.
- Use boykov_kolmogorov_max_flow
- instead.)
- </li>
<li>boykov_kolmogorov_max_flow</li>
<LI>edmonds_maximum_cardinality_matching
</OL>
Modified: branches/release/libs/graph/test/astar_search_test.cpp
==============================================================================
--- branches/release/libs/graph/test/astar_search_test.cpp (original)
+++ branches/release/libs/graph/test/astar_search_test.cpp 2011-03-29 14:56:56 EDT (Tue, 29 Mar 2011)
@@ -15,6 +15,7 @@
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/random.hpp>
#include <boost/random.hpp>
+#include <utility>
#include <vector>
#include <list>
#include <iostream>