|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r74023 - in branches/release: . boost boost/algorithm/string boost/archive boost/bimap boost/config boost/date_time boost/date_time/posix_time boost/detail boost/dynamic_bitset boost/filesystem boost/function boost/functional boost/fusion boost/fusion/container/list/detail boost/geometry boost/geometry/algorithms boost/geometry/arithmetic boost/geometry/core boost/geometry/domains boost/geometry/geometries boost/geometry/iterators boost/geometry/multi boost/geometry/policies boost/geometry/strategies boost/geometry/util boost/geometry/views boost/gil boost/graph boost/graph/distributed boost/graph/distributed/detail boost/icl boost/integer boost/interprocess boost/intrusive boost/io boost/iostreams boost/iterator boost/locale boost/msm boost/msm/back boost/msm/front boost/msm/front/detail boost/msm/front/euml boost/msm/mpl_graph boost/numeric/ublas boost/pending boost/pool boost/program_options boost/program_options/detail boost/property_tree boost/python boost/range boost/serialization boost/signals boost/signals2 boost/spirit boost/spirit/home boost/spirit/home/karma boost/spirit/home/support boost/statechart boost/system boost/thread boost/tr1 boost/typeof boost/unordered boost/utility boost/uuid boost/variant boost/wave boost/xpressive doc libs libs/algorithm/string libs/array libs/array/test libs/bimap libs/config libs/date_time libs/date_time/data libs/date_time/example/gregorian libs/date_time/example/local_time libs/date_time/example/posix_time libs/date_time/example/tutorial libs/date_time/test/posix_time libs/date_time/xmldoc libs/detail libs/filesystem libs/function libs/functional libs/fusion libs/geometry libs/geometry/doc libs/geometry/doc/concept libs/geometry/doc/doxy libs/geometry/doc/generated libs/geometry/doc/html libs/geometry/doc/reference libs/geometry/doc/src libs/geometry/example libs/geometry/test 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/iostreams libs/iterator libs/locale 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/phoenix/doc libs/phoenix/doc/examples libs/pool libs/program_options libs/program_options/test libs/property_tree libs/python libs/range libs/serialization libs/serialization/example libs/serialization/src libs/serialization/test libs/signals libs/signals2 libs/signals2/doc 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/thread libs/timer libs/tr1 libs/typeof/doc libs/unordered libs/utility libs/utility/swap/test libs/uuid libs/wave more status tools tools/bcp tools/boostbook tools/build/v2 tools/build/v2/tools tools/inspect tools/quickbook tools/regression tools/regression/src tools/release tools/wave
From: jewillco_at_[hidden]
Date: 2011-08-23 14:26:49
Author: jewillco
Date: 2011-08-23 14:26:46 EDT (Tue, 23 Aug 2011)
New Revision: 74023
URL: http://svn.boost.org/trac/boost/changeset/74023
Log:
Merged in BGL, enable_if, and related changes from trunk: r67035, r57559, r72837, r73010, r73026, r72960, r73425, r73424, r73009, r73998, r73997, r73006, r73630, r73631, r73999, r73422, r73423, r73996, r71221
Removed:
branches/release/boost/pending/integer_range.hpp
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/array.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/cstdint.hpp (props changed)
branches/release/boost/date_time/c_time.hpp (props changed)
branches/release/boost/date_time/date_formatting.hpp (props changed)
branches/release/boost/date_time/filetime_functions.hpp (props changed)
branches/release/boost/date_time/gregorian_calendar.ipp (props changed)
branches/release/boost/date_time/posix_time/time_serialize.hpp (props changed)
branches/release/boost/date_time/strings_from_facet.hpp (props changed)
branches/release/boost/date_time/time_facet.hpp (props changed)
branches/release/boost/date_time/tz_db_base.hpp (props changed)
branches/release/boost/detail/ (props changed)
branches/release/boost/detail/interlocked.hpp (props changed)
branches/release/boost/dynamic_bitset/dynamic_bitset.hpp (props changed)
branches/release/boost/filesystem/ (props changed)
branches/release/boost/filesystem.hpp (props changed)
branches/release/boost/function/ (props changed)
branches/release/boost/function/function_template.hpp (props changed)
branches/release/boost/functional/ (props changed)
branches/release/boost/fusion/ (props changed)
branches/release/boost/fusion/container/list/detail/build_cons.hpp (props changed)
branches/release/boost/geometry/ (props changed)
branches/release/boost/geometry/algorithms/ (props changed)
branches/release/boost/geometry/arithmetic/ (props changed)
branches/release/boost/geometry/core/ (props changed)
branches/release/boost/geometry/domains/ (props changed)
branches/release/boost/geometry/geometries/ (props changed)
branches/release/boost/geometry/geometry.hpp (props changed)
branches/release/boost/geometry/iterators/ (props changed)
branches/release/boost/geometry/multi/ (props changed)
branches/release/boost/geometry/policies/ (props changed)
branches/release/boost/geometry/strategies/ (props changed)
branches/release/boost/geometry/util/ (props changed)
branches/release/boost/geometry/views/ (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/integer.hpp (props changed)
branches/release/boost/integer_fwd.hpp (props changed)
branches/release/boost/integer_traits.hpp (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/ (props changed)
branches/release/boost/iterator/iterator_facade.hpp (props changed)
branches/release/boost/locale/ (props changed)
branches/release/boost/locale.hpp (props changed)
branches/release/boost/math_fwd.hpp (props changed)
branches/release/boost/msm/ (props changed)
branches/release/boost/msm/active_state_switching_policies.hpp (props changed)
branches/release/boost/msm/back/ (props changed)
branches/release/boost/msm/back/any_event.hpp (props changed)
branches/release/boost/msm/back/args.hpp (props changed)
branches/release/boost/msm/back/bind_helpers.hpp (props changed)
branches/release/boost/msm/back/common_types.hpp (props changed)
branches/release/boost/msm/back/copy_policies.hpp (props changed)
branches/release/boost/msm/back/default_compile_policy.hpp (props changed)
branches/release/boost/msm/back/dispatch_table.hpp (props changed)
branches/release/boost/msm/back/favor_compile_time.hpp (props changed)
branches/release/boost/msm/back/fold_to_list.hpp (props changed)
branches/release/boost/msm/back/history_policies.hpp (props changed)
branches/release/boost/msm/back/metafunctions.hpp (props changed)
branches/release/boost/msm/back/mpl_graph_fsm_check.hpp (props changed)
branches/release/boost/msm/back/no_fsm_check.hpp (props changed)
branches/release/boost/msm/back/queue_container_circular.hpp (props changed)
branches/release/boost/msm/back/queue_container_deque.hpp (props changed)
branches/release/boost/msm/back/state_machine.hpp (props changed)
branches/release/boost/msm/back/tools.hpp (props changed)
branches/release/boost/msm/common.hpp (props changed)
branches/release/boost/msm/front/ (props changed)
branches/release/boost/msm/front/common_states.hpp (props changed)
branches/release/boost/msm/front/completion_event.hpp (props changed)
branches/release/boost/msm/front/detail/ (props changed)
branches/release/boost/msm/front/detail/common_states.hpp (props changed)
branches/release/boost/msm/front/detail/row2_helper.hpp (props changed)
branches/release/boost/msm/front/euml/ (props changed)
branches/release/boost/msm/front/euml/algorithm.hpp (props changed)
branches/release/boost/msm/front/euml/common.hpp (props changed)
branches/release/boost/msm/front/euml/container.hpp (props changed)
branches/release/boost/msm/front/euml/euml.hpp (props changed)
branches/release/boost/msm/front/euml/euml_typeof.hpp (props changed)
branches/release/boost/msm/front/euml/guard_grammar.hpp (props changed)
branches/release/boost/msm/front/euml/iteration.hpp (props changed)
branches/release/boost/msm/front/euml/operator.hpp (props changed)
branches/release/boost/msm/front/euml/phoenix_placeholders.hpp (props changed)
branches/release/boost/msm/front/euml/querying.hpp (props changed)
branches/release/boost/msm/front/euml/state_grammar.hpp (props changed)
branches/release/boost/msm/front/euml/stl.hpp (props changed)
branches/release/boost/msm/front/euml/stt_grammar.hpp (props changed)
branches/release/boost/msm/front/euml/transformation.hpp (props changed)
branches/release/boost/msm/front/functor_row.hpp (props changed)
branches/release/boost/msm/front/internal_row.hpp (props changed)
branches/release/boost/msm/front/row2.hpp (props changed)
branches/release/boost/msm/front/state_machine_def.hpp (props changed)
branches/release/boost/msm/front/states.hpp (props changed)
branches/release/boost/msm/mpl_graph/ (props changed)
branches/release/boost/msm/msm_grammar.hpp (props changed)
branches/release/boost/msm/proto_config.hpp (props changed)
branches/release/boost/msm/row_tags.hpp (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/python/ (props changed)
branches/release/boost/range/ (props changed)
branches/release/boost/regex.h (props changed)
branches/release/boost/regex_fwd.hpp (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/thread/ (props changed)
branches/release/boost/thread.hpp (props changed)
branches/release/boost/token_functions.hpp (props changed)
branches/release/boost/tr1/ (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/unordered/ (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/boost/xpressive/ (props changed)
branches/release/boostcpp.jam (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/test/array0.cpp (props changed)
branches/release/libs/array/test/array2.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/date_time/data/date_time_zonespec.csv (props changed)
branches/release/libs/date_time/example/gregorian/days_between_new_years.cpp (props changed)
branches/release/libs/date_time/example/gregorian/days_since_year_start.cpp (props changed)
branches/release/libs/date_time/example/gregorian/days_till_new_year.cpp (props changed)
branches/release/libs/date_time/example/gregorian/month_add.cpp (props changed)
branches/release/libs/date_time/example/local_time/flight.cpp (props changed)
branches/release/libs/date_time/example/local_time/local_date_time.cpp (props changed)
branches/release/libs/date_time/example/posix_time/print_hours.cpp (props changed)
branches/release/libs/date_time/example/posix_time/time_math.cpp (props changed)
branches/release/libs/date_time/example/tutorial/io_tutorial.cpp (props changed)
branches/release/libs/date_time/test/posix_time/testtime_facet.cpp (props changed)
branches/release/libs/date_time/test/posix_time/testtime_input_facet.cpp (props changed)
branches/release/libs/date_time/xmldoc/date_class.xml (props changed)
branches/release/libs/date_time/xmldoc/usage_examples.xml (props changed)
branches/release/libs/detail/ (props changed)
branches/release/libs/filesystem/ (props changed)
branches/release/libs/function/ (props changed)
branches/release/libs/functional/ (props changed)
branches/release/libs/fusion/ (props changed)
branches/release/libs/geometry/ (props changed)
branches/release/libs/geometry/doc/ (props changed)
branches/release/libs/geometry/doc/Jamfile.v2 (props changed)
branches/release/libs/geometry/doc/about_documentation.qbk (props changed)
branches/release/libs/geometry/doc/acknowledgments.qbk (props changed)
branches/release/libs/geometry/doc/compiling.qbk (props changed)
branches/release/libs/geometry/doc/concept/ (props changed)
branches/release/libs/geometry/doc/copyright_note_policy.txt (props changed)
branches/release/libs/geometry/doc/design_rationale.qbk (props changed)
branches/release/libs/geometry/doc/doxy/ (props changed)
branches/release/libs/geometry/doc/generated/ (props changed)
branches/release/libs/geometry/doc/geometry.qbk (props changed)
branches/release/libs/geometry/doc/html/ (props changed)
branches/release/libs/geometry/doc/imports.qbk (props changed)
branches/release/libs/geometry/doc/introduction.qbk (props changed)
branches/release/libs/geometry/doc/make_qbk.py (props changed)
branches/release/libs/geometry/doc/matrix.qbk (props changed)
branches/release/libs/geometry/doc/quickref.xml (props changed)
branches/release/libs/geometry/doc/quickstart.qbk (props changed)
branches/release/libs/geometry/doc/readme.txt (props changed)
branches/release/libs/geometry/doc/reference/ (props changed)
branches/release/libs/geometry/doc/reference.qbk (props changed)
branches/release/libs/geometry/doc/src/ (props changed)
branches/release/libs/geometry/example/ (props changed)
branches/release/libs/geometry/index.html (props changed)
branches/release/libs/geometry/test/ (props changed)
branches/release/libs/graph/doc/ (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/iostreams/ (props changed)
branches/release/libs/iterator/ (props changed)
branches/release/libs/libraries.htm (props changed)
branches/release/libs/locale/ (props changed)
branches/release/libs/maintainers.txt (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/phoenix/doc/basics.qbk (props changed)
branches/release/libs/phoenix/doc/examples/extending_actors.qbk (props changed)
branches/release/libs/phoenix/doc/organisation.qbk (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/python/ (props changed)
branches/release/libs/range/ (props changed)
branches/release/libs/serialization/ (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/signals/ (props changed)
branches/release/libs/signals2/ (props changed)
branches/release/libs/signals2/doc/ (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/thread/ (props changed)
branches/release/libs/timer/ (props changed)
branches/release/libs/tr1/ (props changed)
branches/release/libs/typeof/doc/typeof.qbk (props changed)
branches/release/libs/unordered/ (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/expected_results.xml (props changed)
branches/release/status/explicit-failures-markup.xml (props changed)
branches/release/status/explicit-failures.xsd (props changed)
branches/release/tools/ (props changed)
branches/release/tools/bcp/ (props changed)
branches/release/tools/boostbook/ (props changed)
branches/release/tools/build/v2/ (props changed)
branches/release/tools/build/v2/tools/mpi.jam (props changed)
branches/release/tools/inspect/ (props changed)
branches/release/tools/quickbook/ (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/astar_search.hpp | 10 +
branches/release/boost/graph/bandwidth.hpp | 22 ++-
branches/release/boost/graph/boykov_kolmogorov_max_flow.hpp | 193 ++++++++++++++++++++-------------------
branches/release/boost/graph/dag_shortest_paths.hpp | 8 +
branches/release/boost/graph/dijkstra_shortest_paths.hpp | 8 +
branches/release/boost/graph/dijkstra_shortest_paths_no_color_map.hpp | 8 +
branches/release/boost/graph/distributed/adjacency_list.hpp | 2
branches/release/boost/graph/distributed/detail/mpi_process_group.ipp | 4
branches/release/boost/graph/distributed/strong_components.hpp | 2
branches/release/boost/graph/floyd_warshall_shortest.hpp | 16 ++-
branches/release/boost/graph/graphml.hpp | 2
branches/release/boost/graph/grid_graph.hpp | 50 +++++++++
branches/release/boost/graph/push_relabel_max_flow.hpp | 10 +-
branches/release/boost/graph/read_dimacs.hpp | 3
branches/release/boost/graph/relax.hpp | 6 +
branches/release/boost/graph/reverse_graph.hpp | 115 ++++++++++++++++++-----
branches/release/boost/pending/property.hpp | 2
branches/release/boost/pending/property_serialize.hpp | 2
branches/release/libs/graph/doc/bandwidth.html | 4
branches/release/libs/graph/doc/constructing_algorithms.html | 6
branches/release/libs/graph/doc/isomorphism.html | 41 +++----
branches/release/libs/graph/test/test_construction.hpp | 2
branches/release/libs/utility/enable_if.html | 111 +++++++++++++++++++---
23 files changed, 412 insertions(+), 215 deletions(-)
Modified: branches/release/boost/graph/astar_search.hpp
==============================================================================
--- branches/release/boost/graph/astar_search.hpp (original)
+++ branches/release/boost/graph/astar_search.hpp 2011-08-23 14:26:46 EDT (Tue, 23 Aug 2011)
@@ -325,6 +325,7 @@
typename detail::map_maker<VertexListGraph, arg_pack_type, tag::distance_map, W>::map_type
distance_map_type;
typedef typename boost::property_traits<distance_map_type>::value_type D;
+ const D inf = arg_pack[_distance_inf | (std::numeric_limits<D>::max)()];
astar_search
(g, s, h,
@@ -336,8 +337,8 @@
detail::override_const_property(arg_pack, _vertex_index_map, g, vertex_index),
detail::make_color_map_from_arg_pack(g, arg_pack),
arg_pack[_distance_compare | std::less<D>()],
- arg_pack[_distance_combine | closed_plus<D>()],
- arg_pack[_distance_inf | (std::numeric_limits<D>::max)()],
+ arg_pack[_distance_combine | closed_plus<D>(inf)],
+ inf,
arg_pack[_distance_zero | D()]);
}
@@ -358,6 +359,7 @@
arg_pack_type, tag::weight_map, edge_weight_t, VertexListGraph>::type
weight_map_type;
typedef typename boost::property_traits<weight_map_type>::value_type D;
+ const D inf = arg_pack[_distance_inf | (std::numeric_limits<D>::max)()];
astar_search_no_init
(g, s, h,
arg_pack[_visitor | make_astar_visitor(null_visitor())],
@@ -368,8 +370,8 @@
detail::override_const_property(arg_pack, _vertex_index_map, g, vertex_index),
detail::make_color_map_from_arg_pack(g, arg_pack),
arg_pack[_distance_compare | std::less<D>()],
- arg_pack[_distance_combine | closed_plus<D>()],
- arg_pack[_distance_inf | (std::numeric_limits<D>::max)()],
+ arg_pack[_distance_combine | closed_plus<D>(inf)],
+ inf,
arg_pack[_distance_zero | D()]);
}
Modified: branches/release/boost/graph/bandwidth.hpp
==============================================================================
--- branches/release/boost/graph/bandwidth.hpp (original)
+++ branches/release/boost/graph/bandwidth.hpp 2011-08-23 14:26:46 EDT (Tue, 23 Aug 2011)
@@ -21,15 +21,14 @@
VertexIndexMap index)
{
BOOST_USING_STD_MAX();
- typedef typename graph_traits<Graph>::vertices_size_type size_type;
- size_type b = 0;
+ using std::abs;
+ typedef typename graph_traits<Graph>::vertices_size_type vertices_size_type;
+ vertices_size_type b = 0;
typename graph_traits<Graph>::out_edge_iterator e, end;
for (boost::tie(e, end) = out_edges(i, g); e != end; ++e) {
int f_i = get(index, i);
int f_j = get(index, target(*e, g));
- using namespace std; // to call abs() unqualified
- if(f_i > f_j)
- b = max BOOST_PREVENT_MACRO_SUBSTITUTION (b, size_type(f_i - f_j));
+ b = max BOOST_PREVENT_MACRO_SUBSTITUTION (b, vertices_size_type(abs(f_i - f_j)));
}
return b;
}
@@ -47,10 +46,15 @@
bandwidth(const Graph& g, VertexIndexMap index)
{
BOOST_USING_STD_MAX();
- typename graph_traits<Graph>::vertices_size_type b = 0;
- typename graph_traits<Graph>::vertex_iterator i, end;
- for (boost::tie(i, end) = vertices(g); i != end; ++i)
- b = max BOOST_PREVENT_MACRO_SUBSTITUTION (b, ith_bandwidth(*i, g, index));
+ using std::abs;
+ typedef typename graph_traits<Graph>::vertices_size_type vertices_size_type;
+ vertices_size_type b = 0;
+ typename graph_traits<Graph>::edge_iterator i, end;
+ for (boost::tie(i, end) = edges(g); i != end; ++i) {
+ int f_i = get(index, source(*i, g));
+ int f_j = get(index, target(*i, g));
+ b = max BOOST_PREVENT_MACRO_SUBSTITUTION (b, vertices_size_type(abs(f_i - f_j)));
+ }
return b;
}
Modified: branches/release/boost/graph/boykov_kolmogorov_max_flow.hpp
==============================================================================
--- branches/release/boost/graph/boykov_kolmogorov_max_flow.hpp (original)
+++ branches/release/boost/graph/boykov_kolmogorov_max_flow.hpp 2011-08-23 14:26:46 EDT (Tue, 23 Aug 2011)
@@ -125,14 +125,14 @@
// 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];
- BOOST_ASSERT(m_rev_edge_map[m_rev_edge_map[*ei]] == *ei); //check if the reverse edge map is build up properly
+ put(m_res_cap_map, *ei, get(m_cap_map, *ei));
+ BOOST_ASSERT(get(m_rev_edge_map, get(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;
+ put(m_time_map, m_source, 1);
+ put(m_time_map, m_sink, 1);
}
tEdgeVal max_flow(){
@@ -168,8 +168,8 @@
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;
+ tEdgeVal cap = get(m_res_cap_map, from_source);
+ put(m_res_cap_map, from_source, 0);
m_flow += cap;
continue;
}
@@ -177,52 +177,52 @@
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];
+ tEdgeVal cap_from_source = get(m_res_cap_map, from_source);
+ tEdgeVal cap_to_sink = get(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;
+ put(m_dist_map, current_node, 1);
+ put(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;
+ put(m_res_cap_map, from_source, get(m_res_cap_map, from_source) - cap_to_sink);
+ put(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;
+ put(m_dist_map, current_node, 1);
+ put(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;
+ put(m_res_cap_map, to_sink, get(m_res_cap_map, to_sink) - cap_from_source);
+ put(m_res_cap_map, from_source, 0);
m_flow += cap_from_source;
}
- } else if(m_res_cap_map[from_source]){
+ } else if(get(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;
+ put(m_dist_map, current_node, 1);
+ put(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];
+ edge_descriptor to_sink = get(m_rev_edge_map, *ei);
vertex_descriptor current_node = source(to_sink, m_g);
- if(m_res_cap_map[to_sink]){
+ if(get(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;
+ put(m_dist_map, current_node, 1);
+ put(m_time_map, current_node, 1);
add_active_node(current_node);
}
}
@@ -252,21 +252,21 @@
}
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
+ if(get(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];
+ put(m_dist_map, other_node, get(m_dist_map, current_node) + 1); //and update the distance-heuristic
+ put(m_time_map, other_node, get(m_time_map, current_node));
add_active_node(other_node);
} else if(get_tree(other_node) == tColorTraits::black()) {
// we do this to get shorter paths. check if we are nearer to
// the source as its parent is
if(is_closer_to_terminal(current_node, other_node)){
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];
+ put(m_dist_map, other_node, get(m_dist_map, current_node) + 1);
+ put(m_time_map, other_node, get(m_time_map, current_node));
}
} else{
BOOST_ASSERT(get_tree(other_node)==tColorTraits::white());
@@ -285,21 +285,21 @@
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
+ edge_descriptor in_edge = get(m_rev_edge_map, *m_last_grow_edge_it);
+ if(get(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
+ put(m_dist_map, other_node, get(m_dist_map, current_node) + 1); //set its distance
+ put(m_time_map, other_node, get(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];
+ put(m_dist_map, other_node, get(m_dist_map, current_node) + 1);
+ put(m_time_map, other_node, get(m_time_map, current_node));
}
} else{
BOOST_ASSERT(get_tree(other_node)==tColorTraits::black());
@@ -340,18 +340,18 @@
//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;
- BOOST_ASSERT(m_res_cap_map[e] >= 0);
- m_res_cap_map[m_rev_edge_map[e]] += bottleneck;
+ put(m_res_cap_map, e, get(m_res_cap_map, e) - bottleneck);
+ BOOST_ASSERT(get(m_res_cap_map, e) >= 0);
+ put(m_res_cap_map, get(m_rev_edge_map, e), get(m_res_cap_map, get(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;
- BOOST_ASSERT(m_res_cap_map[pred] >= 0);
- m_res_cap_map[m_rev_edge_map[pred]] += bottleneck;
- if(m_res_cap_map[pred] == 0){
+ put(m_res_cap_map, pred, get(m_res_cap_map, pred) - bottleneck);
+ BOOST_ASSERT(get(m_res_cap_map, pred) >= 0);
+ put(m_res_cap_map, get(m_rev_edge_map, pred), get(m_res_cap_map, get(m_rev_edge_map, pred)) + bottleneck);
+ if(get(m_res_cap_map, pred) == 0){
set_no_parent(current_node);
m_orphans.push_front(current_node);
}
@@ -361,10 +361,10 @@
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;
- BOOST_ASSERT(m_res_cap_map[pred] >= 0);
- m_res_cap_map[m_rev_edge_map[pred]] += bottleneck;
- if(m_res_cap_map[pred] == 0){
+ put(m_res_cap_map, pred, get(m_res_cap_map, pred) - bottleneck);
+ BOOST_ASSERT(get(m_res_cap_map, pred) >= 0);
+ put(m_res_cap_map, get(m_rev_edge_map, pred), get(m_res_cap_map, get(m_rev_edge_map, pred)) + bottleneck);
+ if(get(m_res_cap_map, pred) == 0){
set_no_parent(current_node);
m_orphans.push_front(current_node);
}
@@ -380,19 +380,19 @@
*/
inline tEdgeVal find_bottleneck(edge_descriptor e){
BOOST_USING_STD_MIN();
- tEdgeVal minimum_cap = m_res_cap_map[e];
+ tEdgeVal minimum_cap = get(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]);
+ minimum_cap = min BOOST_PREVENT_MACRO_SUBSTITUTION(minimum_cap, get(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]);
+ minimum_cap = min BOOST_PREVENT_MACRO_SUBSTITUTION(minimum_cap, get(m_res_cap_map, pred));
current_node = target(pred, m_g);
}
return minimum_cap;
@@ -420,13 +420,13 @@
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];
+ const edge_descriptor in_edge = get(m_rev_edge_map, *ei);
BOOST_ASSERT(target(in_edge, m_g) == current_node); //we should be the target of this edge
- if(m_res_cap_map[in_edge] > 0){
+ if(get(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];
+ if(get(m_dist_map, other_node) < min_distance){
+ min_distance = get(m_dist_map, other_node);
new_parent_edge = in_edge;
}
}
@@ -434,15 +434,15 @@
}
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;
+ put(m_dist_map, current_node, min_distance + 1);
+ put(m_time_map, current_node, m_time);
} else{
- m_time_map[current_node] = 0;
+ put(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];
+ edge_descriptor in_edge = get(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){
+ if(get(m_res_cap_map, in_edge) > 0){
add_active_node(other_node);
}
if(source(get_edge_to_parent(other_node), m_g) == current_node){
@@ -464,26 +464,26 @@
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){
+ if(get(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];
+ if(get(m_dist_map, other_node) < min_distance){
+ min_distance = get(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;
+ put(m_dist_map, current_node, min_distance + 1);
+ put(m_time_map, current_node, m_time);
} else{
- m_time_map[current_node] = 0;
+ put(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){
+ if(get(m_res_cap_map, out_edge) > 0){
add_active_node(other_node);
}
if(target(get_edge_to_parent(other_node), m_g) == current_node){
@@ -511,7 +511,7 @@
//if it has no parent, this node can't be active (if its not source or sink)
if(!has_parent(v) && v != m_source && v != m_sink){
m_active_nodes.pop();
- m_in_active_list_map[v] = false;
+ put(m_in_active_list_map, v, false);
} else{
BOOST_ASSERT(get_tree(v) == tColorTraits::black() || get_tree(v) == tColorTraits::white());
return v;
@@ -524,10 +524,10 @@
*/
inline void add_active_node(vertex_descriptor v){
BOOST_ASSERT(get_tree(v) != tColorTraits::gray());
- if(m_in_active_list_map[v]){
+ if(get(m_in_active_list_map, v)){
return;
} else{
- m_in_active_list_map[v] = true;
+ put(m_in_active_list_map, v, true);
m_active_nodes.push(v);
}
}
@@ -538,7 +538,7 @@
inline void finish_node(vertex_descriptor v){
BOOST_ASSERT(m_active_nodes.front() == v);
m_active_nodes.pop();
- m_in_active_list_map[v] = false;
+ put(m_in_active_list_map, v, false);
m_last_grow_vertex = graph_traits<Graph>::null_vertex();
}
@@ -556,7 +556,7 @@
* white() for sink tree, gray() for no tree
*/
inline tColorValue get_tree(vertex_descriptor v) const {
- return m_tree_map[v];
+ return get(m_tree_map, v);
}
/**
@@ -564,30 +564,30 @@
* for sink tree, gray() for no tree
*/
inline void set_tree(vertex_descriptor v, tColorValue t){
- m_tree_map[v] = t;
+ put(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];
+ return get(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];
+ return get(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){
- BOOST_ASSERT(m_res_cap_map[f_edge_to_parent] > 0);
- m_pre_map[v] = f_edge_to_parent;
- m_has_parent_map[v] = true;
+ BOOST_ASSERT(get(m_res_cap_map, f_edge_to_parent) > 0);
+ put(m_pre_map, v, f_edge_to_parent);
+ put(m_has_parent_map, v, true);
}
/**
@@ -595,7 +595,7 @@
* entry an additional map)
*/
inline void set_no_parent(vertex_descriptor v){
- m_has_parent_map[v] = false;
+ put(m_has_parent_map, v, false);
}
/**
@@ -607,13 +607,13 @@
tDistanceVal current_distance = 0;
vertex_descriptor current_vertex = v;
while(true){
- if(m_time_map[current_vertex] == m_time){
+ if(get(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];
+ current_distance += get(m_dist_map, current_vertex);
break;
}
if(current_vertex == m_sink){
- m_time_map[m_sink] = m_time;
+ put(m_time_map, m_sink, m_time);
break;
}
if(has_parent(current_vertex)){
@@ -626,9 +626,10 @@
}
}
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;
+ while(get(m_time_map, current_vertex) != m_time){
+ put(m_dist_map, current_vertex, current_distance);
+ --current_distance;
+ put(m_time_map, current_vertex, m_time);
current_vertex = target(get_edge_to_parent(current_vertex), m_g);
}
return true;
@@ -643,13 +644,13 @@
tDistanceVal current_distance = 0;
vertex_descriptor current_vertex = v;
while(true){
- if(m_time_map[current_vertex] == m_time){
+ if(get(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];
+ current_distance += get(m_dist_map, current_vertex);
break;
}
if(current_vertex == m_source){
- m_time_map[m_source] = m_time;
+ put(m_time_map, m_source, m_time);
break;
}
if(has_parent(current_vertex)){
@@ -662,9 +663,10 @@
}
}
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;
+ while(get(m_time_map, current_vertex) != m_time){
+ put(m_dist_map, current_vertex, current_distance);
+ --current_distance;
+ put(m_time_map, current_vertex, m_time);
current_vertex = source(get_edge_to_parent(current_vertex), m_g);
}
return true;
@@ -675,7 +677,8 @@
*/
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);
+ return (get(m_time_map, q) <= get(m_time_map, p) &&
+ get(m_dist_map, q) > get(m_dist_map, p)+1);
}
////////
@@ -743,12 +746,12 @@
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<CapacityEdgeMap, edge_descriptor> >(); //read flow-values from edges
+ function_requires<ReadWritePropertyMapConcept<ResidualCapacityEdgeMap, edge_descriptor> >(); //write flow-values to residuals
+ function_requires<ReadablePropertyMapConcept<ReverseEdgeMap, edge_descriptor> >(); //read out reverse edges
+ function_requires<ReadWritePropertyMapConcept<PredecessorMap, vertex_descriptor> >(); //store predecessor there
+ function_requires<ReadWritePropertyMapConcept<ColorMap, vertex_descriptor> >(); //write corresponding tree
+ function_requires<ReadWritePropertyMapConcept<DistanceMap, vertex_descriptor> >(); //write distance to source/sink
function_requires<ReadablePropertyMapConcept<IndexMap, vertex_descriptor> >(); //get index 0...|V|-1
BOOST_ASSERT(num_vertices(g) >= 2 && src != sink);
Modified: branches/release/boost/graph/dag_shortest_paths.hpp
==============================================================================
--- branches/release/boost/graph/dag_shortest_paths.hpp (original)
+++ branches/release/boost/graph/dag_shortest_paths.hpp 2011-08-23 14:26:46 EDT (Tue, 23 Aug 2011)
@@ -88,14 +88,16 @@
{
typedef typename property_traits<DistanceMap>::value_type D;
dummy_property_map p_map;
+ D inf =
+ choose_param(get_param(params, distance_inf_t()),
+ (std::numeric_limits<D>::max)());
dag_shortest_paths
(g, s, distance, weight, color,
choose_param(get_param(params, vertex_predecessor), p_map),
vis,
choose_param(get_param(params, distance_compare_t()), std::less<D>()),
- choose_param(get_param(params, distance_combine_t()), closed_plus<D>()),
- choose_param(get_param(params, distance_inf_t()),
- (std::numeric_limits<D>::max)()),
+ choose_param(get_param(params, distance_combine_t()), closed_plus<D>(inf)),
+ inf,
choose_param(get_param(params, distance_zero_t()),
D()));
}
Modified: branches/release/boost/graph/dijkstra_shortest_paths.hpp
==============================================================================
--- branches/release/boost/graph/dijkstra_shortest_paths.hpp (original)
+++ branches/release/boost/graph/dijkstra_shortest_paths.hpp 2011-08-23 14:26:46 EDT (Tue, 23 Aug 2011)
@@ -420,6 +420,9 @@
dummy_property_map p_map;
typedef typename property_traits<DistanceMap>::value_type D;
+ D inf = choose_param(get_param(params, distance_inf_t()),
+ (std::numeric_limits<D>::max)());
+
dijkstra_shortest_paths
(g, s,
choose_param(get_param(params, vertex_predecessor), p_map),
@@ -427,9 +430,8 @@
choose_param(get_param(params, distance_compare_t()),
std::less<D>()),
choose_param(get_param(params, distance_combine_t()),
- closed_plus<D>()),
- choose_param(get_param(params, distance_inf_t()),
- (std::numeric_limits<D>::max)()),
+ closed_plus<D>(inf)),
+ inf,
choose_param(get_param(params, distance_zero_t()),
D()),
choose_param(get_param(params, graph_visitor),
Modified: branches/release/boost/graph/dijkstra_shortest_paths_no_color_map.hpp
==============================================================================
--- branches/release/boost/graph/dijkstra_shortest_paths_no_color_map.hpp (original)
+++ branches/release/boost/graph/dijkstra_shortest_paths_no_color_map.hpp 2011-08-23 14:26:46 EDT (Tue, 23 Aug 2011)
@@ -186,6 +186,9 @@
dummy_property_map predecessor_map;
typedef typename property_traits<DistanceMap>::value_type DistanceType;
+ DistanceType inf =
+ choose_param(get_param(params, distance_inf_t()),
+ (std::numeric_limits<DistanceType>::max)());
dijkstra_shortest_paths_no_color_map
(graph, start_vertex,
choose_param(get_param(params, vertex_predecessor), predecessor_map),
@@ -193,9 +196,8 @@
choose_param(get_param(params, distance_compare_t()),
std::less<DistanceType>()),
choose_param(get_param(params, distance_combine_t()),
- closed_plus<DistanceType>()),
- choose_param(get_param(params, distance_inf_t()),
- (std::numeric_limits<DistanceType>::max)()),
+ closed_plus<DistanceType>(inf)),
+ inf,
choose_param(get_param(params, distance_zero_t()),
DistanceType()),
choose_param(get_param(params, graph_visitor),
Modified: branches/release/boost/graph/distributed/adjacency_list.hpp
==============================================================================
--- branches/release/boost/graph/distributed/adjacency_list.hpp (original)
+++ branches/release/boost/graph/distributed/adjacency_list.hpp 2011-08-23 14:26:46 EDT (Tue, 23 Aug 2011)
@@ -2931,7 +2931,7 @@
return std::make_pair(edge_descriptor(), false);
} else {
BOOST_ASSERT(false);
- exit(1);
+ abort();
}
}
Modified: branches/release/boost/graph/distributed/detail/mpi_process_group.ipp
==============================================================================
--- branches/release/boost/graph/distributed/detail/mpi_process_group.ipp (original)
+++ branches/release/boost/graph/distributed/detail/mpi_process_group.ipp 2011-08-23 14:26:46 EDT (Tue, 23 Aug 2011)
@@ -725,7 +725,7 @@
process_id(pg), source, tag, pg.my_block_number());
BOOST_ASSERT(false);
- exit(1);
+ abort();
}
}
@@ -746,7 +746,7 @@
process_id(pg), source, tag, pg.my_block_number());
BOOST_ASSERT(false);
- exit(1);
+ abort();
}
}
Modified: branches/release/boost/graph/distributed/strong_components.hpp
==============================================================================
--- branches/release/boost/graph/distributed/strong_components.hpp (original)
+++ branches/release/boost/graph/distributed/strong_components.hpp 2011-08-23 14:26:46 EDT (Tue, 23 Aug 2011)
@@ -693,7 +693,7 @@
if (estart != eend) {
boost::tie(restart, reend) = out_edges(get(fr, v), gr);
while (restart != reend && find(vertex_sets[i].begin(), vertex_sets[i].end(),
- get(rf, target(*restart,g))) == vertex_sets[i].end()) restart++;
+ get(rf, target(*restart,gr))) == vertex_sets[i].end()) restart++;
if (restart != reend)
new_set.push_back(v);
}
Modified: branches/release/boost/graph/floyd_warshall_shortest.hpp
==============================================================================
--- branches/release/boost/graph/floyd_warshall_shortest.hpp (original)
+++ branches/release/boost/graph/floyd_warshall_shortest.hpp 2011-08-23 14:26:46 EDT (Tue, 23 Aug 2011)
@@ -163,14 +163,16 @@
const bgl_named_params<P, T, R>& params)
{
typedef typename property_traits<WeightMap>::value_type WM;
+ WM inf =
+ choose_param(get_param(params, distance_inf_t()),
+ std::numeric_limits<WM>::max BOOST_PREVENT_MACRO_SUBSTITUTION());
return floyd_warshall_initialized_all_pairs_shortest_paths(g, d,
choose_param(get_param(params, distance_compare_t()),
std::less<WM>()),
choose_param(get_param(params, distance_combine_t()),
- closed_plus<WM>()),
- choose_param(get_param(params, distance_inf_t()),
- std::numeric_limits<WM>::max BOOST_PREVENT_MACRO_SUBSTITUTION()),
+ closed_plus<WM>(inf)),
+ inf,
choose_param(get_param(params, distance_zero_t()),
WM()));
}
@@ -185,13 +187,15 @@
{
typedef typename property_traits<WeightMap>::value_type WM;
+ WM inf =
+ choose_param(get_param(params, distance_inf_t()),
+ std::numeric_limits<WM>::max BOOST_PREVENT_MACRO_SUBSTITUTION());
return floyd_warshall_all_pairs_shortest_paths(g, d, w,
choose_param(get_param(params, distance_compare_t()),
std::less<WM>()),
choose_param(get_param(params, distance_combine_t()),
- closed_plus<WM>()),
- choose_param(get_param(params, distance_inf_t()),
- std::numeric_limits<WM>::max BOOST_PREVENT_MACRO_SUBSTITUTION()),
+ closed_plus<WM>(inf)),
+ inf,
choose_param(get_param(params, distance_zero_t()),
WM()));
}
Modified: branches/release/boost/graph/graphml.hpp
==============================================================================
--- branches/release/boost/graph/graphml.hpp (original)
+++ branches/release/boost/graph/graphml.hpp 2011-08-23 14:26:46 EDT (Tue, 23 Aug 2011)
@@ -263,7 +263,7 @@
{
std::string key_id = "key" + lexical_cast<std::string>(key_count++);
if (i->second->key() == typeid(Graph))
- vertex_key_ids[i->first] = key_id;
+ graph_key_ids[i->first] = key_id;
else if (i->second->key() == typeid(vertex_descriptor))
vertex_key_ids[i->first] = key_id;
else if (i->second->key() == typeid(edge_descriptor))
Modified: branches/release/boost/graph/grid_graph.hpp
==============================================================================
--- branches/release/boost/graph/grid_graph.hpp (original)
+++ branches/release/boost/graph/grid_graph.hpp 2011-08-23 14:26:46 EDT (Tue, 23 Aug 2011)
@@ -89,6 +89,32 @@
typedef type const_type;
};
+ //==========================
+ // Reverse Edge Property Map
+ //==========================
+
+ template <typename Descriptor>
+ struct grid_graph_reverse_edge_map {
+ public:
+ typedef Descriptor value_type;
+ typedef Descriptor reference_type;
+ typedef reference_type reference;
+ typedef Descriptor key_type;
+ typedef readable_property_map_tag category;
+
+ grid_graph_reverse_edge_map() { }
+
+ value_type operator[](const key_type& key) const {
+ return (value_type(key.second, key.first));
+ }
+ };
+
+ template<BOOST_GRID_GRAPH_TEMPLATE_PARAMS>
+ struct property_map<BOOST_GRID_GRAPH_TYPE, edge_reverse_t> {
+ typedef grid_graph_reverse_edge_map<BOOST_GRID_GRAPH_TRAITS_T::edge_descriptor> type;
+ typedef type const_type;
+ };
+
//=================
// Function Objects
//=================
@@ -351,7 +377,7 @@
// Stop at the end of this dimension if necessary.
new_position =
(std::min)(new_position,
- length(dimension_index) - 1);
+ vertices_size_type(length(dimension_index) - 1));
}
vertex[dimension_index] = new_position;
@@ -671,7 +697,8 @@
void precalculate() {
m_num_vertices =
std::accumulate(m_dimension_lengths.begin(),
- m_dimension_lengths.end(), 1,
+ m_dimension_lengths.end(),
+ vertices_size_type(1),
std::multiplies<vertices_size_type>());
// Calculate number of edges in each dimension
@@ -971,6 +998,14 @@
BOOST_GRID_GRAPH_TYPE_MEM edges_size_type>(graph));
}
+ template <BOOST_GRID_GRAPH_TEMPLATE_PARAMS>
+ friend inline grid_graph_reverse_edge_map<
+ BOOST_GRID_GRAPH_TYPE_MEM edge_descriptor>
+ get(edge_reverse_t, const BOOST_GRID_GRAPH_TYPE& graph) {
+ return (grid_graph_reverse_edge_map<
+ BOOST_GRID_GRAPH_TYPE_MEM edge_descriptor>());
+ }
+
template<typename Graph,
typename Descriptor,
typename Index>
@@ -986,6 +1021,17 @@
typename Index>
friend struct grid_graph_index_map;
+ template<typename Descriptor>
+ friend inline Descriptor
+ get(const grid_graph_reverse_edge_map<Descriptor>& rev_map,
+ const typename grid_graph_reverse_edge_map<Descriptor>::key_type& key)
+ {
+ return (rev_map[key]);
+ }
+
+ template<typename Descriptor>
+ friend struct grid_graph_reverse_edge_map;
+
}; // grid_graph
} // namespace boost
Modified: branches/release/boost/graph/push_relabel_max_flow.hpp
==============================================================================
--- branches/release/boost/graph/push_relabel_max_flow.hpp (original)
+++ branches/release/boost/graph/push_relabel_max_flow.hpp 2011-08-23 14:26:46 EDT (Tue, 23 Aug 2011)
@@ -450,7 +450,7 @@
for (boost::tie(u_iter, u_end) = vertices(g); u_iter != u_end; ++u_iter) {
u = *u_iter;
put(color, u, ColorTraits::white());
- parent[u] = u;
+ parent[get(index, u)] = u;
current[u] = out_edges(u, g);
}
// eliminate flow cycles and topologically order the vertices
@@ -468,7 +468,7 @@
vertex_descriptor v = target(a, g);
if (get(color, v) == ColorTraits::white()) {
put(color, v, ColorTraits::gray());
- parent[v] = u;
+ parent[get(index, v)] = u;
u = v;
break;
} else if (get(color, v) == ColorTraits::gray()) {
@@ -523,12 +523,12 @@
bos_null = false;
tos = u;
} else {
- topo_next[u] = tos;
+ topo_next[get(index, u)] = tos;
tos = u;
}
}
if (u != r) {
- u = parent[u];
+ u = parent[get(index, u)];
++current[u].first;
} else
break;
@@ -540,7 +540,7 @@
// return excess flows
// note that the sink is not on the stack
if (! bos_null) {
- for (u = tos; u != bos; u = topo_next[u]) {
+ for (u = tos; u != bos; u = topo_next[get(index, u)]) {
boost::tie(ai, a_end) = out_edges(u, g);
while (get(excess_flow, u) > 0 && ai != a_end) {
if (get(capacity, *ai) == 0 && is_residual_edge(*ai))
Modified: branches/release/boost/graph/read_dimacs.hpp
==============================================================================
--- branches/release/boost/graph/read_dimacs.hpp (original)
+++ branches/release/boost/graph/read_dimacs.hpp 2011-08-23 14:26:46 EDT (Tue, 23 Aug 2011)
@@ -281,8 +281,7 @@
std::printf ( "\nline %ld of input - %s\n",
no_lines, err_message[err_no] );
- std::exit (1);
- return (0); /* to avoid warning */
+ return -1;
}
/* -------------------- end of parser -------------------*/
Modified: branches/release/boost/graph/relax.hpp
==============================================================================
--- branches/release/boost/graph/relax.hpp (original)
+++ branches/release/boost/graph/relax.hpp 2011-08-23 14:26:46 EDT (Tue, 23 Aug 2011)
@@ -22,9 +22,13 @@
template <class T>
struct closed_plus
{
+ const T inf;
+
+ closed_plus() : inf(std::numeric_limits<T>::max()) { }
+ closed_plus(T inf) : inf(inf) { }
+
T operator()(const T& a, const T& b) const {
using namespace std;
- const T inf = (std::numeric_limits<T>::max)();
if (a == inf) return inf;
if (b == inf) return inf;
return a + b;
Modified: branches/release/boost/graph/reverse_graph.hpp
==============================================================================
--- branches/release/boost/graph/reverse_graph.hpp (original)
+++ branches/release/boost/graph/reverse_graph.hpp 2011-08-23 14:26:46 EDT (Tue, 23 Aug 2011)
@@ -8,6 +8,7 @@
#include <boost/graph/adjacency_iterator.hpp>
#include <boost/graph/properties.hpp>
+#include <boost/iterator/transform_iterator.hpp>
#include <boost/tuple/tuple.hpp>
#include <boost/type_traits.hpp>
#include <boost/mpl/if.hpp>
@@ -23,10 +24,44 @@
namespace detail {
+ template <typename EdgeDesc>
+ class reverse_graph_edge_descriptor {
+ public:
+ EdgeDesc underlying_desc;
+
+ public:
+ explicit reverse_graph_edge_descriptor(const EdgeDesc& underlying_desc = EdgeDesc())
+ : underlying_desc(underlying_desc) {}
+
+ friend bool operator==(const reverse_graph_edge_descriptor& a, const reverse_graph_edge_descriptor& b) {
+ return a.underlying_desc == b.underlying_desc;
+ }
+ friend bool operator!=(const reverse_graph_edge_descriptor& a, const reverse_graph_edge_descriptor& b) {
+ return a.underlying_desc != b.underlying_desc;
+ }
+ };
+
+ template <typename EdgeDesc>
+ struct reverse_graph_edge_descriptor_maker {
+ typedef reverse_graph_edge_descriptor<EdgeDesc> result_type;
+
+ reverse_graph_edge_descriptor<EdgeDesc> operator()(const EdgeDesc& ed) const {
+ return reverse_graph_edge_descriptor<EdgeDesc>(ed);
+ }
+ };
+
+ template <typename EdgeDesc, typename Iter>
+ std::pair<transform_iterator<reverse_graph_edge_descriptor_maker<EdgeDesc>, Iter>,
+ transform_iterator<reverse_graph_edge_descriptor_maker<EdgeDesc>, Iter> >
+ reverse_edge_iter_pair(const std::pair<Iter, Iter>& ip) {
+ return std::make_pair(make_transform_iterator(ip.first, reverse_graph_edge_descriptor_maker<EdgeDesc>()),
+ make_transform_iterator(ip.second, reverse_graph_edge_descriptor_maker<EdgeDesc>()));
+ }
+
template <bool isEdgeList> struct choose_rev_edge_iter { };
template <> struct choose_rev_edge_iter<true> {
template <class G> struct bind_ {
- typedef typename graph_traits<G>::edge_iterator type;
+ typedef transform_iterator<reverse_graph_edge_descriptor_maker<typename graph_traits<G>::edge_descriptor>, typename graph_traits<G>::edge_iterator> type;
};
};
template <> struct choose_rev_edge_iter<false> {
@@ -49,17 +84,17 @@
// Graph requirements
typedef typename Traits::vertex_descriptor vertex_descriptor;
- typedef typename Traits::edge_descriptor edge_descriptor;
+ typedef detail::reverse_graph_edge_descriptor<typename Traits::edge_descriptor> edge_descriptor;
typedef typename Traits::directed_category directed_category;
typedef typename Traits::edge_parallel_category edge_parallel_category;
typedef typename Traits::traversal_category traversal_category;
// IncidenceGraph requirements
- typedef typename Traits::in_edge_iterator out_edge_iterator;
+ typedef transform_iterator<detail::reverse_graph_edge_descriptor_maker<typename Traits::edge_descriptor>, typename Traits::in_edge_iterator> out_edge_iterator;
typedef typename Traits::degree_size_type degree_size_type;
// BidirectionalGraph requirements
- typedef typename Traits::out_edge_iterator in_edge_iterator;
+ typedef transform_iterator<detail::reverse_graph_edge_descriptor_maker<typename Traits::edge_descriptor>, typename Traits::out_edge_iterator> in_edge_iterator;
// AdjacencyGraph requirements
typedef typename adjacency_iterator_generator<Self,
@@ -158,16 +193,16 @@
typename reverse_graph<BidirectionalGraph>::edge_iterator>
edges(const reverse_graph<BidirectionalGraph,GRef>& g)
{
- return edges(g.m_g);
+ return detail::reverse_edge_iter_pair<typename graph_traits<BidirectionalGraph>::edge_descriptor>(edges(g.m_g));
}
template <class BidirectionalGraph, class GRef>
-inline std::pair<typename graph_traits<BidirectionalGraph>::in_edge_iterator,
- typename graph_traits<BidirectionalGraph>::in_edge_iterator>
+inline std::pair<typename reverse_graph<BidirectionalGraph>::out_edge_iterator,
+ typename reverse_graph<BidirectionalGraph>::out_edge_iterator>
out_edges(const typename graph_traits<BidirectionalGraph>::vertex_descriptor u,
const reverse_graph<BidirectionalGraph,GRef>& g)
{
- return in_edges(u, g.m_g);
+ return detail::reverse_edge_iter_pair<typename graph_traits<BidirectionalGraph>::edge_descriptor>(in_edges(u, g.m_g));
}
template <class BidirectionalGraph, class GRef>
@@ -211,12 +246,12 @@
}
template <class BidirectionalGraph, class GRef>
-inline std::pair<typename graph_traits<BidirectionalGraph>::out_edge_iterator,
- typename graph_traits<BidirectionalGraph>::out_edge_iterator>
+inline std::pair<typename reverse_graph<BidirectionalGraph>::in_edge_iterator,
+ typename reverse_graph<BidirectionalGraph>::in_edge_iterator>
in_edges(const typename graph_traits<BidirectionalGraph>::vertex_descriptor u,
const reverse_graph<BidirectionalGraph,GRef>& g)
{
- return out_edges(u, g.m_g);
+ return detail::reverse_edge_iter_pair<typename graph_traits<BidirectionalGraph>::edge_descriptor>(out_edges(u, g.m_g));
}
template <class BidirectionalGraph, class GRef>
@@ -243,21 +278,52 @@
template <class Edge, class BidirectionalGraph, class GRef>
inline typename graph_traits<BidirectionalGraph>::vertex_descriptor
-source(const Edge& e, const reverse_graph<BidirectionalGraph,GRef>& g)
+source(const detail::reverse_graph_edge_descriptor<Edge>& e, const reverse_graph<BidirectionalGraph,GRef>& g)
{
- return target(e, g.m_g);
+ return target(e.underlying_desc, g.m_g);
}
template <class Edge, class BidirectionalGraph, class GRef>
inline typename graph_traits<BidirectionalGraph>::vertex_descriptor
-target(const Edge& e, const reverse_graph<BidirectionalGraph,GRef>& g)
+target(const detail::reverse_graph_edge_descriptor<Edge>& e, const reverse_graph<BidirectionalGraph,GRef>& g)
{
- return source(e, g.m_g);
+ return source(e.underlying_desc, g.m_g);
}
namespace detail {
+ template <typename PM>
+ struct reverse_graph_edge_property_map {
+ private:
+ PM underlying_pm;
+
+ public:
+ typedef reverse_graph_edge_descriptor<typename property_traits<PM>::key_type> key_type;
+ typedef typename property_traits<PM>::value_type value_type;
+ typedef typename property_traits<PM>::reference reference;
+ typedef typename property_traits<PM>::category category;
+
+ explicit reverse_graph_edge_property_map(const PM& pm): underlying_pm(pm) {}
+
+ friend reference
+ get(const reverse_graph_edge_property_map& m,
+ const key_type& e) {
+ return get(m.underlying_pm, e.underlying_desc);
+ }
+
+ friend void
+ put(const reverse_graph_edge_property_map& m,
+ const key_type& e,
+ const value_type& v) {
+ put(m.underlying_pm, e.underlying_desc, v);
+ }
+
+ reference operator[](const key_type& k) {
+ return (this->underlying_pm)[k.underlying_desc];
+ }
+ };
+
struct reverse_graph_vertex_property_selector {
template <class ReverseGraph, class Property, class Tag>
struct bind_ {
@@ -273,8 +339,8 @@
struct bind_ {
typedef typename ReverseGraph::base_type Graph;
typedef property_map<Graph, Tag> PMap;
- typedef typename PMap::type type;
- typedef typename PMap::const_type const_type;
+ typedef reverse_graph_edge_property_map<typename PMap::type> type;
+ typedef reverse_graph_edge_property_map<typename PMap::const_type> const_type;
};
};
@@ -294,7 +360,7 @@
typename property_map<reverse_graph<BidirGraph,GRef>, Property>::type
get(Property p, reverse_graph<BidirGraph,GRef>& g)
{
- return get(p, g.m_g);
+ return typename property_map<reverse_graph<BidirGraph,GRef>, Property>::type(get(p, g.m_g));
}
template <class BidirGraph, class GRef, class Property>
@@ -302,7 +368,7 @@
get(Property p, const reverse_graph<BidirGraph,GRef>& g)
{
const BidirGraph& gref = g.m_g; // in case GRef is non-const
- return get(p, gref);
+ return typename property_map<reverse_graph<BidirGraph,GRef>, Property>::const_type(get(p, gref));
}
template <class BidirectionalGraph, class GRef, class Property, class Key>
@@ -311,15 +377,15 @@
>::value_type
get(Property p, const reverse_graph<BidirectionalGraph,GRef>& g, const Key& k)
{
- return get(p, g.m_g, k);
+ return get(get(p, g), k);
}
template <class BidirectionalGraph, class GRef, class Property, class Key, class Value>
void
-put(Property p, const reverse_graph<BidirectionalGraph,GRef>& g, const Key& k,
+put(Property p, reverse_graph<BidirectionalGraph,GRef>& g, const Key& k,
const Value& val)
{
- put(p, g.m_g, k, val);
+ put(get(p, g), k, val);
}
template<typename BidirectionalGraph, typename GRef, typename Tag,
@@ -344,9 +410,4 @@
} // namespace boost
-#if BOOST_WORKAROUND(BOOST_MSVC, < 1300)
-// Stay out of the way of the concept checking class
-# undef BidirectionalGraph
-#endif
-
#endif
Deleted: branches/release/boost/pending/integer_range.hpp
==============================================================================
--- branches/release/boost/pending/integer_range.hpp 2011-08-23 14:26:46 EDT (Tue, 23 Aug 2011)
+++ (empty file)
@@ -1,59 +0,0 @@
-// (C) Copyright David Abrahams and Jeremy Siek 2000-2001.
-// 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)
-//
-// Revision History:
-// 04 Jan 2001 Factored counting_iterator stuff into
-// boost/counting_iterator.hpp (David Abrahams)
-
-#ifndef BOOST_INTEGER_RANGE_HPP_
-#define BOOST_INTEGER_RANGE_HPP_
-
-#include <boost/config.hpp>
-#include <boost/iterator/counting_iterator.hpp>
-#include <algorithm>
-
-namespace boost {
-
-//=============================================================================
-// Counting Iterator and Integer Range Class
-
-template <class IntegerType>
-struct integer_range {
- typedef counting_iterator<IntegerType> iterator;
-
- typedef iterator const_iterator;
- typedef IntegerType value_type;
- typedef std::ptrdiff_t difference_type;
- typedef IntegerType reference;
- typedef IntegerType const_reference;
- typedef const IntegerType* pointer;
- typedef const IntegerType* const_pointer;
- typedef IntegerType size_type;
-
- integer_range(IntegerType start, IntegerType finish)
- : m_start(start), m_finish(finish) { }
-
- iterator begin() const { return iterator(m_start); }
- iterator end() const { return iterator(m_finish); }
- size_type size() const { return m_finish - m_start; }
- bool empty() const { return m_finish == m_start; }
- void swap(integer_range& x) {
- std::swap(m_start, x.m_start);
- std::swap(m_finish, x.m_finish);
- }
-protected:
- IntegerType m_start, m_finish;
-};
-
-template <class IntegerType>
-inline integer_range<IntegerType>
-make_integer_range(IntegerType first, IntegerType last)
-{
- return integer_range<IntegerType>(first, last);
-}
-
-} // namespace boost
-
-#endif // BOOST_INTEGER_RANGE_HPP_
Modified: branches/release/boost/pending/property.hpp
==============================================================================
--- branches/release/boost/pending/property.hpp (original)
+++ branches/release/boost/pending/property.hpp 2011-08-23 14:26:46 EDT (Tue, 23 Aug 2011)
@@ -71,7 +71,7 @@
template <class Tag2>
inline detail::error_property_not_found
- get_property_value(const no_property& p, Tag2) {
+ get_property_value(const no_property&, Tag2) {
return detail::error_property_not_found();
}
Modified: branches/release/boost/pending/property_serialize.hpp
==============================================================================
--- branches/release/boost/pending/property_serialize.hpp (original)
+++ branches/release/boost/pending/property_serialize.hpp 2011-08-23 14:26:46 EDT (Tue, 23 Aug 2011)
@@ -22,7 +22,7 @@
template<class Archive, class Tag, class T, class Base>
void
serialize(Archive& ar, property<Tag, T, Base>& prop,
- const unsigned int version)
+ const unsigned int /*version*/)
{
ar & serialization::make_nvp( "property_base" , boost::serialization::base_object<Base>(prop) );
ar & serialization::make_nvp( "property_value" , prop.m_value );
Modified: branches/release/libs/graph/doc/bandwidth.html
==============================================================================
--- branches/release/libs/graph/doc/bandwidth.html (original)
+++ branches/release/libs/graph/doc/bandwidth.html 2011-08-23 14:26:46 EDT (Tue, 23 Aug 2011)
@@ -31,10 +31,10 @@
bandwidth(const Graph& g, VertexIndexMap index_map)
</pre>
-The <b><i>bandwidth</i></b> of an undirected graph is the maximum
+The <b><i>bandwidth</i></b> of a graph is the maximum
distance between two adjacent vertices, with distance measured on a
line upon which the vertices have been placed at unit intervals. To
-put it another way, if the vertices of an undirected graph
+put it another way, if the vertices of a graph
<i>G=(V,E)</i> are each assigned an index from zero to <i>|V| - 1</i>
given by <i>index[v]</i>, then the bandwidth of <i>G</i> is<br>
<br>
Modified: branches/release/libs/graph/doc/constructing_algorithms.html
==============================================================================
--- branches/release/libs/graph/doc/constructing_algorithms.html (original)
+++ branches/release/libs/graph/doc/constructing_algorithms.html 2011-08-23 14:26:46 EDT (Tue, 23 Aug 2011)
@@ -106,7 +106,7 @@
graph algorithm as a template function, the concept checks, and some
typedefs. The implementation is straightforward, the only step not
discussed above is the color initialization step, where we set the
-color of all the vertices to ``uncolored''.
+color of all the vertices to "uncolored."
<P>
<PRE>
@@ -125,8 +125,8 @@
function_requires< VertexListGraphConcept<VertexListGraph> >();
function_requires< ReadWritePropertyMapConcept<Color, vertex_descriptor> >();
function_requires< IntegerConcept<ColorType> >();
- function_requires< size_type, ReadablePropertyMapConcept<Order> >();
- typedef typename same_type<OrderType, vertex_descriptor>::type req_same;
+ function_requires< ReadablePropertyMapConcept<Order, size_type> >();
+ BOOST_STATIC_ASSERT((is_same<OrderType, vertex_descriptor>::value));
size_type max_color = 0;
const size_type V = num_vertices(G);
Modified: branches/release/libs/graph/doc/isomorphism.html
==============================================================================
--- branches/release/libs/graph/doc/isomorphism.html (original)
+++ branches/release/libs/graph/doc/isomorphism.html 2011-08-23 14:26:46 EDT (Tue, 23 Aug 2011)
@@ -59,7 +59,7 @@
algorithm in [<a
href="./bibliography.html#fortin96:_graph_iso_prob">46</a>,<a
href="./bibliography.html#reingold77:_combin_algo">48</a>]. The file
-isomorphism-impl.pdf contains a
+isomorphism-impl.pdf contains a (somewhat out-of-date)
"literate" description of the implementation. The algorithm
used is simple but slow. A more efficient (and much more complex)
algorithm is described in [<a
@@ -101,31 +101,24 @@
<b>Python</b>: Must be a <tt>vertex_vertex_map</tt> for the first graph.
</blockquote>
-IN: <tt>vertex_invariant1(VertexInvariant1 i)</tt>
+IN: <tt>vertex_invariant1(VertexInvariant1 i1)</tt>
+IN: <tt>vertex_invariant2(VertexInvariant2 i2)</tt>
<blockquote>
-A mapping <i>i</i> from vertices to integers such that if there is
-some isomorphism that maps <i>v</i> onto <i>v'</i> then <i>i(v) ==
-i(v')</i>. The <tt>VertexInvariant</tt> type must be a <a
-href="http://www.sgi.com/tech/stl/BinaryFunction.html">BinaryFunction</a>
-where the first argument is a vertex descriptor, the second argument is a
-graph, and the result type is an integer. The vertex invariant must
-work with the types for graph 1.
+Mappings from vertices to integers which restrict which vertices may be
+considered isomorphic. If a candidate isomorphism maps <i>v1</i> to <i>v2</i>
+but <i>i1</i>(<i>v1</i>) != <i>i2</i>(<i>v2</i>), that candidate is rejected.
+This mapping can be used either to speed up the search (as is done by the
+default value, which requires that the degrees of <i>v1</i> and <i>v2</i> are
+equal) or to impose extra conditions on the result. The
+<tt>VertexInvariant1</tt> and <tt>VertexInvariant2</tt> types must model <a
+href="http://www.sgi.com/tech/stl/UnaryFunction.html">UnaryFunction</a>, with
+the argument type of <tt>vertex_invariant1</tt> being <tt>Graph1</tt>'s vertex
+descriptor type, the argument type of <tt>vertex_invariant2</tt> being
+<tt>Graph2</tt>'s vertex descriptor type, and both functions having integral
+result types. The values returned by these two functions must be in the range
+[0, <tt>vertex_max_invariant</tt>).
<br>
-<b>Default:</b> <tt>degree_vertex_invariant</tt><br>
-<b>Python</b>: Unsupported parameter.
-</blockquote>
-
-IN: <tt>vertex_invariant2(VertexInvariant2 i)</tt>
-<blockquote>
-A mapping <i>i</i> from vertices to integers such that if there is
-some isomorphism that maps <i>v</i> onto <i>v'</i> then <i>i(v) ==
-i(v')</i>. The <tt>VertexInvariant</tt> type must be a <a
-href="http://www.sgi.com/tech/stl/BinaryFunction.html">BinaryFunction</a>
-where the first argument is a vertex descriptor, the second argument is a
-graph, and the result type is an integer. The vertex invariant must
-work with the types for both graph 2.
-<br>
-<b>Default:</b> <tt>degree_vertex_invariant</tt><br>
+<b>Default:</b> <tt>degree_vertex_invariant</tt> for both arguments<br>
<b>Python</b>: Unsupported parameter.
</blockquote>
Modified: branches/release/libs/graph/test/test_construction.hpp
==============================================================================
--- branches/release/libs/graph/test/test_construction.hpp (original)
+++ branches/release/libs/graph/test/test_construction.hpp 2011-08-23 14:26:46 EDT (Tue, 23 Aug 2011)
@@ -65,7 +65,7 @@
void build_property_graph(Graph const&, boost::mpl::true_, boost::mpl::false_) {
using namespace boost;
BOOST_CONCEPT_ASSERT((VertexMutablePropertyGraphConcept<Graph>));
- typedef typename vertex_property<Graph>::type VertexProp;
+ typedef typename vertex_property_type<Graph>::type VertexProp;
std::cout << "...build mutable\n";
Modified: branches/release/libs/utility/enable_if.html
==============================================================================
--- branches/release/libs/utility/enable_if.html (original)
+++ branches/release/libs/utility/enable_if.html 2011-08-23 14:26:46 EDT (Tue, 23 Aug 2011)
@@ -21,6 +21,7 @@
<BR>
<BR>
Copyright 2003 Jaakko Järvi, Jeremiah Willcock, Andrew Lumsdaine.<BR>
+Copyright 2011 Matt Calabrese.<BR>
<BR>
<!--TOC section Introduction-->
@@ -81,7 +82,7 @@
<PRE>int::result_type negate(const int&);
</PRE>
-where the return type is invalid. If this was an error, adding an unrelated function template
+where the return type is invalid. If this were an error, adding an unrelated function template
(that was never called) could break otherwise valid code.
Due to the SFINAE principle the above example is not, however, erroneous.
The latter definition of <TT>negate</TT> is simply removed from the overload resolution set.<BR>
@@ -154,6 +155,7 @@
foo(T t) { return t; }
</PRE>
+
<!--TOC section Using <TT>enable_if</TT>-->
<H2><A NAME="htoc5">3</A> Using <TT>enable_if</TT></H2><!--SEC END -->
@@ -162,8 +164,19 @@
The <TT>enable_if</TT> templates are defined in
<TT>boost/utility/enable_if.hpp</TT>, which is included by <TT>boost/utility.hpp</TT>.<BR>
<BR>
-The <TT>enable_if</TT> template can be used either as the return type, or as an
-extra argument. For example, the <TT>foo</TT> function in the previous section could also be written
+With respect to function templates, <TT>enable_if</TT> can be used in multiple different ways:
+
+<UL>
+<LI>As the return type of an instantiatied function
+<LI>As an extra parameter of an instantiated function
+<LI>As an extra template parameter (useful only in a compiler that supports C++0x default
+arguments for function template parameters, see <A href="#sec:enable_if_0x">Enabling function
+templates in C++0x</a> for details)
+</UL>
+
+In the previous section, the return type form of <TT>enable_if</TT> was shown. As an example
+of using the form of <TT>enable_if</TT> that works via an extra function parameter, the
+<TT>foo</TT> function in the previous section could also be written
as:
<PRE>template <class T>
T foo(T t, typename enable_if<boost::is_arithmetic<T> >::type* dummy = 0);
@@ -173,18 +186,80 @@
Note that the second template argument was not given to <TT>enable_if</TT>, as the default
<TT>void</TT> gives the desired behavior.<BR>
<BR>
-Whether to write the enabler as an argument or within the return type is
-largely a matter of taste, but for certain functions, only one
-alternative is possible:
+Which way to write the enabler is largely a matter of taste, but for certain functions, only a
+subset of the options is possible:
<UL><LI>
-Operators have a fixed number of arguments, thus <TT>enable_if</TT> must be used in the return type.
-<LI>Constructors and destructors do not have a return type; an extra argument is the only option.
-<LI>There does not seem to be a way to specify an enabler for a conversion operator. Converting constructors,
-however, can have enablers as extra default arguments.
+Many operators have a fixed number of arguments, thus <TT>enable_if</TT> must be used either in the
+return type or in an extra template parameter.
+<LI>Functions that have a variadic parameter list must use either the return type form or an extra
+template parameter.
+<LI>Constructors do not have a return type so you must use either an extra function parameter or an
+extra template parameter.
+<LI>Constructors that have a variadic parameter list must an extra template parameter.
+<LI>Conversion operators can only be written with an extra template parameter.
</UL>
+<!--TOC subsection Enabling function templates in C++0x-->
+
+<A NAME="sec:enable_if_0x"></A>
+<H3><A NAME="htoc7">3.1</A> Enabling function templates in C++0x</H3><!--SEC END -->
+
+In a compiler which supports C++0x default arguments for function template parameters, you can
+enable and disable function templates by adding an additional template parameter. This approach
+works in all situations where you would use either the return type form of <TT>enable_if</TT> or
+the function parameter form, including operators, constructors, variadic function templates, and
+even overloaded conversion operations.
+
+As an example:
+
+<PRE>#include <boost/type_traits/is_arithmetic.hpp>
+#include <boost/type_traits/is_pointer.hpp>
+#include <boost/utility/enable_if.hpp>
+
+class test
+{
+public:
+ // A constructor that works for any argument list of size 10
+ template< class... T
+ , typename boost::enable_if_c< sizeof...( T ) == 10, int >::type = 0
+ >
+ test( T&&... );
+
+ // A conversion operation that can convert to any arithmetic type
+ template< class T
+ , typename boost::enable_if< boost::is_arithmetic< T >, int >::type = 0
+ >
+ operator T() const;
+
+ // A conversion operation that can convert to any pointer type
+ template< class T
+ , typename boost::enable_if< boost::is_pointer< T >, int >::type = 0
+ >
+ operator T() const;
+};
+
+int main()
+{
+ // Works
+ test test_( 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 );
+
+ // Fails as expected
+ test fail_construction( 1, 2, 3, 4, 5 );
+
+ // Works by calling the conversion operator enabled for arithmetic types
+ int arithmetic_object = test_;
+
+ // Works by calling the conversion operator enabled for pointer types
+ int* pointer_object = test_;
+
+ // Fails as expected
+ struct {} fail_conversion = test_;
+}
+
+</PRE>
+
<!--TOC subsection Enabling template class specializations-->
-<H3><A NAME="htoc6">3.1</A> Enabling template class specializations</H3><!--SEC END -->
+<H3><A NAME="htoc7">3.2</A> Enabling template class specializations</H3><!--SEC END -->
<A NAME="sec:enable_if_classes"></A>
Class template specializations can be enabled or disabled with <TT>enable_if</TT>.
@@ -210,7 +285,7 @@
<BR>
<!--TOC subsection Overlapping enabler conditions-->
-<H3><A NAME="htoc7">3.2</A> Overlapping enabler conditions</H3><!--SEC END -->
+<H3><A NAME="htoc8">3.3</A> Overlapping enabler conditions</H3><!--SEC END -->
<A NAME="sec:overlapping_conditions"></A>
Once the compiler has examined the enabling conditions and included the
@@ -239,7 +314,7 @@
<BR>
<!--TOC subsection Lazy <TT>enable_if</TT>-->
-<H3><A NAME="htoc8">3.3</A> Lazy <TT>enable_if</TT></H3><!--SEC END -->
+<H3><A NAME="htoc9">3.4</A> Lazy <TT>enable_if</TT></H3><!--SEC END -->
<A NAME="sec:enable_if_lazy"></A>
In some cases it is necessary to avoid instantiating part of a
@@ -285,7 +360,7 @@
<BR>
<!--TOC subsection Compiler workarounds-->
-<H3><A NAME="htoc9">3.4</A> Compiler workarounds</H3><!--SEC END -->
+<H3><A NAME="htoc10">3.5</A> Compiler workarounds</H3><!--SEC END -->
<A NAME="sec:workarounds"></A>
Some compilers flag functions as ambiguous if the only distinguishing factor is a different
@@ -367,9 +442,9 @@
Addison-Wesley, 2002.</DL>
<hr/>
- <p>Copyright Jaakko Järvi, Jeremiah Willcock and Andrew Lumsdaine<BR>
-<EM>{jajarvi|jewillco|lums}@osl.iu.edu</EM><BR>
-Indiana University<BR>
+ <p>Copyright Jaakko Järvi<sup>*</sup>, Jeremiah Willcock<sup>*</sup>, Andrew Lumsdaine<sup>*</sup>, Matt Calabrese<BR>
+<EM>{jajarvi|jewillco|lums}@osl.iu.edu, rivorus_at_[hidden]</EM><BR>
+<sup>*</sup>Indiana University<BR>
Open Systems Lab<br/>
Use, modification and distribution are subject to the
Boost Software License, Version 1.0.
@@ -386,4 +461,4 @@
</EM>HEVEA<EM>.
</EM></BLOCKQUOTE>
</BODY>
-</HTML>
\ No newline at end of file
+</HTML>
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