|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r85813 - in branches/release: . boost boost/algorithm boost/algorithm/cxx11 boost/algorithm/searching boost/algorithm/searching/detail boost/algorithm/string/detail boost/archive boost/bimap boost/chrono/detail boost/chrono/io boost/chrono/io_v1 boost/circular_buffer boost/context boost/coroutine boost/date_time boost/date_time/local_time boost/detail boost/dynamic_bitset boost/filesystem boost/function boost/functional boost/functional/overloaded_function boost/fusion boost/geometry boost/geometry/algorithms boost/geometry/arithmetic boost/geometry/core boost/geometry/domains boost/geometry/geometries boost/geometry/index boost/geometry/io boost/geometry/io/dsv boost/geometry/iterators boost/geometry/multi boost/geometry/policies boost/geometry/strategies boost/geometry/util boost/geometry/views boost/gil boost/graph boost/graph/detail boost/graph/distributed boost/graph/distributed/adjlist boost/graph/property_maps boost/heap boost/icl boost/integer boost/intrusive boost/io boost/iostreams boost/iterator boost/lambda boost/local_function boost/locale boost/lockfree boost/math boost/move boost/mpi boost/msm boost/msm/back boost/msm/front boost/msm/front/detail boost/msm/front/euml boost/msm/mpl_graph boost/multi_index boost/numeric boost/numeric/odeint boost/numeric/ublas boost/parameter boost/pending boost/pool boost/predef boost/preprocessor boost/program_options boost/property_map boost/property_tree boost/proto boost/python boost/random boost/random/detail boost/range boost/ratio boost/serialization boost/signals boost/spirit boost/spirit/home boost/spirit/home/karma boost/spirit/home/support boost/statechart boost/system boost/thread boost/tr1 boost/type_erasure boost/type_traits boost/typeof boost/unordered boost/utility boost/uuid boost/variant boost/wave boost/xpressive doc libs libs/algorithm libs/algorithm/doc libs/algorithm/example libs/algorithm/minmax libs/algorithm/string libs/algorithm/string/doc libs/algorithm/string/test libs/algorithm/test libs/algorithm/test/search_test_data libs/any libs/array libs/array/test libs/bimap libs/chrono/example libs/chrono/src libs/chrono/test libs/chrono/test/clock libs/chrono/test/duration libs/chrono/test/io libs/chrono/test/time_point libs/chrono/test/traits libs/circular_buffer libs/context libs/coroutine libs/coroutine/doc libs/date_time libs/date_time/src/gregorian libs/detail libs/filesystem libs/function libs/function/test libs/functional libs/functional/overloaded_function 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/index libs/geometry/doc/reference libs/geometry/doc/src libs/geometry/example libs/geometry/index libs/geometry/index/example libs/geometry/index/test libs/geometry/test libs/graph libs/graph/build libs/graph/doc libs/graph/example libs/graph/src libs/graph/test libs/graph_parallel libs/graph_parallel/test libs/heap libs/icl libs/icl/doc libs/icl/doc/html libs/icl/doc/html/boost/icl libs/icl/doc/html/header/boost/icl libs/icl/example libs/icl/test libs/icl/test/test_doc_code_ libs/integer libs/intrusive libs/io libs/io/doc libs/iostreams libs/iostreams/src libs/iostreams/test libs/iterator libs/local_function libs/locale libs/lockfree libs/math libs/math/doc/overview libs/math/example libs/math/test libs/move libs/mpi libs/mpi/build libs/mpl/doc/refmanual libs/mpl/doc/src/refmanual libs/msm libs/multi_index libs/multi_index/doc libs/numeric/odeint libs/numeric/odeint/doc libs/numeric/ublas libs/numeric/ublas/doc libs/parameter/doc/html libs/phoenix/doc libs/phoenix/doc/examples libs/pool libs/pool/doc/images libs/predef libs/preprocessor libs/program_options libs/property_map libs/property_map/test libs/property_tree libs/python libs/random/test libs/range libs/ratio libs/scope_exit libs/serialization libs/serialization/example libs/serialization/src libs/serialization/test libs/signals libs/signals/src libs/signals2 libs/spirit libs/spirit/classic/example libs/spirit/doc libs/spirit/example libs/spirit/example/qi/compiler_tutorial/conjure2 libs/spirit/phoenix libs/spirit/test libs/spirit/test/qi libs/statechart libs/static_assert libs/system libs/thread libs/timer libs/tr1 libs/type_erasure libs/type_traits libs/typeof/doc libs/unordered libs/utility libs/utility/doc libs/utility/identity_type libs/utility/swap/test libs/utility/test libs/uuid libs/wave more status tools tools/auto_index tools/bcp tools/boostbook tools/build tools/build/v2 tools/inspect tools/inspect/build tools/quickbook tools/regression tools/regression/src tools/release tools/wave
From: jewillco_at_[hidden]
Date: 2013-09-21 16:17:01
Author: jewillco
Date: 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013)
New Revision: 85813
URL: http://svn.boost.org/trac/boost/changeset/85813
Log:
Merged Boost.Graph, Boost.Graph.Parallel, and Boost.PropertyMap changes from Boost trunk
Added:
branches/release/boost/graph/cycle_canceling.hpp
- copied, changed from r85536, trunk/boost/graph/cycle_canceling.hpp
branches/release/boost/graph/detail/augment.hpp
- copied unchanged from r85536, trunk/boost/graph/detail/augment.hpp
branches/release/boost/graph/edge_coloring.hpp
- copied unchanged from r85534, trunk/boost/graph/edge_coloring.hpp
branches/release/boost/graph/find_flow_cost.hpp
- copied unchanged from r85536, trunk/boost/graph/find_flow_cost.hpp
branches/release/boost/graph/hawick_circuits.hpp (contents, props changed)
- copied, changed from r85533, trunk/boost/graph/hawick_circuits.hpp
branches/release/boost/graph/successive_shortest_path_nonnegative_weights.hpp
- copied unchanged from r85568, trunk/boost/graph/successive_shortest_path_nonnegative_weights.hpp
branches/release/libs/graph/doc/cycle_canceling.html
- copied, changed from r85536, trunk/libs/graph/doc/cycle_canceling.html
branches/release/libs/graph/doc/edge_coloring.html
- copied unchanged from r85534, trunk/libs/graph/doc/edge_coloring.html
branches/release/libs/graph/doc/find_flow_cost.html
- copied, changed from r85536, trunk/libs/graph/doc/find_flow_cost.html
branches/release/libs/graph/doc/hawick_circuits.html
- copied unchanged from r85533, trunk/libs/graph/doc/hawick_circuits.html
branches/release/libs/graph/doc/hawick_circuits.md
- copied unchanged from r85533, trunk/libs/graph/doc/hawick_circuits.md
branches/release/libs/graph/doc/successive_shortest_path_nonnegative_weights.html
- copied unchanged from r85568, trunk/libs/graph/doc/successive_shortest_path_nonnegative_weights.html
branches/release/libs/graph/example/cycle_canceling_example.cpp (contents, props changed)
- copied, changed from r85536, trunk/libs/graph/example/cycle_canceling_example.cpp
branches/release/libs/graph/example/edge_coloring.cpp
- copied unchanged from r85534, trunk/libs/graph/example/edge_coloring.cpp
branches/release/libs/graph/example/hawick_circuits.cpp
- copied unchanged from r85533, trunk/libs/graph/example/hawick_circuits.cpp
branches/release/libs/graph/example/successive_shortest_path_nonnegative_weights_example.cpp (contents, props changed)
- copied, changed from r85568, trunk/libs/graph/example/successive_shortest_path_nonnegative_weights_example.cpp
branches/release/libs/graph/test/cycle_canceling_test.cpp (contents, props changed)
- copied, changed from r85536, trunk/libs/graph/test/cycle_canceling_test.cpp
branches/release/libs/graph/test/cycle_test.hpp (contents, props changed)
- copied, changed from r85533, trunk/libs/graph/test/cycle_test.hpp
branches/release/libs/graph/test/hawick_circuits.cpp
- copied unchanged from r85533, trunk/libs/graph/test/hawick_circuits.cpp
branches/release/libs/graph/test/min_cost_max_flow_utils.hpp (contents, props changed)
- copied, changed from r85536, trunk/libs/graph/test/min_cost_max_flow_utils.hpp
branches/release/libs/graph/test/rcsp_custom_vertex_id.cpp (contents, props changed)
- copied, changed from r85571, trunk/libs/graph/test/rcsp_custom_vertex_id.cpp
branches/release/libs/graph/test/successive_shortest_path_nonnegative_weights_test.cpp (contents, props changed)
- copied, changed from r85568, trunk/libs/graph/test/successive_shortest_path_nonnegative_weights_test.cpp
branches/release/libs/graph/test/undirected_dfs.cpp (contents, props changed)
- copied, changed from r78030, trunk/libs/graph/test/undirected_dfs.cpp
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/ (props changed)
branches/release/boost/algorithm/clamp.hpp (props changed)
branches/release/boost/algorithm/cxx11/all_of.hpp (props changed)
branches/release/boost/algorithm/cxx11/any_of.hpp (props changed)
branches/release/boost/algorithm/cxx11/copy_if.hpp (props changed)
branches/release/boost/algorithm/cxx11/copy_n.hpp (props changed)
branches/release/boost/algorithm/cxx11/find_if_not.hpp (props changed)
branches/release/boost/algorithm/cxx11/iota.hpp (props changed)
branches/release/boost/algorithm/cxx11/is_partitioned.hpp (props changed)
branches/release/boost/algorithm/cxx11/is_permutation.hpp (props changed)
branches/release/boost/algorithm/cxx11/is_sorted.hpp (props changed)
branches/release/boost/algorithm/cxx11/none_of.hpp (props changed)
branches/release/boost/algorithm/cxx11/one_of.hpp (props changed)
branches/release/boost/algorithm/cxx11/partition_copy.hpp (props changed)
branches/release/boost/algorithm/cxx11/partition_point.hpp (props changed)
branches/release/boost/algorithm/hex.hpp (props changed)
branches/release/boost/algorithm/minmax_element.hpp (props changed)
branches/release/boost/algorithm/searching/ (props changed)
branches/release/boost/algorithm/searching/boyer_moore.hpp (props changed)
branches/release/boost/algorithm/searching/boyer_moore_horspool.hpp (props changed)
branches/release/boost/algorithm/searching/detail/bm_traits.hpp (props changed)
branches/release/boost/algorithm/searching/detail/debugging.hpp (props changed)
branches/release/boost/algorithm/searching/knuth_morris_pratt.hpp (props changed)
branches/release/boost/algorithm/string/detail/case_conv.hpp (props changed)
branches/release/boost/algorithm/string/detail/classification.hpp (props changed)
branches/release/boost/any.hpp (props changed)
branches/release/boost/archive/ (props changed)
branches/release/boost/array.hpp (props changed)
branches/release/boost/assert.hpp (props changed)
branches/release/boost/bimap/ (props changed)
branches/release/boost/bimap.hpp (props changed)
branches/release/boost/chrono/detail/ (props changed)
branches/release/boost/chrono/io/ (props changed)
branches/release/boost/chrono/io_v1/ (props changed)
branches/release/boost/circular_buffer/ (props changed)
branches/release/boost/circular_buffer.hpp (props changed)
branches/release/boost/concept_check.hpp (props changed)
branches/release/boost/context/ (props changed)
branches/release/boost/coroutine/ (props changed)
branches/release/boost/cstdint.hpp (props changed)
branches/release/boost/date_time/ (props changed)
branches/release/boost/date_time/format_date_parser.hpp (props changed)
branches/release/boost/date_time/local_time/custom_time_zone.hpp (props changed)
branches/release/boost/date_time/strings_from_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/fenv.hpp (props changed)
branches/release/boost/detail/interlocked.hpp (props changed)
branches/release/boost/detail/scoped_enum_emulation.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/foreach.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/functional/overloaded_function/ (props changed)
branches/release/boost/functional/overloaded_function.hpp (props changed)
branches/release/boost/fusion/ (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/index/ (props changed)
branches/release/boost/geometry/io/ (props changed)
branches/release/boost/geometry/io/dsv/ (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/graph/adjacency_list.hpp (props changed)
branches/release/boost/graph/astar_search.hpp (props changed)
branches/release/boost/graph/bellman_ford_shortest_paths.hpp (contents, props changed)
branches/release/boost/graph/betweenness_centrality.hpp (contents, props changed)
branches/release/boost/graph/bipartite.hpp (contents, props changed)
branches/release/boost/graph/boykov_kolmogorov_max_flow.hpp (props changed)
branches/release/boost/graph/breadth_first_search.hpp (contents, props changed)
branches/release/boost/graph/chrobak_payne_drawing.hpp (contents, props changed)
branches/release/boost/graph/closeness_centrality.hpp (contents, props changed)
branches/release/boost/graph/compressed_sparse_row_graph.hpp (contents, props changed)
branches/release/boost/graph/connected_components.hpp (contents, props changed)
branches/release/boost/graph/core_numbers.hpp (contents, props changed)
branches/release/boost/graph/cuthill_mckee_ordering.hpp (contents, props changed)
branches/release/boost/graph/depth_first_search.hpp (contents, props changed)
branches/release/boost/graph/detail/ (props changed)
branches/release/boost/graph/detail/adjacency_list.hpp (contents, props changed)
branches/release/boost/graph/detail/compressed_sparse_row_struct.hpp (props changed)
branches/release/boost/graph/detail/d_ary_heap.hpp (props changed)
branches/release/boost/graph/detail/histogram_sort.hpp (props changed)
branches/release/boost/graph/detail/labeled_graph_traits.hpp (props changed)
branches/release/boost/graph/dijkstra_shortest_paths.hpp (contents, props changed)
branches/release/boost/graph/dijkstra_shortest_paths_no_color_map.hpp (contents, props changed)
branches/release/boost/graph/directed_graph.hpp (props changed)
branches/release/boost/graph/distributed/adjacency_list.hpp (contents, props changed)
branches/release/boost/graph/distributed/adjlist/redistribute.hpp (contents, props changed)
branches/release/boost/graph/distributed/adjlist/serialization.hpp (contents, props changed)
branches/release/boost/graph/distributed/betweenness_centrality.hpp (contents, props changed)
branches/release/boost/graph/distributed/boman_et_al_graph_coloring.hpp (contents, props changed)
branches/release/boost/graph/distributed/breadth_first_search.hpp (contents, props changed)
branches/release/boost/graph/distributed/compressed_sparse_row_graph.hpp (contents, props changed)
branches/release/boost/graph/distributed/concepts.hpp (contents, props changed)
branches/release/boost/graph/distributed/connected_components.hpp (contents, props changed)
branches/release/boost/graph/distributed/connected_components_parallel_search.hpp (contents, props changed)
branches/release/boost/graph/distributed/crauser_et_al_shortest_paths.hpp (contents, props changed)
branches/release/boost/graph/distributed/dehne_gotz_min_spanning_tree.hpp (contents, props changed)
branches/release/boost/graph/distributed/eager_dijkstra_shortest_paths.hpp (contents, props changed)
branches/release/boost/graph/distributed/graphviz.hpp (contents, props changed)
branches/release/boost/graph/distributed/hohberg_biconnected_components.hpp (contents, props changed)
branches/release/boost/graph/distributed/named_graph.hpp (contents, props changed)
branches/release/boost/graph/distributed/page_rank.hpp (contents, props changed)
branches/release/boost/graph/distributed/selector.hpp (props changed)
branches/release/boost/graph/distributed/strong_components.hpp (contents, props changed)
branches/release/boost/graph/edmonds_karp_max_flow.hpp (contents, props changed)
branches/release/boost/graph/fruchterman_reingold.hpp (contents, props changed)
branches/release/boost/graph/graph_concepts.hpp (props changed)
branches/release/boost/graph/graph_traits.hpp (contents, props changed)
branches/release/boost/graph/graph_utility.hpp (contents, props changed)
branches/release/boost/graph/graphml.hpp (props changed)
branches/release/boost/graph/gursoy_atun_layout.hpp (contents, props changed)
branches/release/boost/graph/is_straight_line_drawing.hpp (contents, props changed)
branches/release/boost/graph/kamada_kawai_spring_layout.hpp (props changed)
branches/release/boost/graph/king_ordering.hpp (contents, props changed)
branches/release/boost/graph/kruskal_min_spanning_tree.hpp (contents, props changed)
branches/release/boost/graph/labeled_graph.hpp (props changed)
branches/release/boost/graph/max_cardinality_matching.hpp (props changed)
branches/release/boost/graph/maximum_adjacency_search.hpp (contents, props changed)
branches/release/boost/graph/mcgregor_common_subgraphs.hpp (contents, props changed)
branches/release/boost/graph/metric_tsp_approx.hpp (contents, props changed)
branches/release/boost/graph/named_graph.hpp (props changed)
branches/release/boost/graph/planar_canonical_ordering.hpp (contents, props changed)
branches/release/boost/graph/properties.hpp (props changed)
branches/release/boost/graph/property_maps/constant_property_map.hpp (props changed)
branches/release/boost/graph/r_c_shortest_paths.hpp (contents, props changed)
branches/release/boost/graph/random.hpp (contents, props changed)
branches/release/boost/graph/random_spanning_tree.hpp (contents, props changed)
branches/release/boost/graph/read_dimacs.hpp (contents, props changed)
branches/release/boost/graph/reverse_graph.hpp (props changed)
branches/release/boost/graph/stoer_wagner_min_cut.hpp (contents, props changed)
branches/release/boost/graph/tiernan_all_cycles.hpp (contents, props changed)
branches/release/boost/graph/transitive_closure.hpp (contents, props changed)
branches/release/boost/graph/two_graphs_common_spanning_trees.hpp (contents, props changed)
branches/release/boost/graph/undirected_dfs.hpp (contents, props changed)
branches/release/boost/graph/undirected_graph.hpp (props changed)
branches/release/boost/graph/vf2_sub_graph_iso.hpp (contents, props changed)
branches/release/boost/graph/visitors.hpp (contents, props changed)
branches/release/boost/graph/write_dimacs.hpp (contents, props changed)
branches/release/boost/heap/ (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/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/lambda/ (props changed)
branches/release/boost/local_function/ (props changed)
branches/release/boost/local_function.hpp (props changed)
branches/release/boost/locale/ (props changed)
branches/release/boost/locale.hpp (props changed)
branches/release/boost/lockfree/ (props changed)
branches/release/boost/math/ (props changed)
branches/release/boost/math_fwd.hpp (props changed)
branches/release/boost/move/ (props changed)
branches/release/boost/mpi/ (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/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/event_traits.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/multi_index/ (props changed)
branches/release/boost/multi_index/ordered_index.hpp (props changed)
branches/release/boost/multi_index_container.hpp (props changed)
branches/release/boost/numeric/odeint/ (props changed)
branches/release/boost/numeric/odeint.hpp (props changed)
branches/release/boost/numeric/ublas/ (props changed)
branches/release/boost/numeric/ublas/functional.hpp (props changed)
branches/release/boost/parameter/ (props changed)
branches/release/boost/parameter.hpp (props changed)
branches/release/boost/pending/property.hpp (props changed)
branches/release/boost/pool/ (props changed)
branches/release/boost/predef/ (props changed)
branches/release/boost/predef.h (props changed)
branches/release/boost/preprocessor/ (props changed)
branches/release/boost/program_options/ (props changed)
branches/release/boost/property_map/ (props changed)
branches/release/boost/property_map/dynamic_property_map.hpp (contents, props changed)
branches/release/boost/property_map/property_map.hpp (contents, props changed)
branches/release/boost/property_tree/ (props changed)
branches/release/boost/proto/ (props changed)
branches/release/boost/python/ (props changed)
branches/release/boost/random/ (props changed)
branches/release/boost/random/detail/integer_log2.hpp (props changed)
branches/release/boost/random/discrete_distribution.hpp (props changed)
branches/release/boost/random/piecewise_constant_distribution.hpp (props changed)
branches/release/boost/random/piecewise_linear_distribution.hpp (props changed)
branches/release/boost/random/seed_seq.hpp (props changed)
branches/release/boost/random/subtract_with_carry.hpp (props changed)
branches/release/boost/range/ (props changed)
branches/release/boost/ratio/ (props changed)
branches/release/boost/regex.h (props changed)
branches/release/boost/regex_fwd.hpp (props changed)
branches/release/boost/scope_exit.hpp (props changed)
branches/release/boost/serialization/ (props changed)
branches/release/boost/signals/ (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/timer.hpp (props changed)
branches/release/boost/token_functions.hpp (props changed)
branches/release/boost/tr1/ (props changed)
branches/release/boost/type_erasure/ (props changed)
branches/release/boost/type_traits/ (props changed)
branches/release/boost/type_traits.hpp (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/explicit_operator_bool.hpp (props changed)
branches/release/boost/utility/identity_type.hpp (props changed)
branches/release/boost/utility/result_of.hpp (props changed)
branches/release/boost/utility/string_ref.hpp (props changed)
branches/release/boost/utility/string_ref_fwd.hpp (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/ (props changed)
branches/release/libs/algorithm/doc/ (props changed)
branches/release/libs/algorithm/doc/Jamfile.v2 (props changed)
branches/release/libs/algorithm/doc/algorithm.qbk (props changed)
branches/release/libs/algorithm/doc/all_of.qbk (props changed)
branches/release/libs/algorithm/doc/any_of.qbk (props changed)
branches/release/libs/algorithm/doc/boyer_moore.qbk (props changed)
branches/release/libs/algorithm/doc/boyer_moore_horspool.qbk (props changed)
branches/release/libs/algorithm/doc/clamp-hpp.qbk (props changed)
branches/release/libs/algorithm/doc/hex.qbk (props changed)
branches/release/libs/algorithm/doc/is_partitioned.qbk (props changed)
branches/release/libs/algorithm/doc/knuth_morris_pratt.qbk (props changed)
branches/release/libs/algorithm/doc/none_of.qbk (props changed)
branches/release/libs/algorithm/doc/one_of.qbk (props changed)
branches/release/libs/algorithm/doc/ordered-hpp.qbk (props changed)
branches/release/libs/algorithm/doc/partition_point.qbk (props changed)
branches/release/libs/algorithm/example/Jamfile.v2 (props changed)
branches/release/libs/algorithm/example/clamp_example.cpp (props changed)
branches/release/libs/algorithm/example/search_example.cpp (props changed)
branches/release/libs/algorithm/minmax/index.html (props changed)
branches/release/libs/algorithm/string/ (props changed)
branches/release/libs/algorithm/string/doc/Jamfile.v2 (props changed)
branches/release/libs/algorithm/string/doc/usage.xml (props changed)
branches/release/libs/algorithm/string/test/find_test.cpp (props changed)
branches/release/libs/algorithm/string/test/split_test.cpp (props changed)
branches/release/libs/algorithm/test/ (props changed)
branches/release/libs/algorithm/test/Jamfile.v2 (props changed)
branches/release/libs/algorithm/test/all_of_test.cpp (props changed)
branches/release/libs/algorithm/test/any_of_test.cpp (props changed)
branches/release/libs/algorithm/test/clamp_test.cpp (props changed)
branches/release/libs/algorithm/test/copy_if_test1.cpp (props changed)
branches/release/libs/algorithm/test/copy_n_test1.cpp (props changed)
branches/release/libs/algorithm/test/empty_search_test.cpp (props changed)
branches/release/libs/algorithm/test/find_if_not_test1.cpp (props changed)
branches/release/libs/algorithm/test/hex_fail1.cpp (props changed)
branches/release/libs/algorithm/test/hex_test1.cpp (props changed)
branches/release/libs/algorithm/test/hex_test2.cpp (props changed)
branches/release/libs/algorithm/test/hex_test3.cpp (props changed)
branches/release/libs/algorithm/test/hex_test4.cpp (props changed)
branches/release/libs/algorithm/test/iota_test1.cpp (props changed)
branches/release/libs/algorithm/test/is_partitioned_test1.cpp (props changed)
branches/release/libs/algorithm/test/is_permutation_test1.cpp (props changed)
branches/release/libs/algorithm/test/none_of_test.cpp (props changed)
branches/release/libs/algorithm/test/one_of_test.cpp (props changed)
branches/release/libs/algorithm/test/ordered_test.cpp (props changed)
branches/release/libs/algorithm/test/partition_copy_test1.cpp (props changed)
branches/release/libs/algorithm/test/partition_point_test1.cpp (props changed)
branches/release/libs/algorithm/test/search_fail1.cpp (props changed)
branches/release/libs/algorithm/test/search_fail2.cpp (props changed)
branches/release/libs/algorithm/test/search_fail3.cpp (props changed)
branches/release/libs/algorithm/test/search_test1.cpp (props changed)
branches/release/libs/algorithm/test/search_test2.cpp (props changed)
branches/release/libs/algorithm/test/search_test3.cpp (props changed)
branches/release/libs/algorithm/test/search_test_data/0001.corpus (props changed)
branches/release/libs/algorithm/test/search_test_data/0001b.pat (props changed)
branches/release/libs/algorithm/test/search_test_data/0001e.pat (props changed)
branches/release/libs/algorithm/test/search_test_data/0001f.pat (props changed)
branches/release/libs/algorithm/test/search_test_data/0001n.pat (props changed)
branches/release/libs/algorithm/test/search_test_data/0002b.pat (props changed)
branches/release/libs/algorithm/test/search_test_data/0002e.pat (props changed)
branches/release/libs/algorithm/test/search_test_data/0002f.pat (props changed)
branches/release/libs/algorithm/test/search_test_data/0002n.pat (props changed)
branches/release/libs/any/ (props changed)
branches/release/libs/array/ (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/array2.cpp (props changed)
branches/release/libs/array/test/array6.cpp (props changed)
branches/release/libs/array/test/array_hash.cpp (props changed)
branches/release/libs/bimap/ (props changed)
branches/release/libs/chrono/example/ (props changed)
branches/release/libs/chrono/src/ (props changed)
branches/release/libs/chrono/test/clock/ (props changed)
branches/release/libs/chrono/test/duration/ (props changed)
branches/release/libs/chrono/test/io/ (props changed)
branches/release/libs/chrono/test/time_point/ (props changed)
branches/release/libs/chrono/test/traits/ (props changed)
branches/release/libs/chrono/test/win32_test.cpp (props changed)
branches/release/libs/circular_buffer/ (props changed)
branches/release/libs/context/ (props changed)
branches/release/libs/coroutine/ (props changed)
branches/release/libs/coroutine/doc/ (props changed)
branches/release/libs/date_time/ (props changed)
branches/release/libs/date_time/src/gregorian/ (props changed)
branches/release/libs/detail/ (props changed)
branches/release/libs/filesystem/ (props changed)
branches/release/libs/function/ (props changed)
branches/release/libs/function/test/function_test.cpp (props changed)
branches/release/libs/functional/ (props changed)
branches/release/libs/functional/overloaded_function/ (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/index/ (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/release_notes.qbk (props changed)
branches/release/libs/geometry/doc/src/ (props changed)
branches/release/libs/geometry/example/ (props changed)
branches/release/libs/geometry/index/ (props changed)
branches/release/libs/geometry/index.html (props changed)
branches/release/libs/geometry/index/example/ (props changed)
branches/release/libs/geometry/index/test/ (props changed)
branches/release/libs/geometry/test/ (props changed)
branches/release/libs/graph/ (props changed)
branches/release/libs/graph/build/Jamfile.v2 (contents, props changed)
branches/release/libs/graph/doc/ (props changed)
branches/release/libs/graph/doc/DFSVisitor.html (contents, props changed)
branches/release/libs/graph/doc/astar_search.html (props changed)
branches/release/libs/graph/doc/depth_first_search.html (contents, props changed)
branches/release/libs/graph/doc/dijkstra_shortest_paths_no_color_map.html (contents, props changed)
branches/release/libs/graph/doc/graph_concepts.html (props changed)
branches/release/libs/graph/doc/push_relabel_max_flow.html (props changed)
branches/release/libs/graph/doc/read_graphml.html (props changed)
branches/release/libs/graph/doc/read_graphml.rst (props changed)
branches/release/libs/graph/doc/small_world_generator.html (props changed)
branches/release/libs/graph/doc/table_of_contents.html (contents, props changed)
branches/release/libs/graph/doc/undirected_dfs.html (contents, props changed)
branches/release/libs/graph/doc/vf2_sub_graph_iso.html (props changed)
branches/release/libs/graph/example/ (props changed)
branches/release/libs/graph/example/Jamfile.v2 (contents, props changed)
branches/release/libs/graph/example/astar-cities.cpp (contents, props changed)
branches/release/libs/graph/example/bfs-example.cpp (contents, props changed)
branches/release/libs/graph/example/bfs-example2.cpp (contents, props changed)
branches/release/libs/graph/example/canonical_ordering.cpp (contents, props changed)
branches/release/libs/graph/example/dfs-example.cpp (contents, props changed)
branches/release/libs/graph/example/dfs.cpp (contents, props changed)
branches/release/libs/graph/example/dfs.expected (contents, props changed)
branches/release/libs/graph/example/dijkstra-example-listS.cpp (contents, props changed)
branches/release/libs/graph/example/dijkstra-example.cpp (contents, props changed)
branches/release/libs/graph/example/dijkstra-no-color-map-example.cpp (contents, props changed)
branches/release/libs/graph/example/implicit_graph.cpp (contents, props changed)
branches/release/libs/graph/example/mcgregor_subgraphs_example.cpp (contents, props changed)
branches/release/libs/graph/example/stoer_wagner.cpp (contents, props changed)
branches/release/libs/graph/example/subgraph.cpp (contents, props changed)
branches/release/libs/graph/example/undirected_adjacency_list.cpp (props changed)
branches/release/libs/graph/example/undirected_adjacency_list.expected (props changed)
branches/release/libs/graph/example/vf2_sub_graph_iso_multi_example.cpp (props changed)
branches/release/libs/graph/src/graphml.cpp (props changed)
branches/release/libs/graph/src/read_graphviz_new.cpp (props changed)
branches/release/libs/graph/test/ (props changed)
branches/release/libs/graph/test/adj_list_loops.cpp (contents, props changed)
branches/release/libs/graph/test/all_planar_input_files_test.cpp (contents, props changed)
branches/release/libs/graph/test/astar_search_test.cpp (contents, props changed)
branches/release/libs/graph/test/bellman-test.cpp (contents, props changed)
branches/release/libs/graph/test/bfs.cpp (contents, props changed)
branches/release/libs/graph/test/boykov_kolmogorov_max_flow_test.cpp (contents, props changed)
branches/release/libs/graph/test/closeness_centrality.cpp (contents, props changed)
branches/release/libs/graph/test/clustering_coefficient.cpp (contents, props changed)
branches/release/libs/graph/test/cycle_ratio_tests.cpp (contents, props changed)
branches/release/libs/graph/test/degree_centrality.cpp (contents, props changed)
branches/release/libs/graph/test/dfs.cpp (contents, props changed)
branches/release/libs/graph/test/dijkstra_heap_performance.cpp (contents, props changed)
branches/release/libs/graph/test/dijkstra_no_color_map_compare.cpp (contents, props changed)
branches/release/libs/graph/test/eccentricity.cpp (contents, props changed)
branches/release/libs/graph/test/graphviz_test.cpp (contents, props changed)
branches/release/libs/graph/test/index_graph.cpp (contents, props changed)
branches/release/libs/graph/test/layout_test.cpp (contents, props changed)
branches/release/libs/graph/test/make_connected_test.cpp (contents, props changed)
branches/release/libs/graph/test/matching_test.cpp (contents, props changed)
branches/release/libs/graph/test/mcgregor_subgraphs_test.cpp (contents, props changed)
branches/release/libs/graph/test/mean_geodesic.cpp (contents, props changed)
branches/release/libs/graph/test/metric_tsp_approx.cpp (contents, props changed)
branches/release/libs/graph/test/parallel_edges_loops_test.cpp (contents, props changed)
branches/release/libs/graph/test/property_iter.cpp (contents, props changed)
branches/release/libs/graph/test/sequential_vertex_coloring.cpp (contents, props changed)
branches/release/libs/graph/test/stoer_wagner_test.cpp (contents, props changed)
branches/release/libs/graph/test/subgraph.cpp (contents, props changed)
branches/release/libs/graph/test/test_properties.hpp (contents, props changed)
branches/release/libs/graph/test/tiernan_all_cycles.cpp (contents, props changed)
branches/release/libs/graph/test/transitive_closure_test.cpp (contents, props changed)
branches/release/libs/graph_parallel/ (props changed)
branches/release/libs/graph_parallel/test/adjlist_redist_test.cpp (contents, props changed)
branches/release/libs/graph_parallel/test/adjlist_remove_test.cpp (contents, props changed)
branches/release/libs/graph_parallel/test/distributed_betweenness_centrality_test.cpp (contents, props changed)
branches/release/libs/graph_parallel/test/distributed_connected_components_test.cpp (contents, props changed)
branches/release/libs/graph_parallel/test/distributed_csr_algorithm_test.cpp (contents, props changed)
branches/release/libs/graph_parallel/test/distributed_csr_test.cpp (contents, props changed)
branches/release/libs/graph_parallel/test/distributed_dfs_test.cpp (contents, props changed)
branches/release/libs/graph_parallel/test/distributed_graph_coloring_test.cpp (contents, props changed)
branches/release/libs/graph_parallel/test/distributed_mst_test.cpp (contents, props changed)
branches/release/libs/graph_parallel/test/distributed_shortest_paths_test.cpp (contents, props changed)
branches/release/libs/graph_parallel/test/distributed_st_connected_test.cpp (contents, props changed)
branches/release/libs/graph_parallel/test/distributed_strong_components_test.cpp (contents, props changed)
branches/release/libs/heap/ (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/boost/icl/ (props changed)
branches/release/libs/icl/doc/html/header/boost/icl/ (props changed)
branches/release/libs/icl/example/ (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/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/iostreams/src/file_descriptor.cpp (props changed)
branches/release/libs/iostreams/test/Jamfile.v2 (props changed)
branches/release/libs/iostreams/test/windows_pipe_test.cpp (props changed)
branches/release/libs/iterator/ (props changed)
branches/release/libs/libraries.htm (props changed)
branches/release/libs/local_function/ (props changed)
branches/release/libs/locale/ (props changed)
branches/release/libs/lockfree/ (props changed)
branches/release/libs/maintainers.txt (props changed)
branches/release/libs/math/ (props changed)
branches/release/libs/math/doc/overview/faq.qbk (props changed)
branches/release/libs/math/example/ (props changed)
branches/release/libs/math/test/s_.ipp (props changed)
branches/release/libs/move/ (props changed)
branches/release/libs/mpi/ (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/multi_index/ (props changed)
branches/release/libs/multi_index/doc/compiler_specifics.html (props changed)
branches/release/libs/numeric/odeint/ (props changed)
branches/release/libs/numeric/odeint/doc/ (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/pool/doc/images/mb1.png (props changed)
branches/release/libs/pool/doc/images/mb2.png (props changed)
branches/release/libs/pool/doc/images/mb3.png (props changed)
branches/release/libs/pool/doc/images/mb4.png (props changed)
branches/release/libs/pool/doc/images/pc1.png (props changed)
branches/release/libs/pool/doc/images/pc2.png (props changed)
branches/release/libs/pool/doc/images/pc3.png (props changed)
branches/release/libs/pool/doc/images/pc4.png (props changed)
branches/release/libs/pool/doc/images/pc5.png (props changed)
branches/release/libs/predef/ (props changed)
branches/release/libs/preprocessor/ (props changed)
branches/release/libs/program_options/ (props changed)
branches/release/libs/property_map/ (props changed)
branches/release/libs/property_map/test/property_map_cc.cpp (contents, props changed)
branches/release/libs/property_tree/ (props changed)
branches/release/libs/python/ (props changed)
branches/release/libs/random/test/Jamfile.v2 (props changed)
branches/release/libs/random/test/test_discrete_distribution.cpp (props changed)
branches/release/libs/random/test/test_piecewise_constant_distribution.cpp (props changed)
branches/release/libs/random/test/test_piecewise_linear_distribution.cpp (props changed)
branches/release/libs/random/test/test_seed_seq.cpp (props changed)
branches/release/libs/random/test/test_zero_seed.cpp (props changed)
branches/release/libs/range/ (props changed)
branches/release/libs/ratio/ (props changed)
branches/release/libs/scope_exit/ (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/signals/src/named_slot_map.cpp (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/example/qi/compiler_tutorial/conjure2/ (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/type_erasure/ (props changed)
branches/release/libs/type_traits/ (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/doc/ (props changed)
branches/release/libs/utility/doc/explicit_operator_bool.qbk (props changed)
branches/release/libs/utility/doc/string_ref.qbk (props changed)
branches/release/libs/utility/identity_type/ (props changed)
branches/release/libs/utility/in_place_factories.html (props changed)
branches/release/libs/utility/index.html (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/test/explicit_operator_bool.cpp (props changed)
branches/release/libs/utility/test/explicit_operator_bool_compile_fail_conv_int.cpp (props changed)
branches/release/libs/utility/test/explicit_operator_bool_compile_fail_conv_pvoid.cpp (props changed)
branches/release/libs/utility/test/explicit_operator_bool_compile_fail_delete.cpp (props changed)
branches/release/libs/utility/test/explicit_operator_bool_compile_fail_shift.cpp (props changed)
branches/release/libs/utility/test/result_of_test.cpp (props changed)
branches/release/libs/utility/test/string_ref_test2.cpp (props changed)
branches/release/libs/utility/test/string_ref_test_io.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/auto_index/ (props changed)
branches/release/tools/bcp/ (props changed)
branches/release/tools/boostbook/ (props changed)
branches/release/tools/build/ (props changed)
branches/release/tools/build/v2/ (props changed)
branches/release/tools/inspect/ (props changed)
branches/release/tools/inspect/build/Jamfile.v2 (props changed)
branches/release/tools/inspect/deprecated_macro_check.cpp (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/bellman_ford_shortest_paths.hpp | 2
branches/release/boost/graph/betweenness_centrality.hpp | 3
branches/release/boost/graph/bipartite.hpp | 1
branches/release/boost/graph/breadth_first_search.hpp | 19 +-
branches/release/boost/graph/chrobak_payne_drawing.hpp | 1
branches/release/boost/graph/closeness_centrality.hpp | 2
branches/release/boost/graph/compressed_sparse_row_graph.hpp | 5
branches/release/boost/graph/connected_components.hpp | 2
branches/release/boost/graph/core_numbers.hpp | 1
branches/release/boost/graph/cuthill_mckee_ordering.hpp | 3
branches/release/boost/graph/cycle_canceling.hpp | 2
branches/release/boost/graph/depth_first_search.hpp | 66 +++++++--
branches/release/boost/graph/detail/adjacency_list.hpp | 1
branches/release/boost/graph/detail/augment.hpp | 63 +++++++++
branches/release/boost/graph/dijkstra_shortest_paths.hpp | 175 +++++++++++++++++++++++---
branches/release/boost/graph/dijkstra_shortest_paths_no_color_map.hpp | 2
branches/release/boost/graph/distributed/adjacency_list.hpp | 6
branches/release/boost/graph/distributed/adjlist/redistribute.hpp | 1
branches/release/boost/graph/distributed/adjlist/serialization.hpp | 5
branches/release/boost/graph/distributed/betweenness_centrality.hpp | 27 ----
branches/release/boost/graph/distributed/boman_et_al_graph_coloring.hpp | 1
branches/release/boost/graph/distributed/breadth_first_search.hpp | 3
branches/release/boost/graph/distributed/compressed_sparse_row_graph.hpp | 1
branches/release/boost/graph/distributed/concepts.hpp | 4
branches/release/boost/graph/distributed/connected_components.hpp | 6
branches/release/boost/graph/distributed/connected_components_parallel_search.hpp | 2
branches/release/boost/graph/distributed/crauser_et_al_shortest_paths.hpp | 7 -
branches/release/boost/graph/distributed/dehne_gotz_min_spanning_tree.hpp | 1
branches/release/boost/graph/distributed/eager_dijkstra_shortest_paths.hpp | 7 -
branches/release/boost/graph/distributed/graphviz.hpp | 2
branches/release/boost/graph/distributed/hohberg_biconnected_components.hpp | 2
branches/release/boost/graph/distributed/named_graph.hpp | 3
branches/release/boost/graph/distributed/page_rank.hpp | 2
branches/release/boost/graph/distributed/strong_components.hpp | 6
branches/release/boost/graph/edge_coloring.hpp | 196 +++++++++++++++++++++++++++++
branches/release/boost/graph/edmonds_karp_max_flow.hpp | 1
branches/release/boost/graph/find_flow_cost.hpp | 52 +++++++
branches/release/boost/graph/fruchterman_reingold.hpp | 1
branches/release/boost/graph/graph_traits.hpp | 8 +
branches/release/boost/graph/graph_utility.hpp | 4
branches/release/boost/graph/gursoy_atun_layout.hpp | 4
branches/release/boost/graph/hawick_circuits.hpp | 4
branches/release/boost/graph/is_straight_line_drawing.hpp | 3
branches/release/boost/graph/king_ordering.hpp | 5
branches/release/boost/graph/kruskal_min_spanning_tree.hpp | 1
branches/release/boost/graph/maximum_adjacency_search.hpp | 4
branches/release/boost/graph/mcgregor_common_subgraphs.hpp | 1
branches/release/boost/graph/metric_tsp_approx.hpp | 1
branches/release/boost/graph/named_function_params.hpp | 1
branches/release/boost/graph/planar_canonical_ordering.hpp | 2
branches/release/boost/graph/r_c_shortest_paths.hpp | 33 ++--
branches/release/boost/graph/random.hpp | 2
branches/release/boost/graph/random_spanning_tree.hpp | 1
branches/release/boost/graph/read_dimacs.hpp | 1
branches/release/boost/graph/stoer_wagner_min_cut.hpp | 8
branches/release/boost/graph/successive_shortest_path_nonnegative_weights.hpp | 261 +++++++++++++++++++++++++++++++++++++++
branches/release/boost/graph/tiernan_all_cycles.hpp | 1
branches/release/boost/graph/transitive_closure.hpp | 60 ++++----
branches/release/boost/graph/two_graphs_common_spanning_trees.hpp | 7 -
branches/release/boost/graph/undirected_dfs.hpp | 15 +
branches/release/boost/graph/vf2_sub_graph_iso.hpp | 4
branches/release/boost/graph/visitors.hpp | 3
branches/release/boost/graph/write_dimacs.hpp | 4
branches/release/boost/property_map/dynamic_property_map.hpp | 9 +
branches/release/boost/property_map/property_map.hpp | 3
branches/release/libs/graph/build/Jamfile.v2 | 1
branches/release/libs/graph/doc/DFSVisitor.html | 9 +
branches/release/libs/graph/doc/cycle_canceling.html | 6
branches/release/libs/graph/doc/depth_first_search.html | 6
branches/release/libs/graph/doc/dijkstra_shortest_paths_no_color_map.html | 10
branches/release/libs/graph/doc/edge_coloring.html | 98 ++++++++++++++
branches/release/libs/graph/doc/find_flow_cost.html | 10
branches/release/libs/graph/doc/graph_theory_review.html | 3
branches/release/libs/graph/doc/hawick_circuits.html | 58 ++++++++
branches/release/libs/graph/doc/hawick_circuits.md | 53 ++++++++
branches/release/libs/graph/doc/successive_shortest_path_nonnegative_weights.html | 264 ++++++++++++++++++++++++++++++++++++++++
branches/release/libs/graph/doc/table_of_contents.html | 16 +
branches/release/libs/graph/doc/undirected_dfs.html | 8 +
branches/release/libs/graph/example/Jamfile.v2 | 4
branches/release/libs/graph/example/astar-cities.cpp | 4
branches/release/libs/graph/example/bfs-example.cpp | 11 +
branches/release/libs/graph/example/bfs-example2.cpp | 19 ++
branches/release/libs/graph/example/canonical_ordering.cpp | 8
branches/release/libs/graph/example/cycle_canceling_example.cpp | 15 +
branches/release/libs/graph/example/dfs-example.cpp | 16 +-
branches/release/libs/graph/example/dfs.cpp | 12 +
branches/release/libs/graph/example/dfs.expected | 6
branches/release/libs/graph/example/dijkstra-example-listS.cpp | 1
branches/release/libs/graph/example/dijkstra-example.cpp | 1
branches/release/libs/graph/example/dijkstra-no-color-map-example.cpp | 1
branches/release/libs/graph/example/edge_coloring.cpp | 70 ++++++++++
branches/release/libs/graph/example/hawick_circuits.cpp | 96 ++++++++++++++
branches/release/libs/graph/example/implicit_graph.cpp | 10 +
branches/release/libs/graph/example/mcgregor_subgraphs_example.cpp | 4
branches/release/libs/graph/example/stoer_wagner.cpp | 1
branches/release/libs/graph/example/subgraph.cpp | 1
branches/release/libs/graph/example/successive_shortest_path_nonnegative_weights_example.cpp | 6
branches/release/libs/graph/test/Jamfile.v2 | 5
branches/release/libs/graph/test/adj_list_loops.cpp | 4
branches/release/libs/graph/test/all_planar_input_files_test.cpp | 2
branches/release/libs/graph/test/astar_search_test.cpp | 8
branches/release/libs/graph/test/bellman-test.cpp | 10
branches/release/libs/graph/test/bfs.cpp | 28 +++
branches/release/libs/graph/test/boykov_kolmogorov_max_flow_test.cpp | 3
branches/release/libs/graph/test/closeness_centrality.cpp | 2
branches/release/libs/graph/test/clustering_coefficient.cpp | 4
branches/release/libs/graph/test/cycle_canceling_test.cpp | 30 +++-
branches/release/libs/graph/test/cycle_ratio_tests.cpp | 1
branches/release/libs/graph/test/cycle_test.hpp | 2
branches/release/libs/graph/test/degree_centrality.cpp | 2
branches/release/libs/graph/test/dfs.cpp | 31 +++
branches/release/libs/graph/test/dijkstra_heap_performance.cpp | 10 +
branches/release/libs/graph/test/dijkstra_no_color_map_compare.cpp | 3
branches/release/libs/graph/test/eccentricity.cpp | 2
branches/release/libs/graph/test/graphviz_test.cpp | 3
branches/release/libs/graph/test/hawick_circuits.cpp | 32 ++++
branches/release/libs/graph/test/index_graph.cpp | 1
branches/release/libs/graph/test/layout_test.cpp | 2
branches/release/libs/graph/test/make_connected_test.cpp | 16 +
branches/release/libs/graph/test/matching_test.cpp | 1
branches/release/libs/graph/test/mcgregor_subgraphs_test.cpp | 7 -
branches/release/libs/graph/test/mean_geodesic.cpp | 2
branches/release/libs/graph/test/metric_tsp_approx.cpp | 2
branches/release/libs/graph/test/min_cost_max_flow_utils.hpp | 66 +++++----
branches/release/libs/graph/test/parallel_edges_loops_test.cpp | 2
branches/release/libs/graph/test/property_iter.cpp | 10 -
branches/release/libs/graph/test/rcsp_custom_vertex_id.cpp | 5
branches/release/libs/graph/test/sequential_vertex_coloring.cpp | 1
branches/release/libs/graph/test/stoer_wagner_test.cpp | 16 --
branches/release/libs/graph/test/subgraph.cpp | 1
branches/release/libs/graph/test/successive_shortest_path_nonnegative_weights_test.cpp | 27 ++-
branches/release/libs/graph/test/test_properties.hpp | 3
branches/release/libs/graph/test/tiernan_all_cycles.cpp | 2
branches/release/libs/graph/test/transitive_closure_test.cpp | 10
branches/release/libs/graph/test/undirected_dfs.cpp | 25 +++
branches/release/libs/graph_parallel/test/adjlist_redist_test.cpp | 1
branches/release/libs/graph_parallel/test/adjlist_remove_test.cpp | 1
branches/release/libs/graph_parallel/test/distributed_betweenness_centrality_test.cpp | 3
branches/release/libs/graph_parallel/test/distributed_connected_components_test.cpp | 5
branches/release/libs/graph_parallel/test/distributed_csr_algorithm_test.cpp | 1
branches/release/libs/graph_parallel/test/distributed_csr_test.cpp | 4
branches/release/libs/graph_parallel/test/distributed_dfs_test.cpp | 1
branches/release/libs/graph_parallel/test/distributed_graph_coloring_test.cpp | 2
branches/release/libs/graph_parallel/test/distributed_mst_test.cpp | 2
branches/release/libs/graph_parallel/test/distributed_shortest_paths_test.cpp | 3
branches/release/libs/graph_parallel/test/distributed_st_connected_test.cpp | 2
branches/release/libs/graph_parallel/test/distributed_strong_components_test.cpp | 5
branches/release/libs/property_map/test/property_map_cc.cpp | 1
148 files changed, 1877 insertions(+), 497 deletions(-)
Modified: branches/release/boost/graph/bellman_ford_shortest_paths.hpp
==============================================================================
--- branches/release/boost/graph/bellman_ford_shortest_paths.hpp Sat Sep 21 15:26:42 2013 (r85812)
+++ branches/release/boost/graph/bellman_ford_shortest_paths.hpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -102,8 +102,6 @@
typedef typename GTraits::vertex_descriptor Vertex;
BOOST_CONCEPT_ASSERT(( ReadWritePropertyMapConcept<DistanceMap, Vertex> ));
BOOST_CONCEPT_ASSERT(( ReadablePropertyMapConcept<WeightMap, Edge> ));
- typedef typename property_traits<DistanceMap>::value_type D_value;
- typedef typename property_traits<WeightMap>::value_type W_value;
typename GTraits::edge_iterator i, end;
Modified: branches/release/boost/graph/betweenness_centrality.hpp
==============================================================================
--- branches/release/boost/graph/betweenness_centrality.hpp Sat Sep 21 15:26:42 2013 (r85812)
+++ branches/release/boost/graph/betweenness_centrality.hpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -296,7 +296,6 @@
ShortestPaths shortest_paths)
{
typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator;
- typedef typename graph_traits<Graph>::edge_iterator edge_iterator;
typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
// Initialize centrality
@@ -421,7 +420,6 @@
VertexIndexMap vertex_index)
{
typedef typename graph_traits<Graph>::degree_size_type degree_size_type;
- typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor;
typedef typename mpl::if_c<(is_same<CentralityMap,
dummy_property_map>::value),
@@ -457,7 +455,6 @@
VertexIndexMap vertex_index)
{
typedef typename graph_traits<Graph>::degree_size_type degree_size_type;
- typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor;
typedef typename mpl::if_c<(is_same<CentralityMap,
dummy_property_map>::value),
Modified: branches/release/boost/graph/bipartite.hpp
==============================================================================
--- branches/release/boost/graph/bipartite.hpp Sat Sep 21 15:26:42 2013 (r85812)
+++ branches/release/boost/graph/bipartite.hpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -198,7 +198,6 @@
/// General types and variables
typedef typename property_traits <PartitionMap>::value_type partition_color_t;
typedef typename graph_traits <Graph>::vertex_descriptor vertex_descriptor_t;
- typedef typename graph_traits <Graph>::vertex_iterator vertex_iterator_t;
/// Declare dfs visitor
// detail::empty_recorder recorder;
Modified: branches/release/boost/graph/breadth_first_search.hpp
==============================================================================
--- branches/release/boost/graph/breadth_first_search.hpp Sat Sep 21 15:26:42 2013 (r85812)
+++ branches/release/boost/graph/breadth_first_search.hpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -64,7 +64,6 @@
BOOST_CONCEPT_ASSERT(( IncidenceGraphConcept<IncidenceGraph> ));
typedef graph_traits<IncidenceGraph> GTraits;
typedef typename GTraits::vertex_descriptor Vertex;
- typedef typename GTraits::edge_descriptor Edge;
BOOST_CONCEPT_ASSERT(( BFSVisitorConcept<BFSVisitor, IncidenceGraph> ));
BOOST_CONCEPT_ASSERT(( ReadWritePropertyMapConcept<ColorMap, Vertex> ));
typedef typename property_traits<ColorMap>::value_type ColorValue;
@@ -248,8 +247,7 @@
ColorMap color,
BFSVisitor vis,
const bgl_named_params<P, T, R>& params,
- BOOST_GRAPH_ENABLE_IF_MODELS(VertexListGraph, vertex_list_graph_tag,
- void)* = 0)
+ boost::mpl::false_)
{
typedef graph_traits<VertexListGraph> Traits;
// Buffer default
@@ -271,8 +269,7 @@
ColorMap color,
BFSVisitor vis,
const bgl_named_params<P, T, R>& params,
- BOOST_GRAPH_ENABLE_IF_MODELS(DistributedGraph, distributed_graph_tag,
- void)* = 0);
+ boost::mpl::true_);
#endif // BOOST_GRAPH_USE_MPI
//-------------------------------------------------------------------------
@@ -293,7 +290,11 @@
(g, s, color,
choose_param(get_param(params, graph_visitor),
make_bfs_visitor(null_visitor())),
- params);
+ params,
+ boost::mpl::bool_<
+ boost::is_base_and_derived<
+ distributed_graph_tag,
+ typename graph_traits<VertexListGraph>::traversal_category>::value>());
}
};
@@ -316,7 +317,11 @@
g, vertex_index)),
choose_param(get_param(params, graph_visitor),
make_bfs_visitor(null_vis)),
- params);
+ params,
+ boost::mpl::bool_<
+ boost::is_base_and_derived<
+ distributed_graph_tag,
+ typename graph_traits<VertexListGraph>::traversal_category>::value>());
}
};
Modified: branches/release/boost/graph/chrobak_payne_drawing.hpp
==============================================================================
--- branches/release/boost/graph/chrobak_payne_drawing.hpp Sat Sep 21 15:26:42 2013 (r85812)
+++ branches/release/boost/graph/chrobak_payne_drawing.hpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -73,7 +73,6 @@
{
typedef typename graph_traits<Graph>::vertex_descriptor vertex_t;
- typedef typename graph_traits<Graph>::edge_descriptor edge_t;
typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator_t;
typedef typename PlanarEmbedding::value_type::const_iterator
edge_permutation_iterator_t;
Modified: branches/release/boost/graph/closeness_centrality.hpp
==============================================================================
--- branches/release/boost/graph/closeness_centrality.hpp Sat Sep 21 15:26:42 2013 (r85812)
+++ branches/release/boost/graph/closeness_centrality.hpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -123,7 +123,6 @@
typedef typename property_traits<DistanceMatrixMap>::value_type DistanceMap;
BOOST_CONCEPT_ASSERT(( ReadablePropertyMapConcept<DistanceMap,Vertex> ));
BOOST_CONCEPT_ASSERT(( WritablePropertyMapConcept<CentralityMap,Vertex> ));
- typedef typename property_traits<DistanceMap>::value_type Distance;
typedef typename property_traits<CentralityMap>::value_type Centrality;
typename graph_traits<Graph>::vertex_iterator i, end;
@@ -147,7 +146,6 @@
BOOST_CONCEPT_ASSERT(( ReadablePropertyMapConcept<DistanceMatrixMap,Vertex> ));
typedef typename property_traits<DistanceMatrixMap>::value_type DistanceMap;
BOOST_CONCEPT_ASSERT(( ReadablePropertyMapConcept<DistanceMap,Vertex> ));
- typedef typename property_traits<DistanceMap>::value_type Distance;
typedef typename property_traits<CentralityMap>::value_type Result;
all_closeness_centralities(g, dist, cent, measure_closeness<Result>(g, DistanceMap()));
Modified: branches/release/boost/graph/compressed_sparse_row_graph.hpp
==============================================================================
--- branches/release/boost/graph/compressed_sparse_row_graph.hpp Sat Sep 21 15:26:42 2013 (r85812)
+++ branches/release/boost/graph/compressed_sparse_row_graph.hpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -192,6 +192,11 @@
VertexProperty, Vertex, typed_identity_property_map<Vertex> >
inherited_vertex_properties;
+ // Some tests to prevent use of "void" is a property type (as was done in some test cases):
+ BOOST_STATIC_ASSERT((!is_same<VertexProperty, void>::value));
+ BOOST_STATIC_ASSERT((!is_same<EdgeProperty, void>::value));
+ BOOST_STATIC_ASSERT((!is_same<GraphProperty, void>::value));
+
public:
// For Property Graph
typedef GraphProperty graph_property_type;
Modified: branches/release/boost/graph/connected_components.hpp
==============================================================================
--- branches/release/boost/graph/connected_components.hpp Sat Sep 21 15:26:42 2013 (r85812)
+++ branches/release/boost/graph/connected_components.hpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -86,7 +86,7 @@
typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
BOOST_CONCEPT_ASSERT(( WritablePropertyMapConcept<ComponentMap, Vertex> ));
- typedef typename boost::graph_traits<Graph>::directed_category directed;
+ // typedef typename boost::graph_traits<Graph>::directed_category directed;
// BOOST_STATIC_ASSERT((boost::is_same<directed, undirected_tag>::value));
typedef typename property_traits<ComponentMap>::value_type comp_type;
Modified: branches/release/boost/graph/core_numbers.hpp
==============================================================================
--- branches/release/boost/graph/core_numbers.hpp Sat Sep 21 15:26:42 2013 (r85812)
+++ branches/release/boost/graph/core_numbers.hpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -316,7 +316,6 @@
core_numbers(Graph& g, CoreMap c, EdgeWeightMap wm, VertexIndexMap vim,
CoreNumVisitor vis)
{
- typedef typename graph_traits<Graph>::vertices_size_type size_type;
detail::compute_in_degree_map(g,c,wm);
return detail::core_numbers_dispatch(g,c,wm,vim,vis);
}
Modified: branches/release/boost/graph/cuthill_mckee_ordering.hpp
==============================================================================
--- branches/release/boost/graph/cuthill_mckee_ordering.hpp Sat Sep 21 15:26:42 2013 (r85812)
+++ branches/release/boost/graph/cuthill_mckee_ordering.hpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -75,7 +75,6 @@
{
//create queue, visitor...don't forget namespaces!
- typedef typename property_traits<DegreeMap>::value_type ds_type;
typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
typedef typename boost::sparse::sparse_ordering_queue<Vertex> queue;
typedef typename detail::bfs_rcm_visitor<OutputIterator, queue, DegreeMap> Visitor;
@@ -137,7 +136,6 @@
return permutation;
typedef typename boost::graph_traits<Graph>::vertex_descriptor Vertex;
- typedef typename boost::graph_traits<Graph>::vertex_iterator VerIter;
typedef typename property_traits<ColorMap>::value_type ColorValue;
typedef color_traits<ColorValue> Color;
@@ -172,7 +170,6 @@
if (boost::graph::has_no_vertices(G))
return permutation;
- typedef out_degree_property_map<Graph> DegreeMap;
std::vector<default_color_type> colors(num_vertices(G));
return cuthill_mckee_ordering(G, permutation,
make_iterator_property_map(&colors[0],
Copied and modified: branches/release/boost/graph/cycle_canceling.hpp (from r85536, trunk/boost/graph/cycle_canceling.hpp)
==============================================================================
--- trunk/boost/graph/cycle_canceling.hpp Sat Aug 31 16:09:11 2013 (r85536, copy source)
+++ branches/release/boost/graph/cycle_canceling.hpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -92,7 +92,7 @@
}
-//in this namespace argument dispatching tak place
+//in this namespace argument dispatching takes place
namespace detail {
template <class Graph, class P, class T, class R, class ResidualCapacity, class Weight, class Reversed, class Pred, class Distance>
Modified: branches/release/boost/graph/depth_first_search.hpp
==============================================================================
--- branches/release/boost/graph/depth_first_search.hpp Sat Sep 21 15:26:42 2013 (r85812)
+++ branches/release/boost/graph/depth_first_search.hpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -21,8 +21,10 @@
#include <boost/graph/named_function_params.hpp>
#include <boost/ref.hpp>
#include <boost/implicit_cast.hpp>
+#include <boost/optional.hpp>
#include <boost/parameter.hpp>
#include <boost/concept/assert.hpp>
+#include <boost/tti/has_member_function.hpp>
#include <vector>
#include <utility>
@@ -41,6 +43,7 @@
vis.tree_edge(e, g);
vis.back_edge(e, g);
vis.forward_or_cross_edge(e, g);
+ // vis.finish_edge(e, g); // Optional for user
vis.finish_vertex(u, g);
}
private:
@@ -57,6 +60,25 @@
bool operator()(const T&, const T2&) const { return false; }
};
+ BOOST_TTI_HAS_MEMBER_FUNCTION(finish_edge)
+
+ template <bool IsCallable> struct do_call_finish_edge {
+ template <typename E, typename G, typename Vis>
+ static void call_finish_edge(Vis& vis, const E& e, const G& g) {
+ vis.finish_edge(e, g);
+ }
+ };
+
+ template <> struct do_call_finish_edge<false> {
+ template <typename E, typename G, typename Vis>
+ static void call_finish_edge(Vis&, const E&, const G&) {}
+ };
+
+ template <typename E, typename G, typename Vis>
+ void call_finish_edge(Vis& vis, const E& e, const G& g) { // Only call if method exists
+ do_call_finish_edge<has_member_function_finish_edge<Vis, void>::value>::call_finish_edge(vis, e, g);
+ }
+
// Define BOOST_RECURSIVE_DFS to use older, recursive version.
// It is retained for a while in order to perform performance
@@ -85,36 +107,35 @@
BOOST_CONCEPT_ASSERT(( IncidenceGraphConcept<IncidenceGraph> ));
BOOST_CONCEPT_ASSERT(( DFSVisitorConcept<DFSVisitor, IncidenceGraph> ));
typedef typename graph_traits<IncidenceGraph>::vertex_descriptor Vertex;
+ typedef typename graph_traits<IncidenceGraph>::edge_descriptor Edge;
BOOST_CONCEPT_ASSERT(( ReadWritePropertyMapConcept<ColorMap, Vertex> ));
typedef typename property_traits<ColorMap>::value_type ColorValue;
BOOST_CONCEPT_ASSERT(( ColorValueConcept<ColorValue> ));
typedef color_traits<ColorValue> Color;
typedef typename graph_traits<IncidenceGraph>::out_edge_iterator Iter;
- typedef std::pair<Vertex, std::pair<Iter, Iter> > VertexInfo;
+ typedef std::pair<Vertex, std::pair<boost::optional<Edge>, std::pair<Iter, Iter> > > VertexInfo;
+ boost::optional<Edge> src_e;
Iter ei, ei_end;
std::vector<VertexInfo> stack;
// Possible optimization for vector
//stack.reserve(num_vertices(g));
- typedef typename unwrap_reference<TerminatorFunc>::type TF;
-
put(color, u, Color::gray());
vis.discover_vertex(u, g);
boost::tie(ei, ei_end) = out_edges(u, g);
- // Variable is needed to workaround a borland bug.
- TF& fn = static_cast<TF&>(func);
- if (fn(u, g)) {
+ if (func(u, g)) {
// If this vertex terminates the search, we push empty range
- stack.push_back(std::make_pair(u, std::make_pair(ei_end, ei_end)));
+ stack.push_back(std::make_pair(u, std::make_pair(boost::optional<Edge>(), std::make_pair(ei_end, ei_end))));
} else {
- stack.push_back(std::make_pair(u, std::make_pair(ei, ei_end)));
+ stack.push_back(std::make_pair(u, std::make_pair(boost::optional<Edge>(), std::make_pair(ei, ei_end))));
}
while (!stack.empty()) {
VertexInfo& back = stack.back();
u = back.first;
- boost::tie(ei, ei_end) = back.second;
+ src_e = back.second.first;
+ boost::tie(ei, ei_end) = back.second.second;
stack.pop_back();
while (ei != ei_end) {
Vertex v = target(*ei, g);
@@ -122,24 +143,28 @@
ColorValue v_color = get(color, v);
if (v_color == Color::white()) {
vis.tree_edge(*ei, g);
- stack.push_back(std::make_pair(u, std::make_pair(++ei, ei_end)));
+ src_e = *ei;
+ stack.push_back(std::make_pair(u, std::make_pair(src_e, std::make_pair(++ei, ei_end))));
u = v;
put(color, u, Color::gray());
vis.discover_vertex(u, g);
boost::tie(ei, ei_end) = out_edges(u, g);
- if (fn(u, g)) {
+ if (func(u, g)) {
ei = ei_end;
}
- } else if (v_color == Color::gray()) {
- vis.back_edge(*ei, g);
- ++ei;
} else {
- vis.forward_or_cross_edge(*ei, g);
+ if (v_color == Color::gray()) {
+ vis.back_edge(*ei, g);
+ } else {
+ vis.forward_or_cross_edge(*ei, g);
+ }
+ call_finish_edge(vis, *ei, g);
++ei;
}
}
put(color, u, Color::black());
vis.finish_vertex(u, g);
+ if (src_e) call_finish_edge(vis, src_e.get(), g);
}
}
@@ -164,10 +189,7 @@
put(color, u, Color::gray()); vis.discover_vertex(u, g);
- typedef typename unwrap_reference<TerminatorFunc>::type TF;
- // Variable is needed to workaround a borland bug.
- TF& fn = static_cast<TF&>(func);
- if (!fn(u, g))
+ if (!func(u, g))
for (boost::tie(ei, ei_end) = out_edges(u, g); ei != ei_end; ++ei) {
Vertex v = target(*ei, g); vis.examine_edge(*ei, g);
ColorValue v_color = get(color, v);
@@ -175,6 +197,7 @@
depth_first_visit_impl(g, v, vis, color, func);
} else if (v_color == Color::gray()) vis.back_edge(*ei, g);
else vis.forward_or_cross_edge(*ei, g);
+ call_finish_edge(vis, *ei, g);
}
put(color, u, Color::black()); vis.finish_vertex(u, g);
}
@@ -259,6 +282,10 @@
void forward_or_cross_edge(Edge u, const Graph& g) {
invoke_visitors(m_vis, u, g, ::boost::on_forward_or_cross_edge());
}
+ template <class Edge, class Graph>
+ void finish_edge(Edge u, const Graph& g) {
+ invoke_visitors(m_vis, u, g, ::boost::on_finish_edge());
+ }
template <class Vertex, class Graph>
void finish_vertex(Vertex u, const Graph& g) {
invoke_visitors(m_vis, u, g, ::boost::on_finish_vertex());
@@ -271,6 +298,7 @@
BOOST_GRAPH_EVENT_STUB(on_tree_edge,dfs)
BOOST_GRAPH_EVENT_STUB(on_back_edge,dfs)
BOOST_GRAPH_EVENT_STUB(on_forward_or_cross_edge,dfs)
+ BOOST_GRAPH_EVENT_STUB(on_finish_edge,dfs)
BOOST_GRAPH_EVENT_STUB(on_finish_vertex,dfs)
protected:
Modified: branches/release/boost/graph/detail/adjacency_list.hpp
==============================================================================
--- branches/release/boost/graph/detail/adjacency_list.hpp Sat Sep 21 15:26:42 2013 (r85812)
+++ branches/release/boost/graph/detail/adjacency_list.hpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -806,7 +806,6 @@
typedef typename EdgeList::value_type StoredEdge;
typename EdgeList::iterator i = el.find(StoredEdge(v)), end = el.end();
- BOOST_ASSERT ((i != end));
if (i != end) {
g.m_edges.erase((*i).get_iter());
el.erase(i);
Copied: branches/release/boost/graph/detail/augment.hpp (from r85536, trunk/boost/graph/detail/augment.hpp)
==============================================================================
--- /dev/null 00:00:00 1970 (empty, because file is newly added)
+++ branches/release/boost/graph/detail/augment.hpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813, copy of r85536, trunk/boost/graph/detail/augment.hpp)
@@ -0,0 +1,63 @@
+//=======================================================================
+// Copyright 2013 University of Warsaw.
+// Authors: Piotr Wygocki
+//
+// 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_AUGMENT_HPP
+#define BOOST_GRAPH_AUGMENT_HPP
+
+#include <boost/graph/filtered_graph.hpp>
+
+namespace boost {
+namespace detail {
+
+template <class Graph, class ResCapMap>
+filtered_graph<const Graph, is_residual_edge<ResCapMap> >
+residual_graph(const Graph& g, ResCapMap residual_capacity) {
+ return filtered_graph<const Graph, is_residual_edge<ResCapMap> >
+ (g, is_residual_edge<ResCapMap>(residual_capacity));
+}
+
+template <class Graph, class PredEdgeMap, class ResCapMap,
+ class RevEdgeMap>
+inline void
+augment(const Graph& g,
+ typename graph_traits<Graph>::vertex_descriptor src,
+ typename graph_traits<Graph>::vertex_descriptor sink,
+ PredEdgeMap p,
+ ResCapMap residual_capacity,
+ RevEdgeMap reverse_edge)
+{
+ typename graph_traits<Graph>::edge_descriptor e;
+ typename graph_traits<Graph>::vertex_descriptor u;
+ typedef typename property_traits<ResCapMap>::value_type FlowValue;
+
+ // find minimum residual capacity along the augmenting path
+ FlowValue delta = (std::numeric_limits<FlowValue>::max)();
+ e = get(p, sink);
+ do {
+ BOOST_USING_STD_MIN();
+ delta = min BOOST_PREVENT_MACRO_SUBSTITUTION(delta, get(residual_capacity, e));
+ u = source(e, g);
+ e = get(p, u);
+ } while (u != src);
+
+ // push delta units of flow along the augmenting path
+ e = get(p, sink);
+ do {
+ put(residual_capacity, e, get(residual_capacity, e) - delta);
+ put(residual_capacity, get(reverse_edge, e), get(residual_capacity, get(reverse_edge, e)) + delta);
+ u = source(e, g);
+ e = get(p, u);
+ } while (u != src);
+}
+
+} // namespace detail
+} //namespace boost
+
+#endif /* BOOST_GRAPH_AUGMENT_HPP */
+
Modified: branches/release/boost/graph/dijkstra_shortest_paths.hpp
==============================================================================
--- branches/release/boost/graph/dijkstra_shortest_paths.hpp Sat Sep 21 15:26:42 2013 (r85812)
+++ branches/release/boost/graph/dijkstra_shortest_paths.hpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -118,6 +118,7 @@
struct dijkstra_bfs_visitor
{
typedef typename property_traits<DistanceMap>::value_type D;
+ typedef typename property_traits<WeightMap>::value_type W;
dijkstra_bfs_visitor(UniformCostVisitor vis, UpdatableQueue& Q,
WeightMap w, PredecessorMap p, DistanceMap d,
@@ -159,13 +160,39 @@
void examine_vertex(Vertex u, Graph& g) { m_vis.examine_vertex(u, g); }
template <class Edge, class Graph>
void examine_edge(Edge e, Graph& g) {
- // Comparison needs to be more complicated because distance and weight
- // types may not be the same; see bug 8398
- // (https://svn.boost.org/trac/boost/ticket/8398)
- D source_dist = get(m_distance, source(e, g));
- if (m_compare(m_combine(source_dist, get(m_weight, e)), source_dist))
+ // Test for negative-weight edges:
+ //
+ // Reasons that other comparisons do not work:
+ //
+ // m_compare(e_weight, D(0)):
+ // m_compare only needs to work on distances, not weights, and those
+ // types do not need to be the same (bug 8398,
+ // https://svn.boost.org/trac/boost/ticket/8398).
+ // m_compare(m_combine(source_dist, e_weight), source_dist):
+ // if m_combine is project2nd (as in prim_minimum_spanning_tree),
+ // this test will claim that the edge weight is negative whenever
+ // the edge weight is less than source_dist, even if both of those
+ // are positive (bug 9012,
+ // https://svn.boost.org/trac/boost/ticket/9012).
+ // m_compare(m_combine(e_weight, source_dist), source_dist):
+ // would fix project2nd issue, but documentation only requires that
+ // m_combine be able to take a distance and a weight (in that order)
+ // and return a distance.
+
+ // W e_weight = get(m_weight, e);
+ // sd_plus_ew = source_dist + e_weight.
+ // D sd_plus_ew = m_combine(source_dist, e_weight);
+ // sd_plus_2ew = source_dist + 2 * e_weight.
+ // D sd_plus_2ew = m_combine(sd_plus_ew, e_weight);
+ // The test here is equivalent to e_weight < 0 if m_combine has a
+ // cancellation law, but always returns false when m_combine is a
+ // projection operator.
+ if (m_compare(m_combine(m_zero, get(m_weight, e)), m_zero))
boost::throw_exception(negative_edge());
+ // End of test for negative-weight edges.
+
m_vis.examine_edge(e, g);
+
}
template <class Edge, class Graph>
void black_target(Edge, Graph&) { }
@@ -256,14 +283,14 @@
}
// Call breadth first search with default color map.
- template <class Graph, class DijkstraVisitor,
+ template <class Graph, class SourceInputIter, class DijkstraVisitor,
class PredecessorMap, class DistanceMap,
class WeightMap, class IndexMap, class Compare, class Combine,
class DistZero>
inline void
dijkstra_shortest_paths_no_init
(const Graph& g,
- typename graph_traits<Graph>::vertex_descriptor s,
+ SourceInputIter s_begin, SourceInputIter s_end,
PredecessorMap predecessor, DistanceMap distance, WeightMap weight,
IndexMap index_map,
Compare compare, Combine combine, DistZero zero,
@@ -275,16 +302,16 @@
typedef typename ColorMapHelper::type ColorMap;
ColorMap color =
ColorMapHelper::build(g, index_map);
- dijkstra_shortest_paths_no_init( g, s, predecessor, distance, weight,
+ dijkstra_shortest_paths_no_init( g, s_begin, s_end, predecessor, distance, weight,
index_map, compare, combine, zero, vis,
color);
}
- // Call breadth first search
+ // Call breadth first search with default color map.
template <class Graph, class DijkstraVisitor,
class PredecessorMap, class DistanceMap,
class WeightMap, class IndexMap, class Compare, class Combine,
- class DistZero, class ColorMap>
+ class DistZero>
inline void
dijkstra_shortest_paths_no_init
(const Graph& g,
@@ -292,6 +319,25 @@
PredecessorMap predecessor, DistanceMap distance, WeightMap weight,
IndexMap index_map,
Compare compare, Combine combine, DistZero zero,
+ DijkstraVisitor vis)
+ {
+ dijkstra_shortest_paths_no_init(g, &s, &s + 1, predecessor, distance,
+ weight, index_map, compare, combine, zero,
+ vis);
+ }
+
+ // Call breadth first search
+ template <class Graph, class SourceInputIter, class DijkstraVisitor,
+ class PredecessorMap, class DistanceMap,
+ class WeightMap, class IndexMap, class Compare, class Combine,
+ class DistZero, class ColorMap>
+ inline void
+ dijkstra_shortest_paths_no_init
+ (const Graph& g,
+ SourceInputIter s_begin, SourceInputIter s_end,
+ PredecessorMap predecessor, DistanceMap distance, WeightMap weight,
+ IndexMap index_map,
+ Compare compare, Combine combine, DistZero zero,
DijkstraVisitor vis, ColorMap color)
{
typedef indirect_cmp<DistanceMap, Compare> IndirectCmp;
@@ -309,7 +355,7 @@
PredecessorMap, DistanceMap, Combine, Compare>
bfs_vis(vis, Q, weight, predecessor, distance, combine, compare, zero);
- breadth_first_visit(g, s, Q, bfs_vis, color);
+ breadth_first_visit(g, s_begin, s_end, Q, bfs_vis, color);
return;
}
#endif // BOOST_GRAPH_DIJKSTRA_TESTING
@@ -334,11 +380,30 @@
PredecessorMap, DistanceMap, Combine, Compare>
bfs_vis(vis, Q, weight, predecessor, distance, combine, compare, zero);
- breadth_first_visit(g, s, Q, bfs_vis, color);
+ breadth_first_visit(g, s_begin, s_end, Q, bfs_vis, color);
+ }
+
+ // Call breadth first search
+ template <class Graph, class DijkstraVisitor,
+ class PredecessorMap, class DistanceMap,
+ class WeightMap, class IndexMap, class Compare, class Combine,
+ class DistZero, class ColorMap>
+ inline void
+ dijkstra_shortest_paths_no_init
+ (const Graph& g,
+ typename graph_traits<Graph>::vertex_descriptor s,
+ PredecessorMap predecessor, DistanceMap distance, WeightMap weight,
+ IndexMap index_map,
+ Compare compare, Combine combine, DistZero zero,
+ DijkstraVisitor vis, ColorMap color)
+ {
+ dijkstra_shortest_paths_no_init(g, &s, &s + 1, predecessor, distance,
+ weight, index_map, compare, combine,
+ zero, vis, color);
}
// Initialize distances and call breadth first search with default color map
- template <class VertexListGraph, class DijkstraVisitor,
+ template <class VertexListGraph, class SourceInputIter, class DijkstraVisitor,
class PredecessorMap, class DistanceMap,
class WeightMap, class IndexMap, class Compare, class Combine,
class DistInf, class DistZero, typename T, typename Tag,
@@ -346,7 +411,7 @@
inline void
dijkstra_shortest_paths
(const VertexListGraph& g,
- typename graph_traits<VertexListGraph>::vertex_descriptor s,
+ SourceInputIter s_begin, SourceInputIter s_end,
PredecessorMap predecessor, DistanceMap distance, WeightMap weight,
IndexMap index_map,
Compare compare, Combine combine, DistInf inf, DistZero zero,
@@ -355,16 +420,17 @@
BOOST_GRAPH_ENABLE_IF_MODELS_PARM(VertexListGraph,vertex_list_graph_tag))
{
boost::two_bit_color_map<IndexMap> color(num_vertices(g), index_map);
- dijkstra_shortest_paths(g, s, predecessor, distance, weight, index_map,
- compare, combine, inf, zero, vis,
+ dijkstra_shortest_paths(g, s_begin, s_end, predecessor, distance, weight,
+ index_map, compare, combine, inf, zero, vis,
color);
}
- // Initialize distances and call breadth first search
+ // Initialize distances and call breadth first search with default color map
template <class VertexListGraph, class DijkstraVisitor,
class PredecessorMap, class DistanceMap,
class WeightMap, class IndexMap, class Compare, class Combine,
- class DistInf, class DistZero, class ColorMap>
+ class DistInf, class DistZero, typename T, typename Tag,
+ typename Base>
inline void
dijkstra_shortest_paths
(const VertexListGraph& g,
@@ -372,6 +438,26 @@
PredecessorMap predecessor, DistanceMap distance, WeightMap weight,
IndexMap index_map,
Compare compare, Combine combine, DistInf inf, DistZero zero,
+ DijkstraVisitor vis,
+ const bgl_named_params<T, Tag, Base>&
+ BOOST_GRAPH_ENABLE_IF_MODELS_PARM(VertexListGraph,vertex_list_graph_tag))
+ {
+ dijkstra_shortest_paths(g, &s, &s + 1, predecessor, distance, weight,
+ index_map, compare, combine, inf, zero, vis);
+ }
+
+ // Initialize distances and call breadth first search
+ template <class VertexListGraph, class SourceInputIter, class DijkstraVisitor,
+ class PredecessorMap, class DistanceMap,
+ class WeightMap, class IndexMap, class Compare, class Combine,
+ class DistInf, class DistZero, class ColorMap>
+ inline void
+ dijkstra_shortest_paths
+ (const VertexListGraph& g,
+ SourceInputIter s_begin, SourceInputIter s_end,
+ PredecessorMap predecessor, DistanceMap distance, WeightMap weight,
+ IndexMap index_map,
+ Compare compare, Combine combine, DistInf inf, DistZero zero,
DijkstraVisitor vis, ColorMap color)
{
typedef typename property_traits<ColorMap>::value_type ColorValue;
@@ -383,17 +469,20 @@
put(predecessor, *ui, *ui);
put(color, *ui, Color::white());
}
- put(distance, s, zero);
+ for (SourceInputIter it = s_begin; it != s_end; ++it) {
+ put(distance, *it, zero);
+ }
- dijkstra_shortest_paths_no_init(g, s, predecessor, distance, weight,
- index_map, compare, combine, zero, vis, color);
+ dijkstra_shortest_paths_no_init(g, s_begin, s_end, predecessor, distance,
+ weight, index_map, compare, combine, zero, vis,
+ color);
}
// Initialize distances and call breadth first search
template <class VertexListGraph, class DijkstraVisitor,
class PredecessorMap, class DistanceMap,
class WeightMap, class IndexMap, class Compare, class Combine,
- class DistInf, class DistZero>
+ class DistInf, class DistZero, class ColorMap>
inline void
dijkstra_shortest_paths
(const VertexListGraph& g,
@@ -401,13 +490,53 @@
PredecessorMap predecessor, DistanceMap distance, WeightMap weight,
IndexMap index_map,
Compare compare, Combine combine, DistInf inf, DistZero zero,
+ DijkstraVisitor vis, ColorMap color)
+ {
+ dijkstra_shortest_paths(g, &s, &s + 1, predecessor, distance, weight,
+ index_map, compare, combine, inf, zero,
+ vis, color);
+ }
+
+ // Initialize distances and call breadth first search
+ template <class VertexListGraph, class SourceInputIter,
+ class DijkstraVisitor,
+ class PredecessorMap, class DistanceMap,
+ class WeightMap, class IndexMap, class Compare, class Combine,
+ class DistInf, class DistZero>
+ inline void
+ dijkstra_shortest_paths
+ (const VertexListGraph& g,
+ SourceInputIter s_begin, SourceInputIter s_end,
+ PredecessorMap predecessor, DistanceMap distance, WeightMap weight,
+ IndexMap index_map,
+ Compare compare, Combine combine, DistInf inf, DistZero zero,
DijkstraVisitor vis)
{
- dijkstra_shortest_paths(g, s, predecessor, distance, weight, index_map,
+ dijkstra_shortest_paths(g, s_begin, s_end, predecessor, distance,
+ weight, index_map,
compare, combine, inf, zero, vis,
no_named_parameters());
}
+ // Initialize distances and call breadth first search
+ template <class VertexListGraph, class DijkstraVisitor,
+ class PredecessorMap, class DistanceMap,
+ class WeightMap, class IndexMap, class Compare, class Combine,
+ class DistInf, class DistZero>
+ inline void
+ dijkstra_shortest_paths
+ (const VertexListGraph& g,
+ typename graph_traits<VertexListGraph>::vertex_descriptor s,
+ PredecessorMap predecessor, DistanceMap distance, WeightMap weight,
+ IndexMap index_map,
+ Compare compare, Combine combine, DistInf inf, DistZero zero,
+ DijkstraVisitor vis)
+ {
+ dijkstra_shortest_paths(g, &s, &s + 1, predecessor, distance,
+ weight, index_map,
+ compare, combine, inf, zero, vis);
+ }
+
namespace detail {
// Handle defaults for PredecessorMap and
Modified: branches/release/boost/graph/dijkstra_shortest_paths_no_color_map.hpp
==============================================================================
--- branches/release/boost/graph/dijkstra_shortest_paths_no_color_map.hpp Sat Sep 21 15:26:42 2013 (r85812)
+++ branches/release/boost/graph/dijkstra_shortest_paths_no_color_map.hpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -41,7 +41,6 @@
{
typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
typedef typename property_traits<DistanceMap>::value_type Distance;
- typedef typename property_traits<WeightMap>::value_type Weight;
typedef indirect_cmp<DistanceMap, DistanceCompare> DistanceIndirectCompare;
DistanceIndirectCompare
@@ -92,7 +91,6 @@
}
// Examine neighbors of min_vertex
- typedef typename graph_traits<Graph>::edge_descriptor Edge;
BGL_FORALL_OUTEDGES_T(min_vertex, current_edge, graph, Graph) {
visitor.examine_edge(current_edge, graph);
Modified: branches/release/boost/graph/distributed/adjacency_list.hpp
==============================================================================
--- branches/release/boost/graph/distributed/adjacency_list.hpp Sat Sep 21 15:26:42 2013 (r85812)
+++ branches/release/boost/graph/distributed/adjacency_list.hpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -2501,9 +2501,6 @@
std::pair<edge_descriptor, bool> result
= this->add_local_edge(property, directedS());
- typedef detail::parallel::stored_in_edge<local_edge_descriptor>
- stored_edge;
-
if (result.second) {
if (target.owner == self.processor()) {
// Edge is local, so add the new edge to the list
@@ -3046,8 +3043,6 @@
PBGL_DISTRIB_ADJLIST_TYPE& g)
{
typedef typename PBGL_DISTRIB_ADJLIST_TYPE
- ::vertex_descriptor vertex_descriptor;
- typedef typename PBGL_DISTRIB_ADJLIST_TYPE
::edge_descriptor edge_descriptor;
std::pair<edge_descriptor, bool> the_edge = edge(u, v, g);
if (the_edge.second) remove_edge(the_edge.first, g);
@@ -3777,7 +3772,6 @@
template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS>
void synchronize(const PBGL_DISTRIB_ADJLIST_TYPE& g)
{
- typedef PBGL_DISTRIB_ADJLIST_TYPE graph_type;
synchronize(g.process_group());
}
Modified: branches/release/boost/graph/distributed/adjlist/redistribute.hpp
==============================================================================
--- branches/release/boost/graph/distributed/adjlist/redistribute.hpp Sat Sep 21 15:26:42 2013 (r85812)
+++ branches/release/boost/graph/distributed/adjlist/redistribute.hpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -179,7 +179,6 @@
typedef detail::parallel::redistributed_descriptor<edge_descriptor,
edge_property_type>
redistributed_edge;
- typedef std::pair<vertices_size_type, edges_size_type> num_relocated_pair;
vertex_iterator vi, vi_end;
edge_iterator ei, ei_end;
Modified: branches/release/boost/graph/distributed/adjlist/serialization.hpp
==============================================================================
--- branches/release/boost/graph/distributed/adjlist/serialization.hpp Sat Sep 21 15:26:42 2013 (r85812)
+++ branches/release/boost/graph/distributed/adjlist/serialization.hpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -776,7 +776,6 @@
process_id_type id = g.processor();
- typedef std::pair<local_vertex_descriptor, vertex_descriptor> in_edge;
std::vector<edge_descriptor> saved_in_edges;
BGL_FORALL_VERTICES_T(v, g, Graph)
@@ -830,8 +829,6 @@
process_id_type;
typedef typename graph_traits<
Graph>::vertex_descriptor vertex_descriptor;
- typedef typename graph_traits<
- Graph>::edge_descriptor edge_descriptor;
typedef typename Graph::edge_property_type edge_property_type;
@@ -880,8 +877,6 @@
template <class IStreamConstructibleArchive>
void PBGL_DISTRIB_ADJLIST_TYPE::load(std::string const& filename)
{
- typedef typename config_type::VertexListS vertex_list_selector;
-
process_group_type pg = process_group();
process_id_type id = process_id(pg);
Modified: branches/release/boost/graph/distributed/betweenness_centrality.hpp
==============================================================================
--- branches/release/boost/graph/distributed/betweenness_centrality.hpp Sat Sep 21 15:26:42 2013 (r85812)
+++ branches/release/boost/graph/distributed/betweenness_centrality.hpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -621,12 +621,6 @@
#endif
)
{
- typedef typename property_traits<DistanceMap>::value_type
- distance_type;
-
- typedef std::plus<distance_type> Combine;
- typedef std::less<distance_type> Compare;
-
// The "distance" map needs to act like one, retrieving the default
// value of infinity.
set_property_map_role(vertex_distance, distance);
@@ -717,7 +711,6 @@
using boost::graph::parallel::process_group;
typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
- typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator;
typedef typename graph_traits<Graph>::edges_size_type edges_size_type;
typedef typename property_traits<IncomingMap>::value_type incoming_type;
@@ -974,10 +967,7 @@
using boost::detail::graph::divide_centrality_by_two;
using boost::graph::parallel::process_group;
- typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator;
- typedef typename graph_traits<Graph>::edge_iterator edge_iterator;
typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
- typedef typename graph_traits<Graph>::vertices_size_type vertices_size_type;
typedef typename property_traits<DistanceMap>::value_type distance_type;
typedef typename property_traits<DependencyMap>::value_type dependency_type;
@@ -1064,11 +1054,8 @@
{
using boost::detail::graph::update_centrality;
- typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator;
typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
- typedef typename property_traits<IncomingMap>::value_type incoming_type;
-
// Initialize for this iteration
BGL_FORALL_VERTICES_T(w, g, Graph) {
// put(path_count, w, 0);
@@ -1137,12 +1124,7 @@
using boost::detail::graph::divide_centrality_by_two;
using boost::graph::parallel::process_group;
- typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator;
- typedef typename graph_traits<Graph>::edge_iterator edge_iterator;
typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
- typedef typename graph_traits<Graph>::vertices_size_type vertices_size_type;
-
- typedef typename property_traits<DistanceMap>::value_type distance_type;
typedef ProcessGroup process_group_type;
@@ -1352,10 +1334,6 @@
typedef typename graph_traits<Graph>::degree_size_type degree_size_type;
typedef typename graph_traits<Graph>::edges_size_type edges_size_type;
typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
- typedef typename mpl::if_c<(is_same<CentralityMap,
- dummy_property_map>::value),
- EdgeCentralityMap,
- CentralityMap>::type a_centrality_map;
typename graph_traits<Graph>::vertices_size_type V = num_vertices(g);
@@ -1472,9 +1450,6 @@
VertexIndexMap vertex_index,
Buffer sources)
{
- typedef typename property_traits<DistanceMap>::value_type distance_type;
- typedef static_property_map<distance_type> WeightMap;
-
detail::graph::brandes_unweighted_shortest_paths shortest_paths;
graph::parallel::detail::non_distributed_brandes_betweenness_centrality_impl(pg, g, centrality,
@@ -1528,7 +1503,6 @@
Buffer sources)
{
typedef typename graph_traits<Graph>::degree_size_type degree_size_type;
- typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor;
typedef typename mpl::if_c<(is_same<CentralityMap,
dummy_property_map>::value),
@@ -1565,7 +1539,6 @@
Buffer sources)
{
typedef typename graph_traits<Graph>::degree_size_type degree_size_type;
- typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor;
typedef typename mpl::if_c<(is_same<CentralityMap,
dummy_property_map>::value),
Modified: branches/release/boost/graph/distributed/boman_et_al_graph_coloring.hpp
==============================================================================
--- branches/release/boost/graph/distributed/boman_et_al_graph_coloring.hpp Sat Sep 21 15:26:42 2013 (r85812)
+++ branches/release/boost/graph/distributed/boman_et_al_graph_coloring.hpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -123,7 +123,6 @@
process_group_type;
typedef typename process_group_type::process_id_type process_id_type;
typedef typename graph_traits<DistributedGraph>::vertex_descriptor Vertex;
- typedef typename graph_traits<DistributedGraph>::edge_descriptor Edge;
typedef typename graph_traits<DistributedGraph>::vertices_size_type
vertices_size_type;
typedef typename property_traits<ColorMap>::value_type color_type;
Modified: branches/release/boost/graph/distributed/breadth_first_search.hpp
==============================================================================
--- branches/release/boost/graph/distributed/breadth_first_search.hpp Sat Sep 21 15:26:42 2013 (r85812)
+++ branches/release/boost/graph/distributed/breadth_first_search.hpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -151,8 +151,7 @@
ColorMap color,
BFSVisitor vis,
const bgl_named_params<P, T, R>& params,
- BOOST_GRAPH_ENABLE_IF_MODELS(DistributedGraph, distributed_graph_tag,
- void)*)
+ boost::mpl::true_)
{
parallel_bfs_helper
(g, s, color, vis, get_param(params, buffer_param_t()),
Modified: branches/release/boost/graph/distributed/compressed_sparse_row_graph.hpp
==============================================================================
--- branches/release/boost/graph/distributed/compressed_sparse_row_graph.hpp Sat Sep 21 15:26:42 2013 (r85812)
+++ branches/release/boost/graph/distributed/compressed_sparse_row_graph.hpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -537,7 +537,6 @@
template<BOOST_DISTRIB_CSR_GRAPH_TEMPLATE_PARMS>
void synchronize(const BOOST_DISTRIB_CSR_GRAPH_TYPE& g)
{
- typedef BOOST_DISTRIB_CSR_GRAPH_TYPE graph_type;
synchronize(g.process_group());
}
Modified: branches/release/boost/graph/distributed/concepts.hpp
==============================================================================
--- branches/release/boost/graph/distributed/concepts.hpp Sat Sep 21 15:26:42 2013 (r85812)
+++ branches/release/boost/graph/distributed/concepts.hpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -29,10 +29,6 @@
namespace boost {
-class distributed_graph_tag { };
-class distributed_vertex_list_graph_tag { };
-class distributed_edge_list_graph_tag { };
-
#if BOOST_VERSION >= 103500
namespace concepts {
#endif
Modified: branches/release/boost/graph/distributed/connected_components.hpp
==============================================================================
--- branches/release/boost/graph/distributed/connected_components.hpp Sat Sep 21 15:26:42 2013 (r85812)
+++ branches/release/boost/graph/distributed/connected_components.hpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -296,14 +296,8 @@
typedef typename graph_traits<DistributedGraph>::adjacency_iterator
adjacency_iterator;
- typedef typename graph_traits<DistributedGraph>::out_edge_iterator
- out_edge_iterator;
- typedef typename graph_traits<DistributedGraph>::edge_iterator
- edge_iterator;
typedef typename graph_traits<DistributedGraph>::vertex_descriptor
vertex_descriptor;
- typedef typename graph_traits<DistributedGraph>::edge_descriptor
- edge_descriptor;
typedef typename boost::graph::parallel::process_group_type<DistributedGraph>
::type process_group_type;
Modified: branches/release/boost/graph/distributed/connected_components_parallel_search.hpp
==============================================================================
--- branches/release/boost/graph/distributed/connected_components_parallel_search.hpp Sat Sep 21 15:26:42 2013 (r85812)
+++ branches/release/boost/graph/distributed/connected_components_parallel_search.hpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -290,8 +290,6 @@
typedef typename boost::graph::parallel::process_group_type<Graph>
::type process_group_type;
typedef typename process_group_type::process_id_type process_id_type;
- typedef typename property_map<Graph, vertex_owner_t>
- ::const_type vertex_owner_map;
typedef std::queue<vertex_descriptor> work_queue;
static const component_value_type max_component =
Modified: branches/release/boost/graph/distributed/crauser_et_al_shortest_paths.hpp
==============================================================================
--- branches/release/boost/graph/distributed/crauser_et_al_shortest_paths.hpp Sat Sep 21 15:26:42 2013 (r85812)
+++ branches/release/boost/graph/distributed/crauser_et_al_shortest_paths.hpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -540,13 +540,6 @@
Compare compare, Combine combine, DistInf inf, DistZero zero,
DijkstraVisitor vis)
{
- typedef typename boost::graph::parallel::process_group_type<DistributedGraph>::type
- process_group_type;
- typedef typename process_group_type::process_id_type process_id_type;
- typedef typename graph_traits<DistributedGraph>::vertex_descriptor
- Vertex;
- typedef typename graph_traits<DistributedGraph>::vertices_size_type
- vertices_size_type;
#ifdef PBGL_ACCOUNTING
crauser_et_al_shortest_paths_stats.deleted_vertices.clear();
Modified: branches/release/boost/graph/distributed/dehne_gotz_min_spanning_tree.hpp
==============================================================================
--- branches/release/boost/graph/distributed/dehne_gotz_min_spanning_tree.hpp Sat Sep 21 15:26:42 2013 (r85812)
+++ branches/release/boost/graph/distributed/dehne_gotz_min_spanning_tree.hpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -642,7 +642,6 @@
BOOST_STATIC_ASSERT((is_convertible<traversal_category*,
vertex_list_graph_tag*>::value));
- typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor;
// Don't throw away cached edge weights
Modified: branches/release/boost/graph/distributed/eager_dijkstra_shortest_paths.hpp
==============================================================================
--- branches/release/boost/graph/distributed/eager_dijkstra_shortest_paths.hpp Sat Sep 21 15:26:42 2013 (r85812)
+++ branches/release/boost/graph/distributed/eager_dijkstra_shortest_paths.hpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -349,13 +349,6 @@
Compare compare, Combine combine, DistInf inf, DistZero zero,
DijkstraVisitor vis)
{
- typedef typename boost::graph::parallel::process_group_type<DistributedGraph>::type
- process_group_type;
- typedef typename graph_traits<DistributedGraph>::vertex_descriptor
- Vertex;
- typedef typename graph_traits<DistributedGraph>::vertices_size_type
- vertices_size_type;
-
#ifdef PBGL_ACCOUNTING
eager_dijkstra_shortest_paths_stats.deleted_vertices.clear();
eager_dijkstra_shortest_paths_stats.lookahead = lookahead;
Modified: branches/release/boost/graph/distributed/graphviz.hpp
==============================================================================
--- branches/release/boost/graph/distributed/graphviz.hpp Sat Sep 21 15:26:42 2013 (r85812)
+++ branches/release/boost/graph/distributed/graphviz.hpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -106,10 +106,8 @@
BOOST_GRAPH_ENABLE_IF_MODELS_PARM(Graph,distributed_graph_tag))
{
typedef typename graph_traits<Graph>::directed_category directed_category;
- typedef typename graph_traits<Graph>::vertices_size_type vertices_size_type;
typedef typename boost::graph::parallel::process_group_type<Graph>::type
process_group_type;
- typedef typename process_group_type::process_id_type process_id_type;
typedef typename property_map<Graph, vertex_index_t>::const_type
VertexIndexMap;
typedef typename property_map<Graph, vertex_global_t>::const_type
Modified: branches/release/boost/graph/distributed/hohberg_biconnected_components.hpp
==============================================================================
--- branches/release/boost/graph/distributed/hohberg_biconnected_components.hpp Sat Sep 21 15:26:42 2013 (r85812)
+++ branches/release/boost/graph/distributed/hohberg_biconnected_components.hpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -912,7 +912,6 @@
BOOST_CONCEPT_ASSERT(( IncidenceGraphConcept<Graph> ));
typedef typename graph_traits<Graph>::edges_size_type edges_size_type;
- typedef typename graph_traits<Graph>::degree_size_type degree_size_type;
typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor;
@@ -942,7 +941,6 @@
std::size_t path_length = 1;
typedef std::vector<vertex_descriptor> path_t;
- typedef typename path_t::iterator path_iterator;
unsigned char minimum_phase = 5;
do {
Modified: branches/release/boost/graph/distributed/named_graph.hpp
==============================================================================
--- branches/release/boost/graph/distributed/named_graph.hpp Sat Sep 21 15:26:42 2013 (r85812)
+++ branches/release/boost/graph/distributed/named_graph.hpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -481,8 +481,6 @@
template<BGL_NAMED_GRAPH_PARAMS>
BGL_NAMED_GRAPH::lazy_add_edge::~lazy_add_edge()
{
- typedef typename BGL_NAMED_GRAPH::process_id_type process_id_type;
-
using boost::parallel::detail::make_untracked_pair;
/// If this edge has already been created or will be created by
@@ -679,7 +677,6 @@
template<BGL_NAMED_GRAPH_PARAMS>
BGL_NAMED_GRAPH::lazy_add_edge_with_property::~lazy_add_edge_with_property()
{
- typedef typename BGL_NAMED_GRAPH::process_id_type process_id_type;
using boost::detail::parallel::make_pair_with_property;
/// If this edge has already been created or will be created by
Modified: branches/release/boost/graph/distributed/page_rank.hpp
==============================================================================
--- branches/release/boost/graph/distributed/page_rank.hpp Sat Sep 21 15:26:42 2013 (r85812)
+++ branches/release/boost/graph/distributed/page_rank.hpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -89,8 +89,6 @@
int me;
MPI_Comm_rank(MPI_COMM_WORLD, &me);
- typedef typename property_map<Graph, vertex_owner_t>
- ::const_type vertex_owner_map;
typename property_map<Graph, vertex_owner_t>::const_type
owner = get(vertex_owner, g);
(void)owner;
Modified: branches/release/boost/graph/distributed/strong_components.hpp
==============================================================================
--- branches/release/boost/graph/distributed/strong_components.hpp Sat Sep 21 15:26:42 2013 (r85812)
+++ branches/release/boost/graph/distributed/strong_components.hpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -70,8 +70,6 @@
marshal_set( std::vector<std::vector<typename graph_traits<Graph>::vertex_descriptor> > in,
std::vector<typename graph_traits<Graph>::vertex_descriptor>& out )
{
- typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
-
for( std::size_t i = 0; i < in.size(); ++i ) {
out.insert( out.end(), graph_traits<Graph>::null_vertex() );
out.insert( out.end(), in[i].begin(), in[i].end() );
@@ -85,7 +83,6 @@
std::vector<std::vector<typename graph_traits<Graph>::vertex_descriptor> >& out )
{
typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
- typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator;
while( !in.empty() ) {
typename std::vector<vertex_descriptor>::iterator end
@@ -732,8 +729,6 @@
typedef typename process_group_type::process_id_type process_id_type;
typedef std::vector<std::pair<vertex_descriptor, vertex_descriptor> > VertexPairVec;
- typedef typename graph_traits<Graph>::directed_category directed_category;
-
typename property_map<Graph, vertex_owner_t>::const_type
owner = get(vertex_owner, g);
@@ -862,7 +857,6 @@
VertexIndexMap vertex_index_map,
incidence_graph_tag)
{
- typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator;
typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
typedef iterator_property_map<typename std::vector<vertex_descriptor>::iterator,
VertexIndexMap> IsoMap;
Copied: branches/release/boost/graph/edge_coloring.hpp (from r85534, trunk/boost/graph/edge_coloring.hpp)
==============================================================================
--- /dev/null 00:00:00 1970 (empty, because file is newly added)
+++ branches/release/boost/graph/edge_coloring.hpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813, copy of r85534, trunk/boost/graph/edge_coloring.hpp)
@@ -0,0 +1,196 @@
+//=======================================================================
+// Copyright 2013 Maciej Piechotka
+// Authors: Maciej Piechotka
+//
+// 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_EDGE_COLORING_HPP
+#define BOOST_GRAPH_EDGE_COLORING_HPP
+
+#include <boost/graph/graph_traits.hpp>
+#include <boost/graph/iteration_macros.hpp>
+#include <boost/graph/properties.hpp>
+#include <algorithm>
+#include <limits>
+#include <vector>
+
+/* This algorithm is to find coloring of an edges
+
+ Reference:
+
+ Misra, J., & Gries, D. (1992). A constructive proof of Vizing's
+ theorem. In Information Processing Letters.
+*/
+
+namespace boost {
+ namespace detail {
+ template<typename Graph, typename ColorMap>
+ bool
+ is_free(const Graph &g,
+ ColorMap color,
+ typename boost::graph_traits<Graph>::vertex_descriptor u,
+ typename boost::property_traits<ColorMap>::value_type free_color)
+ {
+ typedef typename boost::property_traits<ColorMap>::value_type color_t;
+ if (free_color == (std::numeric_limits<color_t>::max)())
+ return false;
+ BGL_FORALL_OUTEDGES_T(u, e, g, Graph) {
+ if (get(color, e) == free_color) {
+ return false;
+ }
+ }
+ return true;
+ }
+
+ template<typename Graph, typename ColorMap>
+ std::vector<typename boost::graph_traits<Graph>::vertex_descriptor>
+ maximal_fan(const Graph &g,
+ ColorMap color,
+ typename boost::graph_traits<Graph>::vertex_descriptor x,
+ typename boost::graph_traits<Graph>::vertex_descriptor y)
+ {
+ typedef typename boost::graph_traits<Graph>::vertex_descriptor vertex_t;
+ std::vector<vertex_t> fan;
+ fan.push_back(y);
+ bool extended;
+ do {
+ extended = false;
+ BGL_FORALL_OUTEDGES_T(x, e, g, Graph) {
+ vertex_t v = target(e, g);
+ if (is_free(g, color, fan.back(), get(color, e)) &&
+ std::find(fan.begin(), fan.end(), v) == fan.end()) {
+ fan.push_back(v);
+ extended = true;
+ }
+ }
+ } while(extended);
+ return fan;
+ }
+ template<typename Graph, typename ColorMap>
+ typename boost::property_traits<ColorMap>::value_type
+ find_free_color(const Graph &g,
+ ColorMap color,
+ typename boost::graph_traits<Graph>::vertex_descriptor u)
+ {
+ typename boost::property_traits<ColorMap>::value_type c = 0;
+ while (!is_free(g, color, u, c)) c++;
+ return c;
+ }
+
+ template<typename Graph, typename ColorMap>
+ void
+ invert_cd_path(const Graph &g,
+ ColorMap color,
+ typename boost::graph_traits<Graph>::vertex_descriptor x,
+ typename boost::graph_traits<Graph>::edge_descriptor eold,
+ typename boost::property_traits<ColorMap>::value_type c,
+ typename boost::property_traits<ColorMap>::value_type d)
+ {
+ put(color, eold, d);
+ BGL_FORALL_OUTEDGES_T(x, e, g, Graph) {
+ if (get(color, e) == d && e != eold) {
+ invert_cd_path(g, color, target(e, g), e, d, c);
+ return;
+ }
+ }
+ }
+
+ template<typename Graph, typename ColorMap>
+ void
+ invert_cd_path(const Graph &g,
+ ColorMap color,
+ typename boost::graph_traits<Graph>::vertex_descriptor x,
+ typename boost::property_traits<ColorMap>::value_type c,
+ typename boost::property_traits<ColorMap>::value_type d)
+ {
+ BGL_FORALL_OUTEDGES_T(x, e, g, Graph) {
+ if (get(color, e) == d) {
+ invert_cd_path(g, color, target(e, g), e, d, c);
+ return;
+ }
+ }
+ }
+
+ template<typename Graph, typename ColorMap, typename ForwardIterator>
+ void
+ rotate_fan(const Graph &g,
+ ColorMap color,
+ typename boost::graph_traits<Graph>::vertex_descriptor x,
+ ForwardIterator begin,
+ ForwardIterator end)
+ {
+ typedef typename boost::graph_traits<Graph>::edge_descriptor edge_t;
+ if (begin == end) {
+ return;
+ }
+ edge_t previous = edge(x, *begin, g).first;
+ for (begin++; begin != end; begin++) {
+ edge_t current = edge(x, *begin, g).first;
+ put(color, previous, get(color, current));
+ previous = current;
+ }
+ }
+
+ template<typename Graph, typename ColorMap>
+ class find_free_in_fan
+ {
+ public:
+ find_free_in_fan(const Graph &graph,
+ const ColorMap color,
+ typename boost::property_traits<ColorMap>::value_type d)
+ : graph(graph),
+ color(color),
+ d(d) {}
+ bool operator()(const typename boost::graph_traits<Graph>::vertex_descriptor u) const {
+ return is_free(graph, color, u, d);
+ }
+ private:
+ const Graph &graph;
+ const ColorMap color;
+ const typename boost::property_traits<ColorMap>::value_type d;
+ };
+ }
+
+ template<typename Graph, typename ColorMap>
+ typename boost::property_traits<ColorMap>::value_type
+ color_edge(const Graph &g,
+ ColorMap color,
+ typename boost::graph_traits<Graph>::edge_descriptor e)
+ {
+ typedef typename boost::graph_traits<Graph>::vertex_descriptor vertex_t;
+ typedef typename boost::property_traits<ColorMap>::value_type color_t;
+ typedef typename std::vector<vertex_t>::iterator fan_iterator;
+ using namespace detail;
+ vertex_t x = source(e, g), y = target(e, g);
+ std::vector<vertex_t> fan = maximal_fan(g, color, x, y);
+ color_t c = find_free_color(g, color, x);
+ color_t d = find_free_color(g, color, fan.back());
+ invert_cd_path(g, color, x, c, d);
+ fan_iterator w = std::find_if(fan.begin(),
+ fan.end(),
+ find_free_in_fan<Graph, ColorMap>(g, color, d));
+ rotate_fan(g, color, x, fan.begin(), w + 1);
+ put(color, edge(x, *w, g).first, d);
+ return (std::max)(c, d);
+ }
+
+ template<typename Graph, typename ColorMap>
+ typename boost::property_traits<ColorMap>::value_type
+ edge_coloring(const Graph &g,
+ ColorMap color)
+ {
+ typedef typename boost::property_traits<ColorMap>::value_type color_t;
+ BGL_FORALL_EDGES_T(e, g, Graph) {
+ put(color, e, (std::numeric_limits<color_t>::max)());
+ }
+ color_t colors = 0;
+ BGL_FORALL_EDGES_T(e, g, Graph) {
+ colors = (std::max)(colors, color_edge(g, color, e) + 1);
+ }
+ return colors;
+ }
+}
+
+#endif
Modified: branches/release/boost/graph/edmonds_karp_max_flow.hpp
==============================================================================
--- branches/release/boost/graph/edmonds_karp_max_flow.hpp Sat Sep 21 15:26:42 2013 (r85812)
+++ branches/release/boost/graph/edmonds_karp_max_flow.hpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -151,7 +151,6 @@
const bgl_named_params<P, T, R>& params,
param_not_found)
{
- typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor;
typedef typename graph_traits<Graph>::vertices_size_type size_type;
size_type n = is_default_param(get_param(params, vertex_color)) ?
num_vertices(g) : 1;
Copied: branches/release/boost/graph/find_flow_cost.hpp (from r85536, trunk/boost/graph/find_flow_cost.hpp)
==============================================================================
--- /dev/null 00:00:00 1970 (empty, because file is newly added)
+++ branches/release/boost/graph/find_flow_cost.hpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813, copy of r85536, trunk/boost/graph/find_flow_cost.hpp)
@@ -0,0 +1,52 @@
+//=======================================================================
+// Copyright 2013 University of Warsaw.
+// Authors: Piotr Wygocki
+//
+// 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_FIND_FLOW_COST_HPP
+#define BOOST_GRAPH_FIND_FLOW_COST_HPP
+
+#include <boost/graph/iteration_macros.hpp>
+
+namespace boost {
+
+template<class Graph, class Capacity, class ResidualCapacity, class Weight>
+typename property_traits<typename property_map < Graph, edge_capacity_t >::type>::value_type
+find_flow_cost(const Graph & g, Capacity capacity, ResidualCapacity residual_capacity, Weight weight) {
+ typedef typename property_traits<typename property_map<Graph, edge_weight_t>::const_type>::value_type Cost;
+
+ Cost cost = 0;
+ BGL_FORALL_EDGES_T(e, g, Graph) {
+ if(get(capacity, e) > Cost(0)) {
+ cost += (get(capacity, e) - get(residual_capacity, e)) * get(weight, e);
+ }
+ }
+ return cost;
+}
+
+template <class Graph, class P, class T, class R>
+typename property_traits<typename property_map < Graph, edge_capacity_t >::type>::value_type
+find_flow_cost(const Graph & g,
+ const bgl_named_params<P, T, R>& params) {
+ return find_flow_cost(g,
+ choose_const_pmap(get_param(params, edge_capacity), g, edge_capacity),
+ choose_const_pmap(get_param(params, edge_residual_capacity),
+ g, edge_residual_capacity),
+ choose_const_pmap(get_param(params, edge_weight), g, edge_weight));
+}
+
+template <class Graph>
+typename property_traits<typename property_map < Graph, edge_capacity_t >::type>::value_type
+find_flow_cost(const Graph &g) {
+ bgl_named_params<int, buffer_param_t> params(0);
+ return find_flow_cost(g, params);
+}
+
+
+} //boost
+
+#endif /* BOOST_GRAPH_FIND_FLOW_COST_HPP */
+
Modified: branches/release/boost/graph/fruchterman_reingold.hpp
==============================================================================
--- branches/release/boost/graph/fruchterman_reingold.hpp Sat Sep 21 15:26:42 2013 (r85812)
+++ branches/release/boost/graph/fruchterman_reingold.hpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -282,7 +282,6 @@
Cooling cool,
DisplacementMap displacement)
{
- typedef typename Topology::point_type Point;
typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator;
typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
typedef typename graph_traits<Graph>::edge_iterator edge_iterator;
Modified: branches/release/boost/graph/graph_traits.hpp
==============================================================================
--- branches/release/boost/graph/graph_traits.hpp Sat Sep 21 15:26:42 2013 (r85812)
+++ branches/release/boost/graph/graph_traits.hpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -166,7 +166,13 @@
struct edge_list_graph_tag { };
struct adjacency_matrix_tag { };
- /** @name Taversal Category Traits
+ // Parallel traversal_category tags
+ struct distributed_graph_tag { };
+ struct distributed_vertex_list_graph_tag { };
+ struct distributed_edge_list_graph_tag { };
+#define BOOST_GRAPH_SEQUENTIAL_TRAITS_DEFINES_DISTRIBUTED_TAGS // Disable these from external versions of PBGL
+
+ /** @name Traversal Category Traits
* These traits classify graph types by their supported methods of
* vertex and edge traversal.
*/
Modified: branches/release/boost/graph/graph_utility.hpp
==============================================================================
--- branches/release/boost/graph/graph_utility.hpp Sat Sep 21 15:26:42 2013 (r85812)
+++ branches/release/boost/graph/graph_utility.hpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -237,8 +237,6 @@
template <class Graph, class Vertex>
bool is_adj_dispatch(Graph& g, Vertex a, Vertex b, bidirectional_tag)
{
- typedef typename graph_traits<Graph>::edge_descriptor
- edge_descriptor;
typename graph_traits<Graph>::adjacency_iterator vi, viend,
adj_found;
boost::tie(vi, viend) = adjacent_vertices(a, g);
@@ -265,8 +263,6 @@
template <class Graph, class Vertex>
bool is_adj_dispatch(Graph& g, Vertex a, Vertex b, directed_tag)
{
- typedef typename graph_traits<Graph>::edge_descriptor
- edge_descriptor;
typename graph_traits<Graph>::adjacency_iterator vi, viend, found;
boost::tie(vi, viend) = adjacent_vertices(a, g);
#if defined(BOOST_MSVC) && BOOST_MSVC <= 1300 && defined(__SGI_STL_PORT)
Modified: branches/release/boost/graph/gursoy_atun_layout.hpp
==============================================================================
--- branches/release/boost/graph/gursoy_atun_layout.hpp Sat Sep 21 15:26:42 2013 (r85812)
+++ branches/release/boost/graph/gursoy_atun_layout.hpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -208,9 +208,6 @@
typedef typename graph_traits<VertexListAndIncidenceGraph>::vertex_iterator
vertex_iterator;
- typedef typename graph_traits<VertexListAndIncidenceGraph>::vertex_descriptor
- vertex_descriptor;
- typedef typename Topology::point_type point_type;
vertex_iterator i, iend;
double diameter_ratio = (double)diameter_final / diameter_initial;
double learning_constant_ratio =
@@ -230,6 +227,7 @@
vertex_index_map);
for (int round = 0; round < nsteps; ++round) {
double part_done = (double)round / (nsteps - 1);
+ // fprintf(stderr, "%2d%% done\n", int(rint(part_done * 100.)));
int diameter = (int)(diameter_initial * pow(diameter_ratio, part_done));
double learning_constant =
learning_constant_initial * pow(learning_constant_ratio, part_done);
Copied and modified: branches/release/boost/graph/hawick_circuits.hpp (from r85533, trunk/boost/graph/hawick_circuits.hpp)
==============================================================================
--- trunk/boost/graph/hawick_circuits.hpp Sat Aug 31 15:29:22 2013 (r85533, copy source)
+++ branches/release/boost/graph/hawick_circuits.hpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -105,12 +105,12 @@
typedef typename Traits::vertex_descriptor Vertex;
typedef typename Traits::edge_descriptor Edge;
typedef typename Traits::vertices_size_type VerticesSize;
- typedef typename property_traits<VertexIndexMap>::reference VertexIndex;
+ typedef typename property_traits<VertexIndexMap>::value_type VertexIndex;
typedef typename result_of<
GetAdjacentVertices(Vertex, Graph const&)
>::type AdjacentVertices;
- typedef typename range_iterator<AdjacentVertices>::type AdjacencyIterator;
+ typedef typename range_iterator<AdjacentVertices const>::type AdjacencyIterator;
// The one_bit_color_map starts all white, i.e. not blocked.
// Since we make that assumption (I looked at the implementation, but
Modified: branches/release/boost/graph/is_straight_line_drawing.hpp
==============================================================================
--- branches/release/boost/graph/is_straight_line_drawing.hpp Sat Sep 21 15:26:42 2013 (r85812)
+++ branches/release/boost/graph/is_straight_line_drawing.hpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -106,11 +106,8 @@
{
typedef typename graph_traits<Graph>::vertex_descriptor vertex_t;
- typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator_t;
typedef typename graph_traits<Graph>::edge_descriptor edge_t;
typedef typename graph_traits<Graph>::edge_iterator edge_iterator_t;
- typedef typename graph_traits<Graph>::edges_size_type e_size_t;
- typedef typename graph_traits<Graph>::vertices_size_type v_size_t;
typedef std::size_t x_coord_t;
typedef std::size_t y_coord_t;
Modified: branches/release/boost/graph/king_ordering.hpp
==============================================================================
--- branches/release/boost/graph/king_ordering.hpp Sat Sep 21 15:26:42 2013 (r85812)
+++ branches/release/boost/graph/king_ordering.hpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -37,7 +37,6 @@
typename graph_traits<Graph>::out_edge_iterator ei, ei_end;
Vertex v, w;
- typedef typename std::deque<Vertex>::iterator iterator;
typedef typename std::deque<Vertex>::reverse_iterator reverse_iterator;
reverse_iterator rend = Qptr->rend()-index_begin;
@@ -86,8 +85,6 @@
//this function replaces pop_heap, and tracks state information
template <typename Vertex>
void percolate_down(int offset){
- typedef typename std::deque<Vertex>::reverse_iterator reverse_iterator;
-
int heap_last = index_begin + offset;
int heap_first = Qptr->size() - 1;
@@ -267,7 +264,6 @@
return permutation;
typedef typename boost::graph_traits<Graph>::vertex_descriptor Vertex;
- typedef typename boost::graph_traits<Graph>::vertex_iterator VerIter;
typedef typename property_traits<ColorMap>::value_type ColorValue;
typedef color_traits<ColorValue> Color;
@@ -302,7 +298,6 @@
if (has_no_vertices(G))
return permutation;
- typedef out_degree_property_map<Graph> DegreeMap;
std::vector<default_color_type> colors(num_vertices(G));
return king_ordering(G, permutation,
make_iterator_property_map(&colors[0], index_map,
Modified: branches/release/boost/graph/kruskal_min_spanning_tree.hpp
==============================================================================
--- branches/release/boost/graph/kruskal_min_spanning_tree.hpp Sat Sep 21 15:26:42 2013 (r85812)
+++ branches/release/boost/graph/kruskal_min_spanning_tree.hpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -102,7 +102,6 @@
{
typedef typename graph_traits<Graph>::vertices_size_type size_type;
typedef typename graph_traits<Graph>::vertex_descriptor vertex_t;
- typedef typename property_map<Graph, vertex_index_t>::type index_map_t;
if (num_vertices(g) == 0) return; // Nothing to do in this case
typename graph_traits<Graph>::vertices_size_type
n = num_vertices(g);
Modified: branches/release/boost/graph/maximum_adjacency_search.hpp
==============================================================================
--- branches/release/boost/graph/maximum_adjacency_search.hpp Sat Sep 21 15:26:42 2013 (r85812)
+++ branches/release/boost/graph/maximum_adjacency_search.hpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -118,8 +118,6 @@
void
maximum_adjacency_search(const Graph& g, WeightMap weights, MASVisitor vis, const typename boost::graph_traits<Graph>::vertex_descriptor start, VertexAssignmentMap assignments, KeyedUpdatablePriorityQueue pq) {
typedef typename boost::graph_traits<Graph>::vertex_descriptor vertex_descriptor;
- typedef typename boost::graph_traits<Graph>::vertices_size_type vertices_size_type;
- typedef typename boost::graph_traits<Graph>::edge_descriptor edge_descriptor;
typedef typename boost::property_traits<WeightMap>::value_type weight_type;
std::set<vertex_descriptor> assignedVertices;
@@ -197,7 +195,7 @@
typedef typename boost::graph_traits<Graph>::edge_descriptor edge_descriptor;
BOOST_CONCEPT_ASSERT((boost::Convertible<typename boost::graph_traits<Graph>::directed_category, boost::undirected_tag>));
BOOST_CONCEPT_ASSERT((boost::ReadablePropertyMapConcept<WeightMap, edge_descriptor>));
- typedef typename boost::property_traits<WeightMap>::value_type weight_type;
+ // typedef typename boost::property_traits<WeightMap>::value_type weight_type;
boost::function_requires< MASVisitorConcept<MASVisitor, Graph> >();
BOOST_CONCEPT_ASSERT((boost::ReadWritePropertyMapConcept<VertexAssignmentMap, vertex_descriptor>));
BOOST_CONCEPT_ASSERT((boost::Convertible<vertex_descriptor, typename boost::property_traits<VertexAssignmentMap>::value_type>));
Modified: branches/release/boost/graph/mcgregor_common_subgraphs.hpp
==============================================================================
--- branches/release/boost/graph/mcgregor_common_subgraphs.hpp Sat Sep 21 15:26:42 2013 (r85812)
+++ branches/release/boost/graph/mcgregor_common_subgraphs.hpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -121,7 +121,6 @@
VertexEquivalencePredicate vertices_equivalent,
bool only_connected_subgraphs)
{
- typedef typename graph_traits<GraphFirst>::vertex_descriptor VertexFirst;
typedef typename graph_traits<GraphSecond>::vertex_descriptor VertexSecond;
typedef typename graph_traits<GraphFirst>::edge_descriptor EdgeFirst;
Modified: branches/release/boost/graph/metric_tsp_approx.hpp
==============================================================================
--- branches/release/boost/graph/metric_tsp_approx.hpp Sat Sep 21 15:26:42 2013 (r85812)
+++ branches/release/boost/graph/metric_tsp_approx.hpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -173,7 +173,6 @@
// We build a custom graph in this algorithm.
typedef adjacency_list <vecS, vecS, directedS, no_property, no_property > MSTImpl;
- typedef graph_traits<MSTImpl>::edge_descriptor Edge;
typedef graph_traits<MSTImpl>::vertex_descriptor Vertex;
typedef graph_traits<MSTImpl>::vertex_iterator VItr;
Modified: branches/release/boost/graph/named_function_params.hpp
==============================================================================
--- branches/release/boost/graph/named_function_params.hpp Sat Sep 21 15:26:42 2013 (r85812)
+++ branches/release/boost/graph/named_function_params.hpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -64,6 +64,7 @@
BOOST_BGL_ONE_PARAM_CREF(weight_map, edge_weight) \
BOOST_BGL_ONE_PARAM_CREF(weight_map2, edge_weight2) \
BOOST_BGL_ONE_PARAM_CREF(distance_map, vertex_distance) \
+ BOOST_BGL_ONE_PARAM_CREF(distance_map2, vertex_distance2) \
BOOST_BGL_ONE_PARAM_CREF(predecessor_map, vertex_predecessor) \
BOOST_BGL_ONE_PARAM_CREF(rank_map, vertex_rank) \
BOOST_BGL_ONE_PARAM_CREF(root_map, vertex_root) \
Modified: branches/release/boost/graph/planar_canonical_ordering.hpp
==============================================================================
--- branches/release/boost/graph/planar_canonical_ordering.hpp Sat Sep 21 15:26:42 2013 (r85812)
+++ branches/release/boost/graph/planar_canonical_ordering.hpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -41,10 +41,8 @@
typedef typename graph_traits<Graph>::vertex_descriptor vertex_t;
typedef typename graph_traits<Graph>::edge_descriptor edge_t;
- typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator_t;
typedef typename graph_traits<Graph>::adjacency_iterator
adjacency_iterator_t;
- typedef typename std::pair<vertex_t, vertex_t> vertex_pair_t;
typedef typename property_traits<PlanarEmbedding>::value_type
embedding_value_t;
typedef typename embedding_value_t::const_iterator embedding_iterator_t;
Modified: branches/release/boost/graph/r_c_shortest_paths.hpp
==============================================================================
--- branches/release/boost/graph/r_c_shortest_paths.hpp Sat Sep 21 15:26:42 2013 (r85812)
+++ branches/release/boost/graph/r_c_shortest_paths.hpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -185,7 +185,10 @@
pareto_optimal_resource_containers.clear();
pareto_optimal_solutions.clear();
- unsigned long i_label_num = 0;
+ typedef typename boost::graph_traits<Graph>::vertices_size_type
+ vertices_size_type;
+
+ size_t i_label_num = 0;
typedef
typename
Label_Allocator::template rebind
@@ -217,9 +220,9 @@
vec_vertex_labels[vertex_index_map[s]].push_back( splabel_first_label );
std::vector<typename std::list<Splabel>::iterator>
vec_last_valid_positions_for_dominance( num_vertices( g ) );
- for( int i = 0; i < static_cast<int>( num_vertices( g ) ); ++i )
+ for( vertices_size_type i = 0; i < num_vertices( g ); ++i )
vec_last_valid_positions_for_dominance[i] = vec_vertex_labels[i].begin();
- std::vector<int> vec_last_valid_index_for_dominance( num_vertices( g ), 0 );
+ std::vector<size_t> vec_last_valid_index_for_dominance( num_vertices( g ), 0 );
std::vector<bool>
b_vec_vertex_already_checked_for_dominance( num_vertices( g ), false );
while( !unprocessed_labels.empty() && vis.on_enter_loop(unprocessed_labels, g) )
@@ -241,12 +244,12 @@
// if the label to be extended is undominated
if( !cur_label->b_is_dominated )
{
- int i_cur_resident_vertex_num = cur_label->resident_vertex;
+ vertices_size_type i_cur_resident_vertex_num = get(vertex_index_map, cur_label->resident_vertex);
std::list<Splabel>& list_labels_cur_vertex =
vec_vertex_labels[i_cur_resident_vertex_num];
- if( static_cast<int>( list_labels_cur_vertex.size() ) >= 2
+ if( list_labels_cur_vertex.size() >= 2
&& vec_last_valid_index_for_dominance[i_cur_resident_vertex_num]
- < static_cast<int>( list_labels_cur_vertex.size() ) )
+ < list_labels_cur_vertex.size() )
{
typename std::list<Splabel>::iterator outer_iter =
list_labels_cur_vertex.begin();
@@ -318,7 +321,7 @@
if( !b_outer_iter_erased )
++outer_iter;
}
- if( static_cast<int>( list_labels_cur_vertex.size() ) > 1 )
+ if( list_labels_cur_vertex.size() > 1 )
vec_last_valid_positions_for_dominance[i_cur_resident_vertex_num] =
(--(list_labels_cur_vertex.end()));
else
@@ -327,7 +330,7 @@
b_vec_vertex_already_checked_for_dominance
[i_cur_resident_vertex_num] = true;
vec_last_valid_index_for_dominance[i_cur_resident_vertex_num] =
- static_cast<int>( list_labels_cur_vertex.size() ) - 1;
+ list_labels_cur_vertex.size() - 1;
}
}
if( !b_all_pareto_optimal_solutions && cur_label->resident_vertex == t )
@@ -430,8 +433,8 @@
}
}
- int i_size = static_cast<int>( vec_vertex_labels.size() );
- for( int i = 0; i < i_size; ++i )
+ size_t i_size = vec_vertex_labels.size();
+ for( size_t i = 0; i < i_size; ++i )
{
const std::list<Splabel>& list_labels_cur_vertex = vec_vertex_labels[i];
csi_end = list_labels_cur_vertex.end();
@@ -679,7 +682,7 @@
typename graph_traits<Graph>::edge_descriptor&
ed_last_extended_arc )
{
- int i_size_ed_vec_path = static_cast<int>( ed_vec_path.size() );
+ size_t i_size_ed_vec_path = ed_vec_path.size();
std::vector<typename graph_traits<Graph>::edge_descriptor> buf_path;
if( i_size_ed_vec_path == 0 )
b_feasible = true;
@@ -689,9 +692,9 @@
|| target( ed_vec_path[0], g ) == source( ed_vec_path[1], g ) )
buf_path = ed_vec_path;
else
- for( int i = i_size_ed_vec_path - 1; i >= 0; --i )
- buf_path.push_back( ed_vec_path[i] );
- for( int i = 0; i < i_size_ed_vec_path - 1; ++i )
+ for( size_t i = i_size_ed_vec_path ; i > 0; --i )
+ buf_path.push_back( ed_vec_path[i - 1] );
+ for( size_t i = 0; i < i_size_ed_vec_path - 1; ++i )
{
if( target( buf_path[i], g ) != source( buf_path[i + 1], g ) )
{
@@ -707,7 +710,7 @@
b_correctly_extended = false;
Resource_Container current_resource_levels = initial_resource_levels;
actual_final_resource_levels = current_resource_levels;
- for( int i = 0; i < i_size_ed_vec_path; ++i )
+ for( size_t i = 0; i < i_size_ed_vec_path; ++i )
{
ed_last_extended_arc = buf_path[i];
b_feasible = ref( g,
Modified: branches/release/boost/graph/random.hpp
==============================================================================
--- branches/release/boost/graph/random.hpp Sat Sep 21 15:26:42 2013 (r85812)
+++ branches/release/boost/graph/random.hpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -86,8 +86,6 @@
template <typename Graph, typename WeightMap, typename RandomNumGen>
typename graph_traits<Graph>::edge_descriptor
weighted_random_out_edge(Graph& g, typename graph_traits<Graph>::vertex_descriptor src, WeightMap weight, RandomNumGen& gen) {
- typedef graph_traits<Graph> gt;
- typedef typename gt::vertex_descriptor vertex_descriptor;
typedef typename property_traits<WeightMap>::value_type weight_type;
weight_type weight_sum(0);
BGL_FORALL_OUTEDGES_T(src, e, g, Graph) {weight_sum += get(weight, e);}
Modified: branches/release/boost/graph/random_spanning_tree.hpp
==============================================================================
--- branches/release/boost/graph/random_spanning_tree.hpp Sat Sep 21 15:26:42 2013 (r85812)
+++ branches/release/boost/graph/random_spanning_tree.hpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -33,7 +33,6 @@
template <typename Graph, typename PredMap, typename ColorMap, typename NextEdge>
void random_spanning_tree_internal(const Graph& g, typename graph_traits<Graph>::vertex_descriptor s, PredMap pred, ColorMap color, NextEdge next_edge) {
typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
- typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor;
BOOST_ASSERT (num_vertices(g) >= 1); // g must also be undirected (or symmetric) and connected
Modified: branches/release/boost/graph/read_dimacs.hpp
==============================================================================
--- branches/release/boost/graph/read_dimacs.hpp Sat Sep 21 15:26:42 2013 (r85812)
+++ branches/release/boost/graph/read_dimacs.hpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -45,7 +45,6 @@
const int NODE_FIELDS = 2; /* no of fields in node line */
const int P_FIELDS = 3; /* no of fields in problem line */
- typedef typename graph_traits<Graph>::vertices_size_type vertices_size_type;
typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor;
Modified: branches/release/boost/graph/stoer_wagner_min_cut.hpp
==============================================================================
--- branches/release/boost/graph/stoer_wagner_min_cut.hpp Sat Sep 21 15:26:42 2013 (r85812)
+++ branches/release/boost/graph/stoer_wagner_min_cut.hpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -76,7 +76,6 @@
template < typename Vertex, typename Graph >
void finish_vertex(Vertex u, const Graph & g)
{
- typedef typename boost::property_traits<ParityMap>::value_type parity_type;
typedef typename boost::property_traits<InternalParityMap>::value_type internal_parity_type;
++m_visited;
@@ -131,10 +130,7 @@
typename boost::property_traits<WeightMap>::value_type
stoer_wagner_min_cut(const UndirectedGraph& g, WeightMap weights, ParityMap parities, VertexAssignmentMap assignments, KeyedUpdatablePriorityQueue& pq, IndexMap index_map) {
typedef typename boost::graph_traits<UndirectedGraph>::vertex_descriptor vertex_descriptor;
- typedef typename boost::graph_traits<UndirectedGraph>::vertices_size_type vertices_size_type;
- typedef typename boost::graph_traits<UndirectedGraph>::edge_descriptor edge_descriptor;
typedef typename boost::property_traits<WeightMap>::value_type weight_type;
- typedef typename boost::property_traits<ParityMap>::value_type parity_type;
typename graph_traits<UndirectedGraph>::vertex_iterator u_iter, u_end;
@@ -185,9 +181,9 @@
typedef typename boost::graph_traits<UndirectedGraph>::edge_descriptor edge_descriptor;
BOOST_CONCEPT_ASSERT((boost::Convertible<typename boost::graph_traits<UndirectedGraph>::directed_category, boost::undirected_tag>));
BOOST_CONCEPT_ASSERT((boost::ReadablePropertyMapConcept<WeightMap, edge_descriptor>));
- typedef typename boost::property_traits<WeightMap>::value_type weight_type;
+ // typedef typename boost::property_traits<WeightMap>::value_type weight_type;
BOOST_CONCEPT_ASSERT((boost::WritablePropertyMapConcept<ParityMap, vertex_descriptor>));
- typedef typename boost::property_traits<ParityMap>::value_type parity_type;
+ // typedef typename boost::property_traits<ParityMap>::value_type parity_type;
BOOST_CONCEPT_ASSERT((boost::ReadWritePropertyMapConcept<VertexAssignmentMap, vertex_descriptor>));
BOOST_CONCEPT_ASSERT((boost::Convertible<vertex_descriptor, typename boost::property_traits<VertexAssignmentMap>::value_type>));
BOOST_CONCEPT_ASSERT((boost::KeyedUpdatableQueueConcept<KeyedUpdatablePriorityQueue>));
Copied: branches/release/boost/graph/successive_shortest_path_nonnegative_weights.hpp (from r85568, trunk/boost/graph/successive_shortest_path_nonnegative_weights.hpp)
==============================================================================
--- /dev/null 00:00:00 1970 (empty, because file is newly added)
+++ branches/release/boost/graph/successive_shortest_path_nonnegative_weights.hpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813, copy of r85568, trunk/boost/graph/successive_shortest_path_nonnegative_weights.hpp)
@@ -0,0 +1,261 @@
+//=======================================================================
+// Copyright 2013 University of Warsaw.
+// Authors: Piotr Wygocki
+//
+// 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)
+//=======================================================================
+//
+//This algorithm is described in "Network Flows: Theory, Algorithms, and Applications"
+// by Ahuja, Magnanti, Orlin.
+
+#ifndef BOOST_GRAPH_SUCCESSIVE_SHORTEST_PATH_HPP
+#define BOOST_GRAPH_SUCCESSIVE_SHORTEST_PATH_HPP
+
+#include <numeric>
+
+#include <boost/property_map/property_map.hpp>
+#include <boost/graph/graph_traits.hpp>
+#include <boost/graph/graph_concepts.hpp>
+#include <boost/pending/indirect_cmp.hpp>
+#include <boost/pending/relaxed_heap.hpp>
+#include <boost/graph/dijkstra_shortest_paths.hpp>
+#include <boost/graph/properties.hpp>
+#include <boost/graph/iteration_macros.hpp>
+#include <boost/graph/detail/augment.hpp>
+
+namespace boost {
+
+
+namespace detail {
+
+template <class Graph, class Weight, class Distance, class Reversed>
+class MapReducedWeight :
+ public put_get_helper<typename property_traits<Weight>::value_type, MapReducedWeight<Graph, Weight, Distance, Reversed> > {
+ typedef graph_traits<Graph> gtraits;
+public:
+ typedef boost::readable_property_map_tag category;
+ typedef typename property_traits<Weight>::value_type value_type;
+ typedef value_type reference;
+ typedef typename gtraits::edge_descriptor key_type;
+ MapReducedWeight(const Graph & g, Weight w, Distance d, Reversed r) :
+ g_(g), weight_(w), distance_(d), rev_(r) {}
+
+ reference operator[](key_type v) const {
+ return get(distance_, source(v, g_)) - get(distance_,target(v, g_)) + get(weight_, v);
+ }
+private:
+ const Graph & g_;
+ Weight weight_;
+ Distance distance_;
+ Reversed rev_;
+};
+
+template <class Graph, class Weight, class Distance, class Reversed>
+MapReducedWeight<Graph, Weight, Distance, Reversed>
+make_mapReducedWeight(const Graph & g, Weight w, Distance d, Reversed r) {
+ return MapReducedWeight<Graph, Weight, Distance, Reversed>(g, w, d, r);
+}
+
+}//detail
+
+
+template <class Graph, class Capacity, class ResidualCapacity, class Reversed, class Pred, class Weight, class Distance, class Distance2, class VertexIndex>
+void successive_shortest_path_nonnegative_weights(
+ const Graph &g,
+ typename graph_traits<Graph>::vertex_descriptor s,
+ typename graph_traits<Graph>::vertex_descriptor t,
+ Capacity capacity,
+ ResidualCapacity residual_capacity,
+ Weight weight,
+ Reversed rev,
+ VertexIndex index,
+ Pred pred,
+ Distance distance,
+ Distance2 distance_prev) {
+ filtered_graph<const Graph, is_residual_edge<ResidualCapacity> >
+ gres = detail::residual_graph(g, residual_capacity);
+ typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor;
+
+ BGL_FORALL_EDGES_T(e, g, Graph) {
+ put(residual_capacity, e, get(capacity, e));
+ }
+
+ BGL_FORALL_VERTICES_T(v, g, Graph) {
+ put(distance_prev, v, 0);
+ }
+
+ while(true) {
+ BGL_FORALL_VERTICES_T(v, g, Graph) {
+ put(pred, v, edge_descriptor());
+ }
+ dijkstra_shortest_paths(gres, s,
+ weight_map(detail::make_mapReducedWeight(gres, weight, distance_prev, rev)).
+ distance_map(distance).
+ vertex_index_map(index).
+ visitor(make_dijkstra_visitor(record_edge_predecessors(pred, on_edge_relaxed()))));
+
+ if(get(pred, t) == edge_descriptor()) {
+ break;
+ }
+
+ BGL_FORALL_VERTICES_T(v, g, Graph) {
+ put(distance_prev, v, get(distance_prev, v) + get(distance, v));
+ }
+
+ detail::augment(g, s, t, pred, residual_capacity, rev);
+ }
+}
+
+//in this namespace argument dispatching tak place
+namespace detail {
+
+template <class Graph, class Capacity, class ResidualCapacity, class Weight, class Reversed, class Pred, class Distance, class Distance2, class VertexIndex>
+void successive_shortest_path_nonnegative_weights_dispatch3(
+ const Graph &g,
+ typename graph_traits<Graph>::vertex_descriptor s,
+ typename graph_traits<Graph>::vertex_descriptor t,
+ Capacity capacity,
+ ResidualCapacity residual_capacity,
+ Weight weight,
+ Reversed rev,
+ VertexIndex index,
+ Pred pred,
+ Distance dist,
+ Distance2 dist_pred) {
+ successive_shortest_path_nonnegative_weights(g, s, t, capacity, residual_capacity, weight, rev, index, pred, dist, dist_pred);
+}
+
+//setting default distance map
+template <class Graph, class Capacity, class ResidualCapacity, class Weight, class Reversed, class Pred, class Distance, class VertexIndex>
+void successive_shortest_path_nonnegative_weights_dispatch3(
+ Graph &g,
+ typename graph_traits<Graph>::vertex_descriptor s,
+ typename graph_traits<Graph>::vertex_descriptor t,
+ Capacity capacity,
+ ResidualCapacity residual_capacity,
+ Weight weight,
+ Reversed rev,
+ VertexIndex index,
+ Pred pred,
+ Distance dist,
+ param_not_found) {
+ typedef typename property_traits<Weight>::value_type D;
+
+ std::vector<D> d_map(num_vertices(g));
+
+ successive_shortest_path_nonnegative_weights(g, s, t, capacity, residual_capacity, weight, rev, index, pred, dist,
+ make_iterator_property_map(d_map.begin(), index));
+}
+
+template <class Graph, class P, class T, class R, class Capacity, class ResidualCapacity, class Weight, class Reversed, class Pred, class Distance, class VertexIndex>
+void successive_shortest_path_nonnegative_weights_dispatch2(
+ Graph &g,
+ typename graph_traits<Graph>::vertex_descriptor s,
+ typename graph_traits<Graph>::vertex_descriptor t,
+ Capacity capacity,
+ ResidualCapacity residual_capacity,
+ Weight weight,
+ Reversed rev,
+ VertexIndex index,
+ Pred pred,
+ Distance dist,
+ const bgl_named_params<P, T, R>& params) {
+ successive_shortest_path_nonnegative_weights_dispatch3(g, s, t, capacity, residual_capacity, weight, rev, index, pred, dist, get_param(params, vertex_distance2));
+}
+
+//setting default distance map
+template <class Graph, class P, class T, class R, class Capacity, class ResidualCapacity, class Weight, class Reversed, class Pred, class VertexIndex>
+void successive_shortest_path_nonnegative_weights_dispatch2(
+ Graph &g,
+ typename graph_traits<Graph>::vertex_descriptor s,
+ typename graph_traits<Graph>::vertex_descriptor t,
+ Capacity capacity,
+ ResidualCapacity residual_capacity,
+ Weight weight,
+ Reversed rev,
+ VertexIndex index,
+ Pred pred,
+ param_not_found,
+ const bgl_named_params<P, T, R>& params) {
+ typedef typename property_traits<Weight>::value_type D;
+
+ std::vector<D> d_map(num_vertices(g));
+
+ successive_shortest_path_nonnegative_weights_dispatch3(g, s, t, capacity, residual_capacity, weight, rev, index, pred,
+ make_iterator_property_map(d_map.begin(), index),
+ get_param(params, vertex_distance2));
+}
+
+template <class Graph, class P, class T, class R, class Capacity, class ResidualCapacity, class Weight, class Reversed, class Pred, class VertexIndex>
+void successive_shortest_path_nonnegative_weights_dispatch1(
+ Graph &g,
+ typename graph_traits<Graph>::vertex_descriptor s,
+ typename graph_traits<Graph>::vertex_descriptor t,
+ Capacity capacity,
+ ResidualCapacity residual_capacity,
+ Weight weight,
+ Reversed rev,
+ VertexIndex index,
+ Pred pred,
+ const bgl_named_params<P, T, R>& params) {
+ successive_shortest_path_nonnegative_weights_dispatch2(g, s, t, capacity, residual_capacity, weight, rev, index, pred,
+ get_param(params, vertex_distance), params);
+}
+
+//setting default predecessors map
+template <class Graph, class P, class T, class R, class Capacity, class ResidualCapacity, class Weight, class Reversed, class VertexIndex>
+void successive_shortest_path_nonnegative_weights_dispatch1(
+ Graph &g,
+ typename graph_traits<Graph>::vertex_descriptor s,
+ typename graph_traits<Graph>::vertex_descriptor t,
+ Capacity capacity,
+ ResidualCapacity residual_capacity,
+ Weight weight,
+ Reversed rev,
+ VertexIndex index,
+ param_not_found,
+ const bgl_named_params<P, T, R>& params) {
+ typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor;
+ std::vector<edge_descriptor> pred_vec(num_vertices(g));
+
+ successive_shortest_path_nonnegative_weights_dispatch2(g, s, t, capacity, residual_capacity, weight, rev, index,
+ make_iterator_property_map(pred_vec.begin(), index),
+ get_param(params, vertex_distance), params);
+}
+
+}//detail
+
+
+template <class Graph, class P, class T, class R>
+void successive_shortest_path_nonnegative_weights(
+ Graph &g,
+ typename graph_traits<Graph>::vertex_descriptor s,
+ typename graph_traits<Graph>::vertex_descriptor t,
+ const bgl_named_params<P, T, R>& params) {
+
+ return detail::successive_shortest_path_nonnegative_weights_dispatch1(g, s, t,
+ 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_weight), g, edge_weight),
+ choose_const_pmap(get_param(params, edge_reverse), g, edge_reverse),
+ choose_const_pmap(get_param(params, vertex_index), g, vertex_index),
+ get_param(params, vertex_predecessor),
+ params);
+}
+
+template <class Graph>
+void successive_shortest_path_nonnegative_weights(
+ Graph &g,
+ typename graph_traits<Graph>::vertex_descriptor s,
+ typename graph_traits<Graph>::vertex_descriptor t) {
+ bgl_named_params<int, buffer_param_t> params(0);
+ successive_shortest_path_nonnegative_weights(g, s, t, params);
+}
+
+
+}//boost
+#endif /* BOOST_GRAPH_SUCCESSIVE_SHORTEST_PATH_HPP */
+
Modified: branches/release/boost/graph/tiernan_all_cycles.hpp
==============================================================================
--- branches/release/boost/graph/tiernan_all_cycles.hpp Sat Sep 21 15:26:42 2013 (r85812)
+++ branches/release/boost/graph/tiernan_all_cycles.hpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -212,7 +212,6 @@
{
BOOST_CONCEPT_ASSERT(( IncidenceGraphConcept<Graph> ));
typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
- typedef typename graph_traits<Graph>::edge_descriptor Edge;
typedef typename graph_traits<Graph>::out_edge_iterator OutIterator;
// get the current vertex
Modified: branches/release/boost/graph/transitive_closure.hpp
==============================================================================
--- branches/release/boost/graph/transitive_closure.hpp Sat Sep 21 15:26:42 2013 (r85812)
+++ branches/release/boost/graph/transitive_closure.hpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -14,11 +14,11 @@
#include <functional>
#include <boost/config.hpp>
#include <boost/bind.hpp>
-#include <boost/graph/vector_as_graph.hpp>
#include <boost/graph/strong_components.hpp>
#include <boost/graph/topological_sort.hpp>
#include <boost/graph/graph_concepts.hpp>
#include <boost/graph/named_function_params.hpp>
+#include <boost/graph/adjacency_list.hpp>
#include <boost/concept/assert.hpp>
namespace boost
@@ -71,7 +71,6 @@
if (num_vertices(g) == 0)
return;
typedef typename graph_traits < Graph >::vertex_descriptor vertex;
- typedef typename graph_traits < Graph >::edge_descriptor edge;
typedef typename graph_traits < Graph >::vertex_iterator vertex_iterator;
typedef typename property_traits < VertexIndexMap >::value_type size_type;
typedef typename graph_traits <
@@ -95,7 +94,7 @@
std::vector < std::vector < vertex > >components;
build_component_lists(g, num_scc, component_number, components);
- typedef std::vector<std::vector<cg_vertex> > CG_t;
+ typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS> CG_t;
CG_t CG(num_scc);
for (cg_vertex s = 0; s < components.size(); ++s) {
std::vector < cg_vertex > adj;
@@ -113,7 +112,10 @@
std::unique(adj.begin(), adj.end());
if (di != adj.end())
adj.erase(di, adj.end());
- CG[s] = adj;
+ for (typename std::vector<cg_vertex>::const_iterator i = adj.begin();
+ i != adj.end(); ++i) {
+ add_edge(s, *i, CG);
+ }
}
std::vector<cg_vertex> topo_order;
@@ -126,15 +128,20 @@
iter != topo_order.end(); ++iter)
topo_number[*iter] = n++;
- for (size_type i = 0; i < num_vertices(CG); ++i)
- std::sort(CG[i].begin(), CG[i].end(),
+ std::vector<std::vector<cg_vertex> > CG_vec(num_vertices(CG));
+ for (size_type i = 0; i < num_vertices(CG); ++i) {
+ typedef typename boost::graph_traits<CG_t>::adjacency_iterator cg_adj_iter;
+ std::pair<cg_adj_iter, cg_adj_iter> pr = adjacent_vertices(i, CG);
+ CG_vec[i].assign(pr.first, pr.second);
+ std::sort(CG_vec[i].begin(), CG_vec[i].end(),
boost::bind(std::less<cg_vertex>(),
boost::bind(detail::subscript(topo_number), _1),
boost::bind(detail::subscript(topo_number), _2)));
+ }
std::vector<std::vector<cg_vertex> > chains;
{
- std::vector<cg_vertex> in_a_chain(num_vertices(CG));
+ std::vector<cg_vertex> in_a_chain(CG_vec.size());
for (typename std::vector<cg_vertex>::iterator i = topo_order.begin();
i != topo_order.end(); ++i) {
cg_vertex v = *i;
@@ -144,12 +151,10 @@
for (;;) {
chain.push_back(v);
in_a_chain[v] = true;
- typename graph_traits<CG_t>::adjacency_iterator adj_first, adj_last;
- boost::tie(adj_first, adj_last) = adjacent_vertices(v, CG);
- typename graph_traits<CG_t>::adjacency_iterator next
- = std::find_if(adj_first, adj_last,
+ typename std::vector<cg_vertex>::const_iterator next
+ = std::find_if(CG_vec[v].begin(), CG_vec[v].end(),
std::not1(detail::subscript(in_a_chain)));
- if (next != adj_last)
+ if (next != CG_vec[v].end())
v = *next;
else
break; // end of chain, dead-end
@@ -158,8 +163,8 @@
}
}
}
- std::vector<size_type> chain_number(num_vertices(CG));
- std::vector<size_type> pos_in_chain(num_vertices(CG));
+ std::vector<size_type> chain_number(CG_vec.size());
+ std::vector<size_type> pos_in_chain(CG_vec.size());
for (size_type i = 0; i < chains.size(); ++i)
for (size_type j = 0; j < chains[i].size(); ++j) {
cg_vertex v = chains[i][j];
@@ -168,14 +173,14 @@
}
cg_vertex inf = (std::numeric_limits< cg_vertex >::max)();
- std::vector<std::vector<cg_vertex> > successors(num_vertices(CG),
+ std::vector<std::vector<cg_vertex> > successors(CG_vec.size(),
std::vector<cg_vertex>
(chains.size(), inf));
for (typename std::vector<cg_vertex>::reverse_iterator
i = topo_order.rbegin(); i != topo_order.rend(); ++i) {
cg_vertex u = *i;
- typename graph_traits<CG_t>::adjacency_iterator adj, adj_last;
- for (boost::tie(adj, adj_last) = adjacent_vertices(u, CG);
+ typename std::vector<cg_vertex>::const_iterator adj, adj_last;
+ for (adj = CG_vec[u].begin(), adj_last = CG_vec[u].end();
adj != adj_last; ++adj) {
cg_vertex v = *adj;
if (topo_number[v] < successors[u][chain_number[v]]) {
@@ -188,32 +193,31 @@
}
}
- for (size_type i = 0; i < CG.size(); ++i)
- CG[i].clear();
- for (size_type i = 0; i < CG.size(); ++i)
+ for (size_type i = 0; i < CG_vec.size(); ++i)
+ CG_vec[i].clear();
+ for (size_type i = 0; i < CG_vec.size(); ++i)
for (size_type j = 0; j < chains.size(); ++j) {
size_type topo_num = successors[i][j];
if (topo_num < inf) {
cg_vertex v = topo_order[topo_num];
for (size_type k = pos_in_chain[v]; k < chains[j].size(); ++k)
- CG[i].push_back(chains[j][k]);
+ CG_vec[i].push_back(chains[j][k]);
}
}
// Add vertices to the transitive closure graph
- typedef typename graph_traits < GraphTC >::vertex_descriptor tc_vertex;
{
vertex_iterator i, i_end;
for (boost::tie(i, i_end) = vertices(g); i != i_end; ++i)
g_to_tc_map[*i] = add_vertex(tc);
}
// Add edges between all the vertices in two adjacent SCCs
- typename graph_traits<CG_t>::vertex_iterator si, si_end;
- for (boost::tie(si, si_end) = vertices(CG); si != si_end; ++si) {
- cg_vertex s = *si;
- typename graph_traits<CG_t>::adjacency_iterator i, i_end;
- for (boost::tie(i, i_end) = adjacent_vertices(s, CG); i != i_end; ++i) {
+ typename std::vector<std::vector<cg_vertex> >::const_iterator si, si_end;
+ for (si = CG_vec.begin(), si_end = CG_vec.end(); si != si_end; ++si) {
+ cg_vertex s = si - CG_vec.begin();
+ typename std::vector<cg_vertex>::const_iterator i, i_end;
+ for (i = CG_vec[s].begin(), i_end = CG_vec[s].end(); i != i_end; ++i) {
cg_vertex t = *i;
for (size_type k = 0; k < components[s].size(); ++k)
for (size_type l = 0; l < components[t].size(); ++l)
@@ -300,7 +304,6 @@
template < typename G > void warshall_transitive_closure(G & g)
{
- typedef typename graph_traits < G >::vertex_descriptor vertex;
typedef typename graph_traits < G >::vertex_iterator vertex_iterator;
BOOST_CONCEPT_ASSERT(( AdjacencyMatrixConcept < G > ));
@@ -326,7 +329,6 @@
template < typename G > void warren_transitive_closure(G & g)
{
using namespace boost;
- typedef typename graph_traits < G >::vertex_descriptor vertex;
typedef typename graph_traits < G >::vertex_iterator vertex_iterator;
BOOST_CONCEPT_ASSERT(( AdjacencyMatrixConcept < G > ));
Modified: branches/release/boost/graph/two_graphs_common_spanning_trees.hpp
==============================================================================
--- branches/release/boost/graph/two_graphs_common_spanning_trees.hpp Sat Sep 21 15:26:42 2013 (r85812)
+++ branches/release/boost/graph/two_graphs_common_spanning_trees.hpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -591,17 +591,11 @@
typedef typename GraphTraits::edges_size_type edges_size_type;
typedef typename GraphTraits::edge_iterator edge_iterator;
- typedef typename Seq::const_iterator seq_const_iterator;
- typedef typename Seq::difference_type seq_diff_type;
typedef typename Seq::value_type seq_value_type;
typedef typename Seq::size_type seq_size_type;
- typedef typename Seq::iterator seq_iterator;
- typedef typename Order::const_iterator order_const_iterator;
- typedef typename Order::difference_type order_diff_type;
typedef typename Order::value_type order_value_type;
typedef typename Order::size_type order_size_type;
- typedef typename Order::iterator order_iterator;
BOOST_STATIC_ASSERT((is_same<order_value_type, edge_descriptor>::value));
BOOST_CONCEPT_ASSERT((Convertible<order_size_type, edges_size_type>));
@@ -846,7 +840,6 @@
typedef graph_traits<Graph> GraphTraits;
typedef typename GraphTraits::edge_descriptor edge_descriptor;
- typedef typename GraphTraits::edges_size_type edges_size_type;
typedef typename GraphTraits::edge_iterator edge_iterator;
std::vector<edge_descriptor> iGO, vGO;
Modified: branches/release/boost/graph/undirected_dfs.hpp
==============================================================================
--- branches/release/boost/graph/undirected_dfs.hpp Sat Sep 21 15:26:42 2013 (r85812)
+++ branches/release/boost/graph/undirected_dfs.hpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -46,18 +46,18 @@
typedef color_traits<ColorValue> Color;
typedef color_traits<EColorValue> EColor;
typedef typename graph_traits<IncidenceGraph>::out_edge_iterator Iter;
- typedef std::pair<Vertex, std::pair<Iter, Iter> > VertexInfo;
+ typedef std::pair<Vertex, std::pair<boost::optional<Edge>, std::pair<Iter, Iter> > > VertexInfo;
std::vector<VertexInfo> stack;
put(vertex_color, u, Color::gray());
vis.discover_vertex(u, g);
- stack.push_back(std::make_pair(u, out_edges(u, g)));
+ stack.push_back(std::make_pair(u, std::make_pair(boost::optional<Edge>(), out_edges(u, g))));
while (!stack.empty()) {
VertexInfo& back = stack.back();
u = back.first;
- Iter ei, ei_end;
- boost::tie(ei, ei_end) = back.second;
+ boost::optional<Edge> src_e = back.second.first;
+ Iter ei = back.second.second.first, ei_end = back.second.second.second;
stack.pop_back();
while (ei != ei_end) {
Vertex v = target(*ei, g);
@@ -67,20 +67,24 @@
put(edge_color, *ei, EColor::black());
if (v_color == Color::white()) {
vis.tree_edge(*ei, g);
- stack.push_back(std::make_pair(u, std::make_pair(++ei, ei_end)));
+ src_e = *ei;
+ stack.push_back(std::make_pair(u, std::make_pair(src_e, std::make_pair(++ei, ei_end))));
u = v;
put(vertex_color, u, Color::gray());
vis.discover_vertex(u, g);
boost::tie(ei, ei_end) = out_edges(u, g);
} else if (v_color == Color::gray()) {
if (uv_color == EColor::white()) vis.back_edge(*ei, g);
+ call_finish_edge(vis, *ei, g);
++ei;
} else { // if (v_color == Color::black())
+ call_finish_edge(vis, *ei, g);
++ei;
}
}
put(vertex_color, u, Color::black());
vis.finish_vertex(u, g);
+ if (src_e) call_finish_edge(vis, src_e.get(), g);
}
}
@@ -119,6 +123,7 @@
undir_dfv_impl(g, v, vis, vertex_color, edge_color);
} else if (v_color == Color::gray() && uv_color == EColor::white())
vis.back_edge(*ei, g);
+ call_finish_edge(vis, *ei, g);
}
put(vertex_color, u, Color::black()); vis.finish_vertex(u, g);
}
Modified: branches/release/boost/graph/vf2_sub_graph_iso.hpp
==============================================================================
--- branches/release/boost/graph/vf2_sub_graph_iso.hpp Sat Sep 21 15:26:42 2013 (r85812)
+++ branches/release/boost/graph/vf2_sub_graph_iso.hpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -1014,8 +1014,6 @@
bool vf2_subgraph_iso(const GraphSmall& graph_small, const GraphLarge& graph_large,
SubGraphIsoMapCallback user_callback) {
- typedef typename graph_traits<GraphSmall>::vertex_descriptor vertex_small_type;
-
return vf2_subgraph_iso(graph_small, graph_large, user_callback,
get(vertex_index, graph_small), get(vertex_index, graph_large),
vertex_order_by_mult(graph_small),
@@ -1144,8 +1142,6 @@
bool vf2_graph_iso(const Graph1& graph1, const Graph2& graph2,
GraphIsoMapCallback user_callback) {
- typedef typename graph_traits<Graph1>::vertex_descriptor vertex1_type;
-
return vf2_graph_iso(graph1, graph2, user_callback,
get(vertex_index, graph1), get(vertex_index, graph2),
vertex_order_by_mult(graph1),
Modified: branches/release/boost/graph/visitors.hpp
==============================================================================
--- branches/release/boost/graph/visitors.hpp Sat Sep 21 15:26:42 2013 (r85812)
+++ branches/release/boost/graph/visitors.hpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -44,7 +44,7 @@
on_discover_vertex_num, on_finish_vertex_num, on_examine_vertex_num,
on_examine_edge_num, on_tree_edge_num, on_non_tree_edge_num,
on_gray_target_num, on_black_target_num,
- on_forward_or_cross_edge_num, on_back_edge_num,
+ on_forward_or_cross_edge_num, on_back_edge_num, on_finish_edge_num,
on_edge_relaxed_num, on_edge_not_relaxed_num,
on_edge_minimized_num, on_edge_not_minimized_num
};
@@ -75,6 +75,7 @@
struct on_forward_or_cross_edge {
enum { num = detail::on_forward_or_cross_edge_num }; };
struct on_back_edge { enum { num = detail::on_back_edge_num }; };
+ struct on_finish_edge { enum { num = detail::on_finish_edge_num }; };
struct on_edge_relaxed { enum { num = detail::on_edge_relaxed_num }; };
struct on_edge_not_relaxed {
Modified: branches/release/boost/graph/write_dimacs.hpp
==============================================================================
--- branches/release/boost/graph/write_dimacs.hpp Sat Sep 21 15:26:42 2013 (r85812)
+++ branches/release/boost/graph/write_dimacs.hpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -51,10 +51,6 @@
typename graph_traits<Graph>::vertex_descriptor sink,
std::ostream& out)
{
- typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
- typedef typename graph_traits<Graph>::vertices_size_type vertices_size_type;
- typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor;
- typedef typename graph_traits<Graph>::edges_size_type edges_size_type;
typedef typename graph_traits<Graph>::edge_iterator edge_iterator;
out << "c DIMACS max-flow file generated from boost::write_dimacs_max_flow" << std::endl;
Modified: branches/release/boost/property_map/dynamic_property_map.hpp
==============================================================================
--- branches/release/boost/property_map/dynamic_property_map.hpp Sat Sep 21 15:26:42 2013 (r85812)
+++ branches/release/boost/property_map/dynamic_property_map.hpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -234,6 +234,15 @@
return *this;
}
+ template<typename PropertyMap>
+ dynamic_properties
+ property(const std::string& name, PropertyMap property_map_) const
+ {
+ dynamic_properties result = *this;
+ result.property(name, property_map_);
+ return result;
+ }
+
iterator begin() { return property_maps.begin(); }
const_iterator begin() const { return property_maps.begin(); }
iterator end() { return property_maps.end(); }
Modified: branches/release/boost/property_map/property_map.hpp
==============================================================================
--- branches/release/boost/property_map/property_map.hpp Sat Sep 21 15:26:42 2013 (r85812)
+++ branches/release/boost/property_map/property_map.hpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -13,6 +13,7 @@
#include <boost/assert.hpp>
#include <boost/config.hpp>
+#include <boost/static_assert.hpp>
#include <boost/pending/cstddef.hpp>
#include <boost/detail/iterator.hpp>
#include <boost/concept_check.hpp>
@@ -147,6 +148,7 @@
#else
template <class T>
struct property_traits<T*> {
+ // BOOST_STATIC_ASSERT(boost::is_same<T, T*>::value && !"Using pointers as property maps is deprecated");
typedef T value_type;
typedef value_type& reference;
typedef std::ptrdiff_t key_type;
@@ -154,6 +156,7 @@
};
template <class T>
struct property_traits<const T*> {
+ // BOOST_STATIC_ASSERT(boost::is_same<T, T*>::value && !"Using pointers as property maps is deprecated");
typedef T value_type;
typedef const value_type& reference;
typedef std::ptrdiff_t key_type;
Modified: branches/release/libs/graph/build/Jamfile.v2
==============================================================================
--- branches/release/libs/graph/build/Jamfile.v2 Sat Sep 21 15:26:42 2013 (r85812)
+++ branches/release/libs/graph/build/Jamfile.v2 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -21,6 +21,7 @@
# Without these flags, MSVC 7.1 and 8.0 crash
# User reports that VC++ 8.0 does not fail anymore, so that is removed
<toolset>msvc-7.1:<cxxflags>-GR-
+ <toolset>sun:<build>no
:
:
;
Modified: branches/release/libs/graph/doc/DFSVisitor.html
==============================================================================
--- branches/release/libs/graph/doc/DFSVisitor.html Sat Sep 21 15:26:42 2013 (r85812)
+++ branches/release/libs/graph/doc/DFSVisitor.html 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -150,6 +150,15 @@
</tr>
<tr>
+<td>Finish Edge</td>
+<td><tt>vis.finish_edge(e, g)</tt></td>
+<td><tt>void</tt></td>
+<td>
+This is invoked on each non-tree edge as well as on each tree edge after
+<tt>finish_vertex</tt> has been called on its target vertex.</td>
+</tr>
+
+<tr>
<td>Finish Vertex</td>
<td><tt>vis.finish_vertex(u, g)</tt></td>
<td><tt>void</tt></td>
Copied and modified: branches/release/libs/graph/doc/cycle_canceling.html (from r85536, trunk/libs/graph/doc/cycle_canceling.html)
==============================================================================
--- trunk/libs/graph/doc/cycle_canceling.html Sat Aug 31 16:09:11 2013 (r85536, copy source)
+++ branches/release/libs/graph/doc/cycle_canceling.html 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -56,7 +56,7 @@
Note that edges from <i>E</i> can have negative weights.
<p>
If weights in the graph are nonnegative, the
-successive_shortest_path()
+successive_shortest_path_nonnegative_weights()
might be better choice for min cost max flow.
<p>
@@ -78,7 +78,7 @@
<H3>Where Defined</H3>
<P>
-boost/graph/successive_shortest_path.hpp
+boost/graph/successive_shortest_path_nonnegative_weights.hpp
<P>
@@ -191,7 +191,7 @@
<h3>See Also</h3>
-successive_shortest_path()<br>
+successive_shortest_path_nonnegative_weights()<br>
<a href="./find_flow_cost.html"><tt>find_flow_cost()</tt></a>.
<br>
Modified: branches/release/libs/graph/doc/depth_first_search.html
==============================================================================
--- branches/release/libs/graph/doc/depth_first_search.html Sat Sep 21 15:26:42 2013 (r85812)
+++ branches/release/libs/graph/doc/depth_first_search.html 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -107,6 +107,7 @@
<i>...</i>
<b>else if</b> (<i>color[v] =</i> BLACK)
<i>...</i>
+ <i>...</i>
<b>end for</b>
<i>color[u] :=</i> BLACK
<i>f_time[u] := time := time + 1</i>
@@ -140,6 +141,8 @@
-
<i>(u,v)</i> is a cross or forward edge
-
+finish edge <i>(u,v)</i>
+-
finish vertex <i>u</i>
-
</pre>
@@ -266,6 +269,9 @@
<li><b><tt>vis.forward_or_cross_edge(e, g)</tt></b> is invoked on
forward or cross edges in the graph. In an undirected graph this
method is never called.
+
+<li><b><tt>vis.finish_edge(e, g)</tt></b> is invoked on the non-tree edges in
+ the graph as well as on each tree edge after its target vertex is finished.
<li><b><tt>vis.finish_vertex(u, g)</tt></b> is invoked on a vertex after
all of its out edges have been added to the search tree and all of
Modified: branches/release/libs/graph/doc/dijkstra_shortest_paths_no_color_map.html
==============================================================================
--- branches/release/libs/graph/doc/dijkstra_shortest_paths_no_color_map.html Sat Sep 21 15:26:42 2013 (r85812)
+++ branches/release/libs/graph/doc/dijkstra_shortest_paths_no_color_map.html 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -124,11 +124,12 @@
<b>if</b> (<i>w(u,v) + d[u] < d[v]</i>)
<i>d[v] := w(u,v) + d[u]</i>
<i>p[v] := u</i>
- DECREASE-KEY(<i>Q</i>, <i>v</i>)
+ <b>if</b> (<i>d[v]</i> was originally infinity)
+ INSERT(<i>Q</i>, <i>v</i>)
+ <b>else</b>
+ DECREASE-KEY(<i>Q</i>, <i>v</i>)
<b>else</b>
...
- <b>if</b> (<i>d[v]</i> was originally infinity)
- INSERT(<i>Q</i>, <i>v</i>)
<b>end for</b>
<b>end while</b>
return (<i>d</i>, <i>p</i>)
@@ -146,10 +147,11 @@
edge <i>(u,v)</i> relaxed
+discover vertex <i>v</i>
+
edge <i>(u,v)</i> not relaxed
-discover vertex <i>v</i>
finish vertex <i>u</i>
</pre>
</td>
Copied: branches/release/libs/graph/doc/edge_coloring.html (from r85534, trunk/libs/graph/doc/edge_coloring.html)
==============================================================================
--- /dev/null 00:00:00 1970 (empty, because file is newly added)
+++ branches/release/libs/graph/doc/edge_coloring.html 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813, copy of r85534, trunk/libs/graph/doc/edge_coloring.html)
@@ -0,0 +1,98 @@
+<HTML>
+<!--
+ ~~ Copyright (c) Maciej Piechotka 2013
+ ~~
+ Distributed under the Boost Software License, Version 1.0.
+ (See accompanying file LICENSE_1_0.txt or copy at
+ http://www.boost.org/LICENSE_1_0.txt)
+-->
+
+
+<Head>
+<Title>Boost Graph Library: Edge Coloring</Title>
+<BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b"
+ ALINK="#ff0000">
+<IMG SRC="../../../boost.png"
+ ALT="C++ Boost" width="277" height="86">
+
+<BR Clear>
+
+<H1>
+<!-- <img src="figs/python.gif" alt="(Python)"/> -->
+<TT>edge_coloring</TT>
+</H1>
+
+
+<P>
+<DIV ALIGN="LEFT">
+<TABLE CELLPADDING=3 border>
+<TR><TH ALIGN="LEFT"><B>Graphs:</B></TH>
+<TD ALIGN="LEFT">undirected, loop-free</TD>
+</TR>
+<TR><TH ALIGN="LEFT"><B>Properties:</B></TH>
+<TD ALIGN="LEFT">color</TD>
+</TR>
+<TR><TH ALIGN="LEFT"><B>Complexity:</B></TH>
+<TD ALIGN="LEFT">time: <i>O(|E| |V|)</i> </TD>
+</TR>
+</TABLE>
+</DIV>
+
+
+<pre>
+ template <class Graph, class ColorMap>
+ typename boost::property_traits<ColorMap>::value_type
+ edge_coloring(const Graph &g, ColorMap color);
+</pre>
+
+<p>Computes an edge coloring for the vertices in the graph, using
+an algorithm proposed by Mista et al. []. Given edges ordered
+e<sub>1</sub>, e<sub>2</sub>, ..., e<sub>n</sub> it assignes a
+colors c<sub>1</sub>, c<sub>2</sub>, ..., c<sub>n</sub> in a way
+that no vertex connects with 2 edges of the same color. Furthermore
+at most m + 1 colors are used.
+
+<!-- King, I.P. An automatic reordering scheme for simultaneous equations derived from network analysis. Int. J. Numer. Methods Engrg. 2 (1970), 523-533 -->
+
+<h3>Where defined</h3>
+boost/graph/edge_coloring.hpp
+
+<h3>Parameters</h3>
+
+IN: <tt>const Graph& g</tt>
+<blockquote>
+ The graph object on which the algorithm will be applied. The type
+ <tt>Graph</tt> must be a model of <a href="EdgeListGraph.html">
+ Edge List Graph</a> and <a href="IncidenceGraph.html">Incidence
+ Graph</a>.
+</blockquote>
+
+OUT: <tt>ColorMap color</tt>
+<blockquote>
+ This property map records the colors of each edges. It must be a
+ model of <A HREF="../../property_map/doc/ReadWritePropertyMap.html">
+ Read/Write Property Map</A> whose key type is the same as the edge
+ descriptor type of the graph and whose value type is an integral type
+ that can store all values smaller or equal to m.
+</blockquote>
+
+
+<h3>Example</h3>
+
+See <A
+href="../example/edge_coloring.cpp"><tt>example/king_ordering.cpp</tt></A>.
+
+<h3>See Also</h3>
+
+sequential vertex ordering.
+
+<br>
+<HR>
+<TABLE>
+<TR valign=top>
+<TD nowrap>Copyright © 2013</TD><TD>
+Maciej Piechotka (<A HREF="mailto:uzytkownik2_at_[hidden]">uzytkownik2_at_[hidden]</A>)
+</TD></TR></TABLE>
+
+</BODY>
+</HTML>
Copied and modified: branches/release/libs/graph/doc/find_flow_cost.html (from r85536, trunk/libs/graph/doc/find_flow_cost.html)
==============================================================================
--- trunk/libs/graph/doc/find_flow_cost.html Sat Aug 31 16:09:11 2013 (r85536, copy source)
+++ branches/release/libs/graph/doc/find_flow_cost.html 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -42,13 +42,13 @@
<p>
In order to compute the min cost max flow use :
-successive_shortest_path() or
+successive_shortest_path_nonnegative_weights() or
<a href="./cycle_canceling.html"><tt>cycle_canceling()</tt></a>.
<H3>Where Defined</H3>
<P>
-boost/graph/successive_shortest_path.hpp
+boost/graph/successive_shortest_path_nonnegative_weights.hpp
<P>
@@ -102,13 +102,13 @@
<h3>Example</h3>
-The function is used in the successive_shortest_path example. The program in <a
-href="../example/successive_shortest_path_example.cpp"><tt>example/successive_shortest_path_example.cpp</tt></a>.
+The function is used in the successive_shortest_path_nonnegative_weights example. The program in <a
+href="../example/successive_shortest_path_nonnegative_weights_example.cpp"><tt>example/successive_shortest_path_nonnegative_weights_example.cpp</tt></a>.
<h3>See Also</h3>
<a href="./cycle_canceling.html"><tt>cycle_canceling()</tt></a><br>
-successive_shortest_path().
+successive_shortest_path_nonnegative_weights().
<br>
<HR>
Modified: branches/release/libs/graph/doc/graph_theory_review.html
==============================================================================
--- branches/release/libs/graph/doc/graph_theory_review.html Sat Sep 21 15:26:42 2013 (r85812)
+++ branches/release/libs/graph/doc/graph_theory_review.html 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -552,6 +552,9 @@
The <b><i>maximum flow problem</i></b> is to determine the maximum
possible value for <i>|f|</i> and the corresponding flow values for
every vertex pair in the graph.
+<p>
+The <b><i>minimum cost maximum flow problem</i></b> is to determine the maximum flow which minimizes <i> sum<sub>(u,v) in E</sub>
+cost(u,v) * f(u,v) </i>.
<p>
A flow network is shown in <a href="#fig:max-flow">Figure
Copied: branches/release/libs/graph/doc/hawick_circuits.html (from r85533, trunk/libs/graph/doc/hawick_circuits.html)
==============================================================================
--- /dev/null 00:00:00 1970 (empty, because file is newly added)
+++ branches/release/libs/graph/doc/hawick_circuits.html 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813, copy of r85533, trunk/libs/graph/doc/hawick_circuits.html)
@@ -0,0 +1,58 @@
+<p><body bgcolor="#ffffff" link="#0000ee" text="#000000" vlink="#551a8b" alink="#ff0000"></p>
+
+<p><img src="../../../boost.png" alt="C++ Boost" /></p>
+
+<h1 id="hawick_circuits"><code>hawick_circuits</code></h1>
+
+<pre><code>template <typename Graph, typename Visitor, typename VertexIndexMap>
+void hawick_circuits(Graph const& graph, Visitor visitor, VertexIndexMap const& vim = get(vertex_index, graph));
+
+template <typename Graph, typename Visitor, typename VertexIndexMap>
+void hawick_unique_circuits(Graph const& graph, Visitor visitor, VertexIndexMap const& vim = get(vertex_index, graph));
+</code></pre>
+
+<p>Enumerate all the elementary circuits in a directed multigraph. Specifically,
+self-loops and redundant circuits caused by parallel edges are enumerated too.
+<code>hawick_unique_circuits</code> may be used if redundant circuits caused by parallel
+edges are not desired.</p>
+
+<p>The algorithm is described in detail in
+http://www.massey.ac.nz/~kahawick/cstn/013/cstn-013.pdf.</p>
+
+<h3 id="where-defined">Where defined</h3>
+
+<p>#include <boost/graph/hawick_circuits.hpp></p>
+
+<h3 id="parameters">Parameters</h3>
+
+<p><strong>IN:</strong> <code>Graph const& graph</code></p>
+
+<blockquote>
+ <p>The graph on which the algorithm is to be performed. It must be a model of
+ the <code>VertexListGraph</code> and <code>AdjacencyGraph</code> concepts.</p>
+</blockquote>
+
+<p><strong>IN:</strong> <code>Visitor visitor</code></p>
+
+<blockquote>
+ <p>The visitor that will be notified on each circuit found by the algorithm.
+ The <code>visitor.cycle(circuit, graph)</code> expression must be valid, with <code>circuit</code>
+ being a <code>const</code>-reference to a random access sequence of <code>vertex_descriptor</code>s.</p>
+
+ <p>For example, if a circuit <code>u -> v -> w -> u</code> exists in the graph, the
+ visitor will be called with a sequence consisting of <code>(u, v, w)</code>.</p>
+</blockquote>
+
+<p><strong>IN:</strong> <code>VertexIndexMap const& vim = get(vertex_index, graph)</code></p>
+
+<blockquote>
+ <p>A model of the <code>ReadablePropertyMap</code> concept mapping each <code>vertex_descriptor</code>
+ to an integer in the range <code>[0, num_vertices(graph))</code>. It defaults to using
+ the vertex index map provided by the <code>graph</code>.</p>
+</blockquote>
+
+<hr />
+
+<div class="footer">
+ © 2013 Louis Dionne
+</div>
Copied: branches/release/libs/graph/doc/hawick_circuits.md (from r85533, trunk/libs/graph/doc/hawick_circuits.md)
==============================================================================
--- /dev/null 00:00:00 1970 (empty, because file is newly added)
+++ branches/release/libs/graph/doc/hawick_circuits.md 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813, copy of r85533, trunk/libs/graph/doc/hawick_circuits.md)
@@ -0,0 +1,53 @@
+<body bgcolor="#ffffff" link="#0000ee" text="#000000" vlink="#551a8b" alink="#ff0000">
+
+
+
+# `hawick_circuits`
+
+ template <typename Graph, typename Visitor, typename VertexIndexMap>
+ void hawick_circuits(Graph const& graph, Visitor visitor, VertexIndexMap const& vim = get(vertex_index, graph));
+
+ template <typename Graph, typename Visitor, typename VertexIndexMap>
+ void hawick_unique_circuits(Graph const& graph, Visitor visitor, VertexIndexMap const& vim = get(vertex_index, graph));
+
+Enumerate all the elementary circuits in a directed multigraph. Specifically,
+self-loops and redundant circuits caused by parallel edges are enumerated too.
+`hawick_unique_circuits` may be used if redundant circuits caused by parallel
+edges are not desired.
+
+The algorithm is described in detail in
+<http://www.massey.ac.nz/~kahawick/cstn/013/cstn-013.pdf>.
+
+
+### Where defined
+
+[`#include <boost/graph/hawick_circuits.hpp>`](../../../boost/graph/hawick_circuits.hpp)
+
+
+### Parameters
+
+__IN:__ `Graph const& graph`
+
+> The graph on which the algorithm is to be performed. It must be a model of
+> the `VertexListGraph` and `AdjacencyGraph` concepts.
+
+__IN:__ `Visitor visitor`
+
+> The visitor that will be notified on each circuit found by the algorithm.
+> The `visitor.cycle(circuit, graph)` expression must be valid, with `circuit`
+> being a `const`-reference to a random access sequence of `vertex_descriptor`s.
+>
+> For example, if a circuit `u -> v -> w -> u` exists in the graph, the
+> visitor will be called with a sequence consisting of `(u, v, w)`.
+
+__IN:__ `VertexIndexMap const& vim = get(vertex_index, graph)`
+
+> A model of the `ReadablePropertyMap` concept mapping each `vertex_descriptor`
+> to an integer in the range `[0, num_vertices(graph))`. It defaults to using
+> the vertex index map provided by the `graph`.
+
+
+------------------------------------------------------------------------------
+<div class="footer">
+ © 2013 Louis Dionne
+</div>
Copied: branches/release/libs/graph/doc/successive_shortest_path_nonnegative_weights.html (from r85568, trunk/libs/graph/doc/successive_shortest_path_nonnegative_weights.html)
==============================================================================
--- /dev/null 00:00:00 1970 (empty, because file is newly added)
+++ branches/release/libs/graph/doc/successive_shortest_path_nonnegative_weights.html 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813, copy of r85568, trunk/libs/graph/doc/successive_shortest_path_nonnegative_weights.html)
@@ -0,0 +1,264 @@
+<HTML>
+<!--
+ Copyright (c) Piotr Wygocki 2013
+
+ Distributed under the Boost Software License, Version 1.0.
+ (See accompanying file LICENSE_1_0.txt or copy at
+ http://www.boost.org/LICENSE_1_0.txt)
+ -->
+<Head>
+<Title>Boost Graph Library: Successive Shortest Path for Min Cost Max Flow</Title>
+<BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b"
+ ALINK="#ff0000">
+<IMG SRC="../../../boost.png"
+ ALT="C++ Boost" width="277" height="86">
+
+<BR Clear>
+
+<H1><A NAME="sec:successive_shortest_path_nonnegative_weights">
+<TT>successive_shortest_path_nonnegative_weights</TT>
+</H1>
+
+<PRE>
+<i>// named parameter version</i>
+template <class Graph, class P, class T, class R>
+void successive_shortest_path_nonnegative_weights(
+ Graph &g,
+ typename graph_traits<Graph>::vertex_descriptor s,
+ typename graph_traits<Graph>::vertex_descriptor t,
+ const bgl_named_params<P, T, R> & params = <i>all defaults</i>)
+
+<i>// non-named parameter version</i>
+template <class Graph, class Capacity, class ResidualCapacity, class Reversed, class Pred, class Weight, class Distance, class Distance2, class VertexIndex>
+void successive_shortest_path_nonnegative_weights(
+ const Graph & g,
+ typename graph_traits<Graph>::vertex_descriptor s,
+ typename graph_traits<Graph>::vertex_descriptor t,
+ Capacity capacity,
+ ResidualCapacity residual_capacity,
+ Weight weight,
+ Reversed rev,
+ VertexIndex index,
+ Pred pred,
+ Distance distance,
+ Distance2 distance_prev)
+</PRE>
+
+<P>
+The <tt>successive_shortest_path_nonnegative_weights()</tt> function calculates the minimum cost 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 function calculates the flow values <i>f(u,v)</i> for all <i>(u,v)</i> in
+<i>E</i>, which are returned in the form of the residual capacity
+<i>r(u,v) = c(u,v) - f(u,v)</i>.
+
+<p>
+There are several special requirements on the input graph and property
+map parameters for this algorithm. First, the directed graph
+<i>G=(V,E)</i> that represents the network must be augmented to
+include the reverse edge for every edge in <i>E</i>. That is, the
+input graph should be <i>G<sub>in</sub> = (V,{E U
+E<sup>T</sup>})</i>. The <tt>ReverseEdgeMap</tt> argument <tt>rev</tt>
+must map each edge in the original graph to its reverse edge, that is
+<i>(u,v) -> (v,u)</i> for all <i>(u,v)</i> in <i>E</i>. The
+<tt>CapacityEdgeMap</tt> argument <tt>cap</tt> must map each edge in
+<i>E</i> to a positive number, and each edge in <i>E<sup>T</sup></i>
+to 0. The <tt>WeightMap</tt> has to map each edge from <i>E</i> to nonnegative number, and each edge from <i>E<sup>T</sup></i> to <i>-weight</i> of its reversed edge.
+
+<p>
+The algorithm is described in <a
+href="./bibliography.html#ahuja93:_network_flows">Network Flows</a>.
+
+<p>
+This algorithm starts with empty flow and in each round augments the shortest path (in terms of weight) in the residual graph.
+
+<p>
+In order to find the cost of the result flow use:
+find_flow_cost().
+
+<H3>Where Defined</H3>
+
+<P>
+boost/graph/successive_shortest_path_nonnegative_weights.hpp
+
+<P>
+
+<h3>Parameters</h3>
+
+IN: <tt>Graph& g</tt>
+<blockquote>
+ A directed graph. The
+ graph's type must be a model of <a
+ href="./VertexListGraph.html">VertexListGraph</a> and IncidenceGraph For each edge
+ <i>(u,v)</i> in the graph, the reverse edge <i>(v,u)</i> must also
+ be in the graph.
+</blockquote>
+
+IN: <tt>vertex_descriptor s</tt>
+<blockquote>
+ The source vertex for the flow network graph.
+</blockquote>
+
+IN: <tt>vertex_descriptor t</tt>
+<blockquote>
+ The sink vertex for the flow network graph.
+</blockquote>
+
+<h3>Named Parameters</h3>
+
+
+IN: <tt>capacity_map(CapacityEdgeMap cap)</tt>
+<blockquote>
+ The edge capacity property map. The type must be a model of a
+ constant <a
+ href="../../property_map/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>
+
+OUT: <tt>residual_capacity_map(ResidualCapacityEdgeMap res)</tt>
+<blockquote>
+ This maps edges to their residual capacity. The type must be a model
+ of a mutable <a
+ href="../../property_map/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>
+
+IN: <tt>reverse_edge_map(ReverseEdgeMap rev)</tt>
+<blockquote>
+ An edge property map that maps every edge <i>(u,v)</i> in the graph
+ to the reverse edge <i>(v,u)</i>. The map must be a model of
+ constant <a href="../../property_map/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>
+
+IN: <tt>weight_map(WeightMap w_map)</tt>
+<blockquote>
+ The weight or ``cost'' of each edge in the graph. The weights
+ must all be non-negative, and the algorithm will throw a
+ negative_edge
+ exception if one of the edges is negative.
+ The type <tt>WeightMap</tt> must be a model of
+ Readable Property Map. The edge descriptor type of
+ the graph needs to be usable as the key type for the weight
+ map. The value type for this map must be
+ the same as the value type of the distance map.<br>
+ <b>Default:</b> <tt>get(edge_weight, g)</tt><br>
+
+</blockquote>
+
+UTIL: <tt>predecessor_map(PredEdgeMap pred)</tt>
+<blockquote>
+ Use by the algorithm to store augmenting paths. The map must be a
+ model of mutable <a
+ href="../../property_map/doc/LvaluePropertyMap.html">Lvalue Property Map</a>.
+ The key type must be the graph's vertex descriptor type and the
+ value type must be the graph's edge descriptor type.<br>
+
+ <b>Default:</b> an <a
+ href="../../property_map/doc/iterator_property_map.html">
+ <tt>iterator_property_map</tt></a> created from a <tt>std::vector</tt>
+ of edge descriptors of size <tt>num_vertices(g)</tt> and
+ using the <tt>i_map</tt> for the index map.
+</blockquote>
+
+UTIL: <tt>distance_map(DistanceMap d_map)</tt>
+<blockquote>
+ The shortest path weight from the source vertex <tt>s</tt> to each
+ vertex in the graph <tt>g</tt> is recorded in this property map. The
+ shortest path weight is the sum of the edge weights along the
+ shortest path. The type <tt>DistanceMap</tt> must be a model of <a
+ href="../../property_map/doc/ReadWritePropertyMap.html">Read/Write
+ Property Map</a>. The vertex descriptor type of the graph needs to
+ be usable as the key type of the distance map.
+
+ <b>Default:</b> <a
+ href="../../property_map/doc/iterator_property_map.html">
+ <tt>iterator_property_map</tt></a> created from a
+ <tt>std::vector</tt> of the <tt>WeightMap</tt>'s value type of size
+ <tt>num_vertices(g)</tt> and using the <tt>i_map</tt> for the index
+ map.<br>
+
+</blockquote>
+
+UTIL: <tt>distance_map2(DistanceMap2 d_map2)</tt>
+<blockquote>
+ The shortest path computation in iteration nr <i>k</i> uses distances computed in iteration <i>k</i>.
+ The type <tt>DistanceMap2</tt> must be a model of <a
+ href="../../property_map/doc/ReadWritePropertyMap.html">Read/Write
+ Property Map</a>. The vertex descriptor type of the graph needs to
+ be usable as the key type of the distance map.
+
+ <b>Default:</b> <a
+ href="../../property_map/doc/iterator_property_map.html">
+ <tt>iterator_property_map</tt></a> created from a
+ <tt>std::vector</tt> of the <tt>WeightMap</tt>'s value type of size
+ <tt>num_vertices(g)</tt> and using the <tt>i_map</tt> for the index
+ map.<br>
+
+</blockquote>
+
+IN: <tt>vertex_index_map(VertexIndexMap i_map)</tt>
+<blockquote>
+ Maps each vertex of the graph to a unique integer in the range
+ <tt>[0, num_vertices(g))</tt>. This property map is only needed
+ if the default for the distance or distance2 or predecessor map is used.
+ The vertex index map must be a model of <a
+ href="../../property_map/doc/ReadablePropertyMap.html">Readable Property
+ Map</a>. The key type of the map must be the graph's vertex
+ descriptor type.<br>
+ <b>Default:</b> <tt>get(vertex_index, g)</tt>
+ Note: if you use this default, make sure your graph has
+ an internal <tt>vertex_index</tt> property. For example,
+ <tt>adjacenty_list</tt> with <tt>VertexList=listS</tt> does
+ not have an internal <tt>vertex_index</tt> property.
+</blockquote>
+
+
+<h3>Complexity</h3>
+In the integer capacity case, if <i>U</i> is the value of the max flow, then the complexity is <i> O(U * (|E| + |V|*log|V|))</i>,
+where <i>O(|E| + |V|*log|V|)</i> is the complexity of the dijkstra algorithm and <i>U</i> is upper bound on number of iteration.
+In many real world cases number of iterations is much smaller than <i>U</i>.
+
+
+<h3>Example</h3>
+
+The program in <a
+href="../example/successive_shortest_path_nonnegative_weights_example.cpp"><tt>example/successive_shortest_path_nonnegative_weights_example.cpp</tt></a>.
+
+<h3>See Also</h3>
+
+cycle_canceling()<br>
+find_flow_cost().
+
+<br>
+<HR>
+<TABLE>
+<TR valign=top>
+<TD nowrap>Copyright © 2013</TD><TD>
+Piotr Wygocki, University of Warsaw (<A HREF="mailto:wygos_at_[hidden]">wygos at mimuw.edu.pl</A>)
+</TD></TR></TABLE>
+
+</BODY>
+</HTML>
+<!-- LocalWords: HTML Siek Edmonds BGCOLOR ffffff ee VLINK ALINK ff IMG SRC
+ -->
+<!-- LocalWords: gif ALT BR sec edmonds karp TT DIV CELLPADDING TR TD PRE lt
+ -->
+<!-- LocalWords: typename VertexListGraph CapacityEdgeMap ReverseEdgeMap gt
+ -->
+<!-- LocalWords: ResidualCapacityEdgeMap VertexIndexMap src rev ColorMap pred
+ -->
+<!-- LocalWords: PredEdgeMap tt href html hpp ul li nbsp br LvaluePropertyMap
+ -->
+<!-- LocalWords: num ColorValue DIMACS cpp pre config iostream dimacs int std
+ -->
+<!-- LocalWords: namespace vecS directedS cout endl iter ei HR valign nowrap
+ -->
+<!-- LocalWords: jeremy siek htm Univ mailto jsiek lsc edu
+p -->
+
Modified: branches/release/libs/graph/doc/table_of_contents.html
==============================================================================
--- branches/release/libs/graph/doc/table_of_contents.html Sat Sep 21 15:26:42 2013 (r85812)
+++ branches/release/libs/graph/doc/table_of_contents.html 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -214,6 +214,12 @@
<li>boykov_kolmogorov_max_flow</li>
<LI>edmonds_maximum_cardinality_matching
</OL>
+ <LI>Minimum Cost Maximum Flow Algorithms
+ <OL>
+ <LI>cycle_canceling
+ <LI>successive_shortest_path_nonnegative_weights
+ <li>find_flow_cost</li>
+ </OL>
<LI>Minimum Cut Algorithms
<OL>
<LI>stoer_wagner_min_cut
@@ -284,10 +290,12 @@
<li>Miscellaneous Algorithms
<ol>
<li>metric_tsp_approx</li>
- <LI>sequential_vertex_coloring
- <LI>is_bipartite (including two-coloring of bipartite graphs)
- <LI>find_odd_cycle
- <LI>maximum_adjacency_search
+ <LI>sequential_vertex_coloring</li>
+ <LI>edge_coloring</li>
+ <LI>is_bipartite (including two-coloring of bipartite graphs)</li>
+ <LI>find_odd_cycle</li>
+ <LI>maximum_adjacency_search</li>
+ <LI>hawick_circuits (find all circuits of a directed graph)</li>
</ol>
</li>
Modified: branches/release/libs/graph/doc/undirected_dfs.html
==============================================================================
--- branches/release/libs/graph/doc/undirected_dfs.html Sat Sep 21 15:26:42 2013 (r85812)
+++ branches/release/libs/graph/doc/undirected_dfs.html 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -7,7 +7,7 @@
http://www.boost.org/LICENSE_1_0.txt)
-->
<Head>
-<Title>Boost Graph Library: Depth-First Search</Title>
+<Title>Boost Graph Library: Undirected Depth-First Search</Title>
<BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b"
ALINK="#ff0000">
<IMG SRC="../../../boost.png"
@@ -116,6 +116,7 @@
<b>call</b> DFS-VISIT(<i>G</i>, <i>v</i>)
<b>else if</b> (<i>vcolor[v] =</i> GRAY and <i>ec =</i> WHITE)
<i>...</i>
+ <i>...</i>
<b>end for</b>
<i>vcolor[u] :=</i> BLACK
<i>f_time[u] := time := time + 1</i>
@@ -152,6 +153,8 @@
<i>(u,v)</i> is a back edge
-
-
+finish edge <i>(u,v)</i>
+-
finish vertex <i>u</i>
-
</pre>
@@ -291,6 +294,9 @@
<li><b><tt>vis.back_edge(e, g)</tt></b> is invoked on the back edges in
the graph.
+<li><b><tt>vis.finish_edge(e, g)</tt></b> is invoked on the back edges in
+ the graph as well as on each tree edge after its target vertex is finished.
+
<li><b><tt>vis.finish_vertex(u, g)</tt></b> is invoked on a vertex after
all of its out edges have been added to the search tree and all of
the adjacent vertices have been discovered (but before their
Modified: branches/release/libs/graph/example/Jamfile.v2
==============================================================================
--- branches/release/libs/graph/example/Jamfile.v2 Sat Sep 21 15:26:42 2013 (r85812)
+++ branches/release/libs/graph/example/Jamfile.v2 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -50,4 +50,8 @@
exe vf2_sub_graph_iso_example : vf2_sub_graph_iso_example.cpp ;
exe vf2_sub_graph_iso_multi_example : vf2_sub_graph_iso_multi_example.cpp ;
exe sloan_ordering : sloan_ordering.cpp ;
+exe hawick_circuits : hawick_circuits.cpp ;
+exe edge_coloring : edge_coloring.cpp ;
+exe successive_shortest_path_nonnegative_weights_example : successive_shortest_path_nonnegative_weights_example.cpp ;
+exe cycle_canceling_example : cycle_canceling_example.cpp ;
Modified: branches/release/libs/graph/example/astar-cities.cpp
==============================================================================
--- branches/release/libs/graph/example/astar-cities.cpp Sat Sep 21 15:26:42 2013 (r85812)
+++ branches/release/libs/graph/example/astar-cities.cpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -118,7 +118,6 @@
typedef property_map<mygraph_t, edge_weight_t>::type WeightMap;
typedef mygraph_t::vertex_descriptor vertex;
typedef mygraph_t::edge_descriptor edge_descriptor;
- typedef mygraph_t::vertex_iterator vertex_iterator;
typedef std::pair<int, int> edge;
// specify data
@@ -196,7 +195,8 @@
(g, start,
distance_heuristic<mygraph_t, cost, location*>
(locations, goal),
- predecessor_map(&p[0]).distance_map(&d[0]).
+ predecessor_map(make_iterator_property_map(p.begin(), get(vertex_index, g))).
+ distance_map(make_iterator_property_map(d.begin(), get(vertex_index, g))).
visitor(astar_goal_visitor<vertex>(goal)));
Modified: branches/release/libs/graph/example/bfs-example.cpp
==============================================================================
--- branches/release/libs/graph/example/bfs-example.cpp Sat Sep 21 15:26:42 2013 (r85812)
+++ branches/release/libs/graph/example/bfs-example.cpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -54,15 +54,18 @@
#endif
// Typedefs
- typedef graph_traits < graph_t >::vertex_descriptor Vertex;
typedef graph_traits < graph_t >::vertices_size_type Size;
- typedef Size* Iiter;
// a vector to hold the discover time property for each vertex
std::vector < Size > dtime(num_vertices(g));
+ typedef
+ iterator_property_map<std::vector<Size>::iterator,
+ property_map<graph_t, vertex_index_t>::const_type>
+ dtime_pm_type;
+ dtime_pm_type dtime_pm(dtime.begin(), get(vertex_index, g));
Size time = 0;
- bfs_time_visitor < Size * >vis(&dtime[0], time);
+ bfs_time_visitor < dtime_pm_type >vis(dtime_pm, time);
breadth_first_search(g, vertex(s, g), visitor(vis));
// Use std::sort to order the vertices by their discover time
@@ -70,7 +73,7 @@
integer_range < int >range(0, N);
std::copy(range.begin(), range.end(), discover_order.begin());
std::sort(discover_order.begin(), discover_order.end(),
- indirect_cmp < Iiter, std::less < Size > >(&dtime[0]));
+ indirect_cmp < dtime_pm_type, std::less < Size > >(dtime_pm));
std::cout << "order of discovery: ";
for (int i = 0; i < N; ++i)
Modified: branches/release/libs/graph/example/bfs-example2.cpp
==============================================================================
--- branches/release/libs/graph/example/bfs-example2.cpp Sat Sep 21 15:26:42 2013 (r85812)
+++ branches/release/libs/graph/example/bfs-example2.cpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -9,6 +9,7 @@
#include <boost/graph/breadth_first_search.hpp>
#include <boost/pending/indirect_cmp.hpp>
#include <boost/range/irange.hpp>
+#include <boost/property_map/property_map.hpp>
#include <iostream>
@@ -30,6 +31,7 @@
struct VertexProps {
boost::default_color_type color;
std::size_t discover_time;
+ unsigned int index;
};
int
@@ -63,9 +65,7 @@
#endif
// Typedefs
- typedef graph_traits<graph_t>::vertex_descriptor Vertex;
typedef graph_traits<graph_t>::vertices_size_type Size;
- typedef Size* Iiter;
Size time = 0;
typedef property_map<graph_t, std::size_t VertexProps::*>::type dtime_map_t;
@@ -76,17 +76,28 @@
// a vector to hold the discover time property for each vertex
std::vector < Size > dtime(num_vertices(g));
+ typedef
+ iterator_property_map<std::vector<Size>::iterator,
+ property_map<graph_t, unsigned int VertexProps::*>::type>
+ dtime_pm_type;
graph_traits<graph_t>::vertex_iterator vi, vi_end;
std::size_t c = 0;
- for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi, ++c)
+ for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi, ++c) {
dtime[c] = dtime_map[*vi];
+ put(&VertexProps::index, g, *vi, c);
+ }
+ dtime_pm_type dtime_pm(dtime.begin(), get(&VertexProps::index, g));
// Use std::sort to order the vertices by their discover time
std::vector<graph_traits<graph_t>::vertices_size_type > discover_order(N);
integer_range < int >range(0, N);
std::copy(range.begin(), range.end(), discover_order.begin());
std::sort(discover_order.begin(), discover_order.end(),
- indirect_cmp < Iiter, std::less < Size > >(&dtime[0]));
+ make_indirect_cmp(
+ std::less<Size>(),
+ make_iterator_property_map(
+ dtime.begin(),
+ typed_identity_property_map<std::size_t>())));
std::cout << "order of discovery: ";
for (int i = 0; i < N; ++i)
Modified: branches/release/libs/graph/example/canonical_ordering.cpp
==============================================================================
--- branches/release/libs/graph/example/canonical_ordering.cpp Sat Sep 21 15:26:42 2013 (r85812)
+++ branches/release/libs/graph/example/canonical_ordering.cpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -64,7 +64,8 @@
std::vector<vec_t> embedding(num_vertices(g));
if (boyer_myrvold_planarity_test(boyer_myrvold_params::graph = g,
boyer_myrvold_params::embedding =
- &embedding[0]
+ make_iterator_property_map(
+ embedding.begin(), get(vertex_index, g))
)
)
std::cout << "Input graph is planar" << std::endl;
@@ -75,7 +76,10 @@
ordering_storage_t;
ordering_storage_t ordering;
- planar_canonical_ordering(g, &embedding[0], std::back_inserter(ordering));
+ planar_canonical_ordering(g,
+ make_iterator_property_map(
+ embedding.begin(), get(vertex_index, g)),
+ std::back_inserter(ordering));
ordering_storage_t::iterator oi, oi_end;
oi_end = ordering.end();
Copied and modified: branches/release/libs/graph/example/cycle_canceling_example.cpp (from r85536, trunk/libs/graph/example/cycle_canceling_example.cpp)
==============================================================================
--- trunk/libs/graph/example/cycle_canceling_example.cpp Sat Aug 31 16:09:11 2013 (r85536, copy source)
+++ branches/release/libs/graph/example/cycle_canceling_example.cpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -1,3 +1,12 @@
+//=======================================================================
+// Copyright 2013 University of Warsaw.
+// Authors: Piotr Wygocki
+//
+// Distributed under the Boost Software License, Version 1.0. (See
+// accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+//=======================================================================
+
#include <boost/graph/cycle_canceling.hpp>
#include <boost/graph/edmonds_karp_max_flow.hpp>
@@ -5,9 +14,9 @@
int main() {
- unsigned s,t;
- boost::SampleGraph::Graph g
- = boost::SampleGraph::getSampleGraph(s, t);
+ boost::SampleGraph::vertex_descriptor s,t;
+ boost::SampleGraph::Graph g;
+ boost::SampleGraph::getSampleGraph(g, s, t);
boost::edmonds_karp_max_flow(g, s, t);
boost::cycle_canceling(g);
Modified: branches/release/libs/graph/example/dfs-example.cpp
==============================================================================
--- branches/release/libs/graph/example/dfs-example.cpp Sat Sep 21 15:26:42 2013 (r85812)
+++ branches/release/libs/graph/example/dfs-example.cpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -58,15 +58,17 @@
graph_t g(edge_array, edge_array + sizeof(edge_array) / sizeof(E), N);
#endif
- // Typedefs
- typedef boost::graph_traits < graph_t >::vertex_descriptor Vertex;
- typedef size_type* Iiter;
-
// discover time and finish time properties
std::vector < size_type > dtime(num_vertices(g));
std::vector < size_type > ftime(num_vertices(g));
+ typedef
+ iterator_property_map<std::vector<size_type>::iterator,
+ property_map<graph_t, vertex_index_t>::const_type>
+ time_pm_type;
+ time_pm_type dtime_pm(dtime.begin(), get(vertex_index, g));
+ time_pm_type ftime_pm(ftime.begin(), get(vertex_index, g));
size_type t = 0;
- dfs_time_visitor < size_type * >vis(&dtime[0], &ftime[0], t);
+ dfs_time_visitor < time_pm_type >vis(dtime_pm, ftime_pm, t);
depth_first_search(g, visitor(vis));
@@ -75,7 +77,7 @@
integer_range < size_type > r(0, N);
std::copy(r.begin(), r.end(), discover_order.begin());
std::sort(discover_order.begin(), discover_order.end(),
- indirect_cmp < Iiter, std::less < size_type > >(&dtime[0]));
+ indirect_cmp < time_pm_type, std::less < size_type > >(dtime_pm));
std::cout << "order of discovery: ";
int i;
for (i = 0; i < N; ++i)
@@ -84,7 +86,7 @@
std::vector < size_type > finish_order(N);
std::copy(r.begin(), r.end(), finish_order.begin());
std::sort(finish_order.begin(), finish_order.end(),
- indirect_cmp < Iiter, std::less < size_type > >(&ftime[0]));
+ indirect_cmp < time_pm_type, std::less < size_type > >(ftime_pm));
std::cout << std::endl << "order of finish: ";
for (i = 0; i < N; ++i)
std::cout << name[finish_order[i]] << " ";
Modified: branches/release/libs/graph/example/dfs.cpp
==============================================================================
--- branches/release/libs/graph/example/dfs.cpp Sat Sep 21 15:26:42 2013 (r85812)
+++ branches/release/libs/graph/example/dfs.cpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -27,12 +27,18 @@
Tree edge: 0 --> 2
Tree edge: 2 --> 1
Back edge: 1 --> 1
+ Finish edge: 1 --> 1
Tree edge: 1 --> 3
Back edge: 3 --> 1
+ Finish edge: 3 --> 1
Tree edge: 3 --> 4
Back edge: 4 --> 0
+ Finish edge: 4 --> 0
Back edge: 4 --> 1
+ Finish edge: 4 --> 1
Forward or cross edge: 2 --> 3
+ Finish edge: 2 --> 3
+ Finish edge: 0 --> 2
1 10
3 8
2 9
@@ -69,6 +75,12 @@
<< " --> " << target(e, G) << endl;
Base::forward_or_cross_edge(e, G);
}
+ template <class Edge, class Graph>
+ void finish_edge(Edge e, Graph& G) {
+ cout << "Finish edge: " << source(e, G) <<
+ " --> " << target(e, G) << endl;
+ Base::finish_edge(e, G);
+ }
};
template <class VisitorList>
edge_categorizer<VisitorList>
Modified: branches/release/libs/graph/example/dfs.expected
==============================================================================
--- branches/release/libs/graph/example/dfs.expected Sat Sep 21 15:26:42 2013 (r85812)
+++ branches/release/libs/graph/example/dfs.expected 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -1,12 +1,18 @@
Tree edge: 0 --> 2
Tree edge: 2 --> 1
Back edge: 1 --> 1
+Finish edge: 1 --> 1
Tree edge: 1 --> 3
Back edge: 3 --> 1
+Finish edge: 3 --> 1
Tree edge: 3 --> 4
Back edge: 4 --> 0
+Finish edge: 4 --> 0
Back edge: 4 --> 1
+Finish edge: 4 --> 1
Forward or cross edge: 2 --> 3
+Finish edge: 2 --> 3
+Finish edge: 0 --> 2
1 10
3 8
2 9
Modified: branches/release/libs/graph/example/dijkstra-example-listS.cpp
==============================================================================
--- branches/release/libs/graph/example/dijkstra-example-listS.cpp Sat Sep 21 15:26:42 2013 (r85812)
+++ branches/release/libs/graph/example/dijkstra-example-listS.cpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -26,7 +26,6 @@
property<vertex_distance_t, int,
property<vertex_predecessor_t, vertex_descriptor> > > >,
property<edge_weight_t, int> > graph_t;
- typedef graph_traits<graph_t>::edge_descriptor edge_descriptor;
typedef std::pair<int, int> Edge;
const int num_nodes = 5;
Modified: branches/release/libs/graph/example/dijkstra-example.cpp
==============================================================================
--- branches/release/libs/graph/example/dijkstra-example.cpp Sat Sep 21 15:26:42 2013 (r85812)
+++ branches/release/libs/graph/example/dijkstra-example.cpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -22,7 +22,6 @@
typedef adjacency_list < listS, vecS, directedS,
no_property, property < edge_weight_t, int > > graph_t;
typedef graph_traits < graph_t >::vertex_descriptor vertex_descriptor;
- typedef graph_traits < graph_t >::edge_descriptor edge_descriptor;
typedef std::pair<int, int> Edge;
const int num_nodes = 5;
Modified: branches/release/libs/graph/example/dijkstra-no-color-map-example.cpp
==============================================================================
--- branches/release/libs/graph/example/dijkstra-no-color-map-example.cpp Sat Sep 21 15:26:42 2013 (r85812)
+++ branches/release/libs/graph/example/dijkstra-no-color-map-example.cpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -26,7 +26,6 @@
typedef adjacency_list < listS, vecS, directedS,
no_property, property < edge_weight_t, int > > graph_t;
typedef graph_traits < graph_t >::vertex_descriptor vertex_descriptor;
- typedef graph_traits < graph_t >::edge_descriptor edge_descriptor;
typedef std::pair<int, int> Edge;
const int num_nodes = 5;
Copied: branches/release/libs/graph/example/edge_coloring.cpp (from r85534, trunk/libs/graph/example/edge_coloring.cpp)
==============================================================================
--- /dev/null 00:00:00 1970 (empty, because file is newly added)
+++ branches/release/libs/graph/example/edge_coloring.cpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813, copy of r85534, trunk/libs/graph/example/edge_coloring.cpp)
@@ -0,0 +1,70 @@
+//=======================================================================
+// Copyright 2013 Maciej Piechotka
+// Authors: Maciej Piechotka
+//
+// Distributed under the Boost Software License, Version 1.0. (See
+// accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+//=======================================================================
+
+#include <boost/config.hpp>
+#include <boost/graph/adjacency_list.hpp>
+#include <boost/graph/edge_coloring.hpp>
+#include <boost/graph/properties.hpp>
+
+/*
+ Sample output
+ Colored using 5 colors
+ a-d: 4
+ a-f: 0
+ b-c: 2
+ b-e: 3
+ b-g: 1
+ b-j: 0
+ c-d: 0
+ c-e: 1
+ d-f: 2
+ d-i: 1
+ e-g: 4
+ f-g: 3
+ f-h: 1
+ g-h: 0
+*/
+
+int main(int, char *[])
+{
+ using namespace boost;
+ using namespace std;
+ typedef adjacency_list<vecS, vecS, undirectedS, no_property, size_t, no_property> Graph;
+
+ typedef std::pair<std::size_t, std::size_t> Pair;
+ Pair edges[14] = { Pair(0,3), //a-d
+ Pair(0,5), //a-f
+ Pair(1,2), //b-c
+ Pair(1,4), //b-e
+ Pair(1,6), //b-g
+ Pair(1,9), //b-j
+ Pair(2,3), //c-d
+ Pair(2,4), //c-e
+ Pair(3,5), //d-f
+ Pair(3,8), //d-i
+ Pair(4,6), //e-g
+ Pair(5,6), //f-g
+ Pair(5,7), //f-h
+ Pair(6,7) }; //g-h
+
+ Graph G(10);
+
+ for (size_t i = 0; i < sizeof(edges)/sizeof(edges[0]); i++)
+ add_edge(edges[i].first, edges[i].second, G).first;
+
+ size_t colors = edge_coloring(G, get(edge_bundle, G));
+
+ cout << "Colored using " << colors << " colors" << endl;
+ for (size_t i = 0; i < sizeof(edges)/sizeof(edges[0]); i++) {
+ cout << " " << (char)('a' + edges[i].first) << "-" << (char)('a' + edges[i].second) << ": " << G[edge(edges[i].first, edges[i].second, G).first] << endl;
+ }
+
+ return 0;
+}
+
Copied: branches/release/libs/graph/example/hawick_circuits.cpp (from r85533, trunk/libs/graph/example/hawick_circuits.cpp)
==============================================================================
--- /dev/null 00:00:00 1970 (empty, because file is newly added)
+++ branches/release/libs/graph/example/hawick_circuits.cpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813, copy of r85533, trunk/libs/graph/example/hawick_circuits.cpp)
@@ -0,0 +1,96 @@
+// Copyright Louis Dionne 2013
+
+// Use, modification and distribution is subject to the Boost Software
+// License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy
+// at http://www.boost.org/LICENSE_1_0.txt)
+
+#include <boost/assert.hpp>
+#include <boost/graph/directed_graph.hpp>
+#include <boost/graph/graph_traits.hpp>
+#include <boost/graph/hawick_circuits.hpp>
+#include <boost/lexical_cast.hpp>
+#include <boost/next_prior.hpp>
+#include <boost/property_map/property_map.hpp>
+#include <cstdlib>
+#include <iostream>
+#include <iterator>
+#include <map>
+
+
+template <typename OutputStream>
+struct cycle_printer
+{
+ cycle_printer(OutputStream& stream)
+ : os(stream)
+ { }
+
+ template <typename Path, typename Graph>
+ void cycle(Path const& p, Graph const& g)
+ {
+ if (p.empty())
+ return;
+
+ // Get the property map containing the vertex indices
+ // so we can print them.
+ typedef typename boost::property_map<
+ Graph, boost::vertex_index_t
+ >::const_type IndexMap;
+
+ IndexMap indices = get(boost::vertex_index, g);
+
+ // Iterate over path printing each vertex that forms the cycle.
+ typename Path::const_iterator i, before_end = boost::prior(p.end());
+ for (i = p.begin(); i != before_end; ++i) {
+ os << get(indices, *i) << " ";
+ }
+ os << get(indices, *i) << '\n';
+ }
+ OutputStream& os;
+};
+
+
+// VertexPairIterator is an iterator over pairs of whitespace separated
+// vertices `u` and `v` representing a directed edge from `u` to `v`.
+template <typename Graph, typename VertexPairIterator>
+void build_graph(Graph& graph, unsigned int const nvertices,
+ VertexPairIterator first, VertexPairIterator last) {
+ typedef boost::graph_traits<Graph> Traits;
+ typedef typename Traits::vertex_descriptor vertex_descriptor;
+ std::map<unsigned int, vertex_descriptor> vertices;
+
+ for (unsigned int i = 0; i < nvertices; ++i)
+ vertices[i] = add_vertex(graph);
+
+ for (; first != last; ++first) {
+ unsigned int u = *first++;
+
+ BOOST_ASSERT_MSG(first != last,
+ "there is a lonely vertex at the end of the edge list");
+
+ unsigned int v = *first;
+
+ BOOST_ASSERT_MSG(vertices.count(u) == 1 && vertices.count(v) == 1,
+ "specified a vertex over the number of vertices in the graph");
+
+ add_edge(vertices[u], vertices[v], graph);
+ }
+ BOOST_ASSERT(num_vertices(graph) == nvertices);
+}
+
+
+int main(int argc, char const* argv[]) {
+ if (argc < 2) {
+ std::cout << "usage: " << argv[0] << " num_vertices < input\n";
+ return EXIT_FAILURE;
+ }
+
+ unsigned int num_vertices = boost::lexical_cast<unsigned int>(argv[1]);
+ std::istream_iterator<unsigned int> first_vertex(std::cin), last_vertex;
+ boost::directed_graph<> graph;
+ build_graph(graph, num_vertices, first_vertex, last_vertex);
+
+ cycle_printer<std::ostream> visitor(std::cout);
+ boost::hawick_circuits(graph, visitor);
+
+ return EXIT_SUCCESS;
+}
Modified: branches/release/libs/graph/example/implicit_graph.cpp
==============================================================================
--- branches/release/libs/graph/example/implicit_graph.cpp Sat Sep 21 15:26:42 2013 (r85812)
+++ branches/release/libs/graph/example/implicit_graph.cpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -527,10 +527,16 @@
vertex_descriptor source = 0;
std::vector<vertex_descriptor> pred(num_vertices(g));
std::vector<edge_weight_map_value_type> dist(num_vertices(g));
+ iterator_property_map<std::vector<vertex_descriptor>::iterator,
+ property_map<ring_graph, vertex_index_t>::const_type>
+ pred_pm(pred.begin(), get(vertex_index, g));
+ iterator_property_map<std::vector<edge_weight_map_value_type>::iterator,
+ property_map<ring_graph, vertex_index_t>::const_type>
+ dist_pm(dist.begin(), get(vertex_index, g));
dijkstra_shortest_paths(g, source,
- predecessor_map(&pred[0]).
- distance_map(&dist[0]) );
+ predecessor_map(pred_pm).
+ distance_map(dist_pm) );
std::cout << "Dijkstra search from vertex " << source << std::endl;
for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) {
Modified: branches/release/libs/graph/example/mcgregor_subgraphs_example.cpp
==============================================================================
--- branches/release/libs/graph/example/mcgregor_subgraphs_example.cpp Sat Sep 21 15:26:42 2013 (r85812)
+++ branches/release/libs/graph/example/mcgregor_subgraphs_example.cpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -76,11 +76,7 @@
property<vertex_index_t, unsigned int> >,
property<edge_name_t, unsigned int> > Graph;
- typedef graph_traits<Graph>::vertex_descriptor Vertex;
- typedef graph_traits<Graph>::edge_descriptor Edge;
-
typedef property_map<Graph, vertex_name_t>::type VertexNameMap;
- typedef property_map<Graph, edge_name_t>::type EdgeNameMap;
// Test maximum and unique variants on known graphs
Graph graph_simple1, graph_simple2;
Modified: branches/release/libs/graph/example/stoer_wagner.cpp
==============================================================================
--- branches/release/libs/graph/example/stoer_wagner.cpp Sat Sep 21 15:26:42 2013 (r85812)
+++ branches/release/libs/graph/example/stoer_wagner.cpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -27,7 +27,6 @@
typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS,
boost::no_property, boost::property<boost::edge_weight_t, int> > undirected_graph;
- typedef boost::graph_traits<undirected_graph>::vertex_descriptor vertex_descriptor;
typedef boost::property_map<undirected_graph, boost::edge_weight_t>::type weight_map_type;
typedef boost::property_traits<weight_map_type>::value_type weight_type;
Modified: branches/release/libs/graph/example/subgraph.cpp
==============================================================================
--- branches/release/libs/graph/example/subgraph.cpp Sat Sep 21 15:26:42 2013 (r85812)
+++ branches/release/libs/graph/example/subgraph.cpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -41,7 +41,6 @@
int main(int,char*[])
{
using namespace boost;
- typedef adjacency_list_traits<vecS, vecS, directedS> Traits;
typedef subgraph< adjacency_list<vecS, vecS, directedS,
property<vertex_color_t, int>, property<edge_index_t, int> > > Graph;
Copied and modified: branches/release/libs/graph/example/successive_shortest_path_nonnegative_weights_example.cpp (from r85568, trunk/libs/graph/example/successive_shortest_path_nonnegative_weights_example.cpp)
==============================================================================
--- trunk/libs/graph/example/successive_shortest_path_nonnegative_weights_example.cpp Wed Sep 4 17:39:21 2013 (r85568, copy source)
+++ branches/release/libs/graph/example/successive_shortest_path_nonnegative_weights_example.cpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -14,9 +14,9 @@
int main() {
- unsigned s,t;
- boost::SampleGraph::Graph g
- = boost::SampleGraph::getSampleGraph(s, t);
+ boost::SampleGraph::vertex_descriptor s,t;
+ boost::SampleGraph::Graph g;
+ boost::SampleGraph::getSampleGraph(g, s, t);
boost::successive_shortest_path_nonnegative_weights(g, s, t);
Modified: branches/release/libs/graph/test/Jamfile.v2
==============================================================================
--- branches/release/libs/graph/test/Jamfile.v2 Sat Sep 21 15:26:42 2013 (r85812)
+++ branches/release/libs/graph/test/Jamfile.v2 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -43,6 +43,7 @@
[ run csr_graph_test.cpp : : : : : <variant>release ]
[ run dag_longest_paths.cpp ]
[ run dfs.cpp ../../test/build//boost_test_exec_monitor ]
+ [ run undirected_dfs.cpp ../../test/build//boost_test_exec_monitor ]
[ compile dfs_cc.cpp ]
[ compile dijkstra_cc.cpp ]
[ run dijkstra_heap_performance.cpp : 10000 ]
@@ -103,6 +104,7 @@
../../system/build
: $(PLANAR_INPUT_FILES) ]
[ run r_c_shortest_paths_test.cpp ]
+ [ run rcsp_custom_vertex_id.cpp ]
[ run is_straight_line_draw_test.cpp ]
[ run metric_tsp_approx.cpp : metric_tsp_approx.graph ]
[ compile dimacs.cpp ]
@@ -126,6 +128,9 @@
[ run stoer_wagner_test.cpp ../../test/build//boost_unit_test_framework/<link>static : $(TEST_DIR) ]
[ compile filtered_graph_properties_dijkstra.cpp ]
[ run vf2_sub_graph_iso_test.cpp ]
+ [ run hawick_circuits.cpp ]
+ [ run successive_shortest_path_nonnegative_weights_test.cpp ../../test/build//boost_unit_test_framework/<link>static ]
+ [ run cycle_canceling_test.cpp ../../test/build//boost_unit_test_framework/<link>static ]
;
# Run SDB tests only when -sSDB= is set.
Modified: branches/release/libs/graph/test/adj_list_loops.cpp
==============================================================================
--- branches/release/libs/graph/test/adj_list_loops.cpp Sat Sep 21 15:26:42 2013 (r85812)
+++ branches/release/libs/graph/test/adj_list_loops.cpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -17,7 +17,6 @@
void test_graph_nonloop()
{
typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
- typedef typename graph_traits<Graph>::edge_descriptor Edge;
// Build a graph with 1 edge and turn it into a loop.
Graph g(5);
@@ -36,7 +35,6 @@
void test_multigraph_nonloop()
{
typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
- typedef typename graph_traits<Graph>::edge_descriptor Edge;
// Build a graph with 1 edge and turn it into a loop.
Graph g(5);
@@ -55,7 +53,6 @@
void test_graph_loop()
{
typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
- typedef typename graph_traits<Graph>::edge_descriptor Edge;
Graph g(5);
Vertex v = *next(vertices(g).first, 2);
@@ -70,7 +67,6 @@
void test_multigraph_loop()
{
typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
- typedef typename graph_traits<Graph>::edge_descriptor Edge;
Graph g(5);
Vertex v = *next(vertices(g).first, 2);
Modified: branches/release/libs/graph/test/all_planar_input_files_test.cpp
==============================================================================
--- branches/release/libs/graph/test/all_planar_input_files_test.cpp Sat Sep 21 15:26:42 2013 (r85812)
+++ branches/release/libs/graph/test/all_planar_input_files_test.cpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -122,9 +122,7 @@
typedef graph_traits<graph>::edge_iterator edge_iterator_t;
typedef graph_traits<graph>::vertex_iterator vertex_iterator_t;
typedef graph_traits<graph>::edges_size_type e_size_t;
- typedef graph_traits<graph>::vertices_size_type v_size_t;
typedef graph_traits<graph>::vertex_descriptor vertex_t;
- typedef std::pair<vertex_t, vertex_t> vertex_pair_t;
typedef edge_index_update_visitor<property_map<graph, edge_index_t>::type>
edge_visitor_t;
Modified: branches/release/libs/graph/test/astar_search_test.cpp
==============================================================================
--- branches/release/libs/graph/test/astar_search_test.cpp Sat Sep 21 15:26:42 2013 (r85812)
+++ branches/release/libs/graph/test/astar_search_test.cpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -122,7 +122,6 @@
typedef property_map<mygraph_t, edge_weight_t>::type WeightMap;
typedef mygraph_t::vertex_descriptor vertex;
typedef mygraph_t::edge_descriptor edge_descriptor;
- typedef mygraph_t::vertex_iterator vertex_iterator;
typedef std::pair<int, int> edge;
// specify data
@@ -185,13 +184,18 @@
vector<mygraph_t::vertex_descriptor> p(num_vertices(g));
vector<cost> d(num_vertices(g));
+
+ boost::property_map<mygraph_t, boost::vertex_index_t>::const_type
+ idx = get(boost::vertex_index, g);
+
try {
// call astar named parameter interface
astar_search
(g, start,
distance_heuristic<mygraph_t, cost, location*>
(locations, goal),
- predecessor_map(&p[0]).distance_map(&d[0]).
+ predecessor_map(make_iterator_property_map(p.begin(), idx)).
+ distance_map(make_iterator_property_map(d.begin(), idx)).
visitor(astar_goal_visitor<vertex>(goal)).distance_inf(my_float((std::numeric_limits<float>::max)())));
Modified: branches/release/libs/graph/test/bellman-test.cpp
==============================================================================
--- branches/release/libs/graph/test/bellman-test.cpp Sat Sep 21 15:26:42 2013 (r85812)
+++ branches/release/libs/graph/test/bellman-test.cpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -56,8 +56,8 @@
bool const r = bellman_ford_shortest_paths
(g, int (numVertex),
weight_pmap,
- &parent[0],
- &distance[0],
+ boost::make_iterator_property_map(parent.begin(), get(boost::vertex_index, g)),
+ boost::make_iterator_property_map(distance.begin(), get(boost::vertex_index, g)),
closed_plus<int>(),
std::less<int>(),
default_bellman_visitor());
@@ -81,8 +81,10 @@
std::vector<int> distance2(numVertex, 17);
bool const r2 = bellman_ford_shortest_paths
(g,
- weight_map(weight_pmap).distance_map(&distance2[0]).
- predecessor_map(&parent2[0]).root_vertex(s));
+ weight_map(weight_pmap).
+ distance_map(boost::make_iterator_property_map(distance2.begin(), get(boost::vertex_index, g))).
+ predecessor_map(boost::make_iterator_property_map(parent2.begin(), get(boost::vertex_index, g))).
+ root_vertex(s));
if (r2) {
for(int i = 0; i < numVertex; ++i) {
std::cout << name[i] << ": ";
Modified: branches/release/libs/graph/test/bfs.cpp
==============================================================================
--- branches/release/libs/graph/test/bfs.cpp Sat Sep 21 15:26:42 2013 (r85812)
+++ branches/release/libs/graph/test/bfs.cpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -140,20 +140,38 @@
parent[*ui] = *ui;
std::vector<boost::default_color_type> color(i);
+ // Get vertex index map
+ typedef typename boost::property_map<Graph, boost::vertex_index_t>::const_type idx_type;
+ idx_type idx = get(boost::vertex_index, g);
+
+ // Make property maps from vectors
+ typedef
+ boost::iterator_property_map<std::vector<int>::iterator, idx_type>
+ distance_pm_type;
+ distance_pm_type distance_pm(distance.begin(), idx);
+ typedef
+ boost::iterator_property_map<typename std::vector<vertex_descriptor>::iterator, idx_type>
+ parent_pm_type;
+ parent_pm_type parent_pm(parent.begin(), idx);
+ typedef
+ boost::iterator_property_map<std::vector<boost::default_color_type>::iterator, idx_type>
+ color_pm_type;
+ color_pm_type color_pm(color.begin(), idx);
+
// Create the testing visitor.
- bfs_testing_visitor<int*,vertex_descriptor*,Graph,
- boost::default_color_type*>
- vis(start, &distance[0], &parent[0], &color[0]);
+ bfs_testing_visitor<distance_pm_type, parent_pm_type, Graph,
+ color_pm_type>
+ vis(start, distance_pm, parent_pm, color_pm);
boost::breadth_first_search(g, start,
visitor(vis).
- color_map(&color[0]));
+ color_map(color_pm));
// All white vertices should be unreachable from the source.
for (boost::tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui)
if (color[*ui] == Color::white()) {
std::vector<boost::default_color_type> color2(i, Color::white());
- BOOST_CHECK(!boost::is_reachable(start, *ui, g, &color2[0]));
+ BOOST_CHECK(!boost::is_reachable(start, *ui, g, color_pm_type(color2.begin(), idx)));
}
// The shortest path to a child should be one longer than
Modified: branches/release/libs/graph/test/boykov_kolmogorov_max_flow_test.cpp
==============================================================================
--- branches/release/libs/graph/test/boykov_kolmogorov_max_flow_test.cpp Sat Sep 21 15:26:42 2013 (r85812)
+++ branches/release/libs/graph/test/boykov_kolmogorov_max_flow_test.cpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -218,7 +218,8 @@
get(edge_capacity,g),
get(edge_residual_capacity,g),
get(edge_reverse,g),
- &(color_vec[0]),
+ boost::make_iterator_property_map(
+ color_vec.begin(), get(vertex_index, g)),
get(vertex_index,g),
src, sink);
Modified: branches/release/libs/graph/test/closeness_centrality.cpp
==============================================================================
--- branches/release/libs/graph/test/closeness_centrality.cpp Sat Sep 21 15:26:42 2013 (r85812)
+++ branches/release/libs/graph/test/closeness_centrality.cpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -31,8 +31,6 @@
void build_graph(Graph& g,
typename vertex_vector<Graph>::type& v)
{
- typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
-
// add vertices
for(size_t i = 0; i < N; ++i) {
v[i] = add_vertex(g);
Modified: branches/release/libs/graph/test/clustering_coefficient.cpp
==============================================================================
--- branches/release/libs/graph/test/clustering_coefficient.cpp Sat Sep 21 15:26:42 2013 (r85812)
+++ branches/release/libs/graph/test/clustering_coefficient.cpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -27,8 +27,6 @@
template <typename Graph>
void build_graph(Graph& g, typename vertex_vector<Graph>::type& v)
{
- typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
-
// add vertices
for(size_t i = 0; i < N; ++i) {
v[i] = add_vertex(g);
@@ -98,7 +96,7 @@
main(int, char *[])
{
typedef undirected_graph<> Graph;
- typedef directed_graph<> Digraph;
+ // typedef directed_graph<> Digraph;
// TODO: write a test for directed clustering coefficient.
Copied and modified: branches/release/libs/graph/test/cycle_canceling_test.cpp (from r85536, trunk/libs/graph/test/cycle_canceling_test.cpp)
==============================================================================
--- trunk/libs/graph/test/cycle_canceling_test.cpp Sat Aug 31 16:09:11 2013 (r85536, copy source)
+++ branches/release/libs/graph/test/cycle_canceling_test.cpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -1,3 +1,12 @@
+//=======================================================================
+// Copyright 2013 University of Warsaw.
+// Authors: Piotr Wygocki
+//
+// 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)
+//=======================================================================
+
#define BOOST_TEST_MODULE cycle_canceling_test
#include <boost/test/unit_test.hpp>
@@ -9,9 +18,9 @@
BOOST_AUTO_TEST_CASE(cycle_canceling_def_test) {
- unsigned s,t;
- boost::SampleGraph::Graph g
- = boost::SampleGraph::getSampleGraph(s, t);
+ boost::SampleGraph::vertex_descriptor s,t;
+ boost::SampleGraph::Graph g;
+ boost::SampleGraph::getSampleGraph(g, s, t);
boost::edmonds_karp_max_flow(g, s, t);
boost::cycle_canceling(g);
@@ -21,9 +30,9 @@
}
BOOST_AUTO_TEST_CASE(path_augmentation_def_test2) {
- unsigned s,t;
- boost::SampleGraph::Graph g
- = boost::SampleGraph::getSampleGraph2(s, t);
+ boost::SampleGraph::vertex_descriptor s,t;
+ boost::SampleGraph::Graph g;
+ boost::SampleGraph::getSampleGraph2(g, s, t);
boost::edmonds_karp_max_flow(g, s, t);
boost::cycle_canceling(g);
@@ -33,17 +42,20 @@
}
BOOST_AUTO_TEST_CASE(cycle_canceling_test) {
- unsigned s,t;
+ boost::SampleGraph::vertex_descriptor s,t;
typedef boost::SampleGraph::Graph Graph;
- Graph g = boost::SampleGraph::getSampleGraph(s, t);
+ boost::SampleGraph::Graph g;
+ boost::SampleGraph::getSampleGraph(g, s, t);
int N = num_vertices(g);
std::vector<int> dist(N);
typedef boost::graph_traits<Graph>::edge_descriptor edge_descriptor;
std::vector<edge_descriptor> pred(N);
+ boost::property_map<Graph, boost::vertex_index_t>::const_type idx = get(boost::vertex_index, g);
+
boost::edmonds_karp_max_flow(g, s, t);
- boost::cycle_canceling(g, boost::distance_map(&dist[0]).predecessor_map(&pred[0]).vertex_index_map(boost::identity_property_map()));
+ boost::cycle_canceling(g, boost::distance_map(boost::make_iterator_property_map(dist.begin(), idx)).predecessor_map(boost::make_iterator_property_map(pred.begin(), idx)).vertex_index_map(idx));
int cost = boost::find_flow_cost(g);
BOOST_CHECK_EQUAL(cost, 29);
Modified: branches/release/libs/graph/test/cycle_ratio_tests.cpp
==============================================================================
--- branches/release/libs/graph/test/cycle_ratio_tests.cpp Sat Sep 21 15:26:42 2013 (r85812)
+++ branches/release/libs/graph/test/cycle_ratio_tests.cpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -331,7 +331,6 @@
{
GraphMInt gm(10);
typedef graph_traits<GraphMInt>::vertex_iterator VertexItM;
- typedef graph_traits<GraphMInt>::edge_descriptor EdgeM;
VertexItM vi1, vi2, vi_end;
for (boost::tie(vi1, vi_end) = vertices(gm); vi1 != vi_end; ++vi1)
{
Copied and modified: branches/release/libs/graph/test/cycle_test.hpp (from r85533, trunk/libs/graph/test/cycle_test.hpp)
==============================================================================
--- trunk/libs/graph/test/cycle_test.hpp Sat Aug 31 15:29:22 2013 (r85533, copy source)
+++ branches/release/libs/graph/test/cycle_test.hpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -38,7 +38,7 @@
// that the paths are valid.
typename Path::const_iterator i, j, last = prior(p.end());
for (i = p.begin(); i != last; ++i) {
- j = next(i);
+ j = boost::next(i);
BOOST_ASSERT(edge(*i, *j, g).second);
}
BOOST_ASSERT(edge(p.back(), p.front(), g).second);
Modified: branches/release/libs/graph/test/degree_centrality.cpp
==============================================================================
--- branches/release/libs/graph/test/degree_centrality.cpp Sat Sep 21 15:26:42 2013 (r85812)
+++ branches/release/libs/graph/test/degree_centrality.cpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -22,8 +22,6 @@
void build_graph(Graph& g,
vector<typename graph_traits<Graph>::vertex_descriptor>& v)
{
- typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
-
// add vertices
for(size_t i = 0; i < N; ++i) {
v[i] = add_vertex(g);
Modified: branches/release/libs/graph/test/dfs.cpp
==============================================================================
--- branches/release/libs/graph/test/dfs.cpp Sat Sep 21 15:26:42 2013 (r85812)
+++ branches/release/libs/graph/test/dfs.cpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -68,6 +68,12 @@
using namespace boost;
BOOST_CHECK( get(m_color, target(e, g)) == Color::black() );
}
+ template <class Edge, class Graph>
+ void finish_edge(Edge e, Graph& g) {
+ using namespace boost;
+ BOOST_CHECK( get(m_color, target(e, g)) == Color::gray() ||
+ get(m_color, target(e, g)) == Color::black() );
+ }
template <class Vertex, class Graph>
void finish_vertex(Vertex u, Graph&) {
using namespace boost;
@@ -116,9 +122,24 @@
std::vector<int> discover_time(num_vertices(g)),
finish_time(num_vertices(g));
- dfs_test_visitor<ColorMap, vertex_descriptor*,
- int*, int*> vis(color, &parent[0],
- &discover_time[0], &finish_time[0]);
+ // Get vertex index map
+ typedef typename boost::property_map<Graph, boost::vertex_index_t>::const_type idx_type;
+ idx_type idx = get(boost::vertex_index, g);
+
+ typedef
+ boost::iterator_property_map<typename std::vector<vertex_descriptor>::iterator, idx_type>
+ parent_pm_type;
+ parent_pm_type parent_pm(parent.begin(), idx);
+ typedef
+ boost::iterator_property_map<std::vector<int>::iterator, idx_type>
+ time_pm_type;
+ time_pm_type discover_time_pm(discover_time.begin(), idx);
+ time_pm_type finish_time_pm(finish_time.begin(), idx);
+
+ dfs_test_visitor<ColorMap, parent_pm_type,
+ time_pm_type, time_pm_type>
+ vis(color, parent_pm,
+ discover_time_pm, finish_time_pm);
boost::depth_first_search(g, visitor(vis).color_map(color));
@@ -136,10 +157,10 @@
|| finish_time[v] < discover_time[u]
|| (discover_time[v] < discover_time[u]
&& finish_time[u] < finish_time[v]
- && boost::is_descendant(u, v, &parent[0]))
+ && boost::is_descendant(u, v, parent_pm))
|| (discover_time[u] < discover_time[v]
&& finish_time[v] < finish_time[u]
- && boost::is_descendant(v, u, &parent[0]))
+ && boost::is_descendant(v, u, parent_pm))
);
}
}
Modified: branches/release/libs/graph/test/dijkstra_heap_performance.cpp
==============================================================================
--- branches/release/libs/graph/test/dijkstra_heap_performance.cpp Sat Sep 21 15:26:42 2013 (r85812)
+++ branches/release/libs/graph/test/dijkstra_heap_performance.cpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -117,7 +117,9 @@
dijkstra_relaxed_heap = false;
#endif
dijkstra_shortest_paths(g, vertex(0, g),
- distance_map(&binary_heap_distances[0]));
+ distance_map(
+ boost::make_iterator_property_map(
+ binary_heap_distances.begin(), get(boost::vertex_index, g))));
double binary_heap_time = t.elapsed();
std::cout << binary_heap_time << " seconds.\n";
@@ -135,7 +137,9 @@
dijkstra_relaxed_heap = true;
#endif
dijkstra_shortest_paths(g, vertex(0, g),
- distance_map(&relaxed_heap_distances[0]));
+ distance_map(
+ boost::make_iterator_property_map(
+ relaxed_heap_distances.begin(), get(boost::vertex_index, g))));
double relaxed_heap_time = t.elapsed();
std::cout << relaxed_heap_time << " seconds.\n"
<< "Speedup = " << (binary_heap_time / relaxed_heap_time) << ".\n";
@@ -159,7 +163,7 @@
dijkstra_shortest_paths_no_color_map
(g, vertex(0, g),
boost::dummy_property_map(),
- boost::make_iterator_property_map(&no_color_map_distances[0],
+ boost::make_iterator_property_map(no_color_map_distances.begin(),
get(boost::vertex_index, g),
0.),
get(boost::edge_weight, g),
Modified: branches/release/libs/graph/test/dijkstra_no_color_map_compare.cpp
==============================================================================
--- branches/release/libs/graph/test/dijkstra_no_color_map_compare.cpp Sat Sep 21 15:26:42 2013 (r85812)
+++ branches/release/libs/graph/test/dijkstra_no_color_map_compare.cpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -94,9 +94,6 @@
property<vertex_index_t, int >,
property<edge_weight_t, double> > graph_t;
- typedef graph_traits<graph_t>::vertex_descriptor vertex_t;
- typedef graph_traits<graph_t>::edge_descriptor edge_t;
-
graph_t graph;
generate_random_graph(graph, vertices_to_create, edges_to_create, generator);
Modified: branches/release/libs/graph/test/eccentricity.cpp
==============================================================================
--- branches/release/libs/graph/test/eccentricity.cpp Sat Sep 21 15:26:42 2013 (r85812)
+++ branches/release/libs/graph/test/eccentricity.cpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -31,8 +31,6 @@
void build_graph(Graph& g,
typename vertex_vector<Graph>::type& v)
{
- typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
-
// add vertices
for(size_t i = 0; i < N; ++i) {
v[i] = add_vertex(g);
Modified: branches/release/libs/graph/test/graphviz_test.cpp
==============================================================================
--- branches/release/libs/graph/test/graphviz_test.cpp Sat Sep 21 15:26:42 2013 (r85812)
+++ branches/release/libs/graph/test/graphviz_test.cpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -75,9 +75,6 @@
MassMap mass,
WeightMap weight) {
- typedef typename graph_traits < graph_t >::edge_descriptor edge_t;
- typedef typename graph_traits < graph_t >::vertex_descriptor vertex_t;
-
// Construct a graph and set up the dynamic_property_maps.
dynamic_properties dp(ignore_other_properties);
dp.property(node_id,name);
Copied: branches/release/libs/graph/test/hawick_circuits.cpp (from r85533, trunk/libs/graph/test/hawick_circuits.cpp)
==============================================================================
--- /dev/null 00:00:00 1970 (empty, because file is newly added)
+++ branches/release/libs/graph/test/hawick_circuits.cpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813, copy of r85533, trunk/libs/graph/test/hawick_circuits.cpp)
@@ -0,0 +1,32 @@
+// (C) Copyright 2013 Louis Dionne
+//
+// Use, modification and distribution are subject to the
+// Boost Software License, Version 1.0 (See accompanying file
+// LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt)
+
+#include "cycle_test.hpp"
+#include <boost/graph/hawick_circuits.hpp>
+#include <iostream>
+
+
+struct call_hawick_circuits {
+ template <typename Graph, typename Visitor>
+ void operator()(Graph const& g, Visitor const& v) const {
+ boost::hawick_circuits(g, v);
+ }
+};
+
+struct call_hawick_unique_circuits {
+ template <typename Graph, typename Visitor>
+ void operator()(Graph const& g, Visitor const& v) const {
+ boost::hawick_unique_circuits(g, v);
+ }
+};
+
+int main() {
+ std::cout << "---------hawick_circuits---------\n";
+ cycle_test(call_hawick_circuits());
+
+ std::cout << "\n\n---------hawick_unique_circuits---------\n";
+ cycle_test(call_hawick_unique_circuits());
+}
Modified: branches/release/libs/graph/test/index_graph.cpp
==============================================================================
--- branches/release/libs/graph/test/index_graph.cpp Sat Sep 21 15:26:42 2013 (r85812)
+++ branches/release/libs/graph/test/index_graph.cpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -64,7 +64,6 @@
template <typename Graph>
void build()
{
- typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
typedef typename graph_traits<Graph>::vertex_iterator Iterator;
typedef typename property_map<Graph, vertex_index_t>::type IndexMap;
Modified: branches/release/libs/graph/test/layout_test.cpp
==============================================================================
--- branches/release/libs/graph/test/layout_test.cpp Sat Sep 21 15:26:42 2013 (r85812)
+++ branches/release/libs/graph/test/layout_test.cpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -78,10 +78,8 @@
void
test_circle_layout(Graph*, typename graph_traits<Graph>::vertices_size_type n)
{
- typedef typename graph_traits<Graph>::vertex_descriptor vertex;
typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator;
typedef typename graph_traits<Graph>::vertices_size_type vertices_size_type;
- typedef typename graph_traits<Graph>::edges_size_type edges_size_type;
Graph g(n);
Modified: branches/release/libs/graph/test/make_connected_test.cpp
==============================================================================
--- branches/release/libs/graph/test/make_connected_test.cpp Sat Sep 21 15:26:42 2013 (r85812)
+++ branches/release/libs/graph/test/make_connected_test.cpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -114,10 +114,14 @@
make_disconnected_cycles(gVV, num_cycles, cycle_size);
reset_edge_index(gVV);
std::vector<int> gVV_components(num_vertices(gVV));
- BOOST_CHECK(connected_components(gVV, &gVV_components[0]) ==
+ boost::iterator_property_map<
+ std::vector<int>::iterator,
+ typename boost::property_map<VVgraph_t, boost::vertex_index_t>::const_type
+ > gVV_components_pm(gVV_components.begin(), get(boost::vertex_index, gVV));
+ BOOST_CHECK(connected_components(gVV, gVV_components_pm) ==
static_cast<int>(num_cycles));
make_connected(gVV);
- BOOST_CHECK(connected_components(gVV, &gVV_components[0]) == 1);
+ BOOST_CHECK(connected_components(gVV, gVV_components_pm) == 1);
BOOST_CHECK(num_edges(gVV) == num_cycles * cycle_size + num_cycles - 1);
LVgraph_t gLV;
@@ -126,10 +130,14 @@
make_disconnected_cycles(gLV, num_cycles, cycle_size);
reset_edge_index(gLV);
std::vector<int> gLV_components(num_vertices(gLV));
- BOOST_CHECK(connected_components(gLV, &gLV_components[0]) ==
+ boost::iterator_property_map<
+ std::vector<int>::iterator,
+ typename boost::property_map<VVgraph_t, boost::vertex_index_t>::const_type
+ > gLV_components_pm(gLV_components.begin(), get(boost::vertex_index, gLV));
+ BOOST_CHECK(connected_components(gLV, gLV_components_pm) ==
static_cast<int>(num_cycles));
make_connected(gLV);
- BOOST_CHECK(connected_components(gLV, &gLV_components[0]) == 1);
+ BOOST_CHECK(connected_components(gLV, gLV_components_pm) == 1);
BOOST_CHECK(num_edges(gLV) == num_cycles * cycle_size + num_cycles - 1);
VLgraph_t gVL;
Modified: branches/release/libs/graph/test/matching_test.cpp
==============================================================================
--- branches/release/libs/graph/test/matching_test.cpp Sat Sep 21 15:26:42 2013 (r85812)
+++ branches/release/libs/graph/test/matching_test.cpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -131,7 +131,6 @@
typedef vector_property_map< typename graph_traits<Graph>::vertex_descriptor, vertex_index_map_t > mate_t;
typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator_t;
typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor_t;
- typedef typename graph_traits<Graph>::vertices_size_type v_size_t;
const std::size_t double_num_v = num_v * 2;
Modified: branches/release/libs/graph/test/mcgregor_subgraphs_test.cpp
==============================================================================
--- branches/release/libs/graph/test/mcgregor_subgraphs_test.cpp Sat Sep 21 15:26:42 2013 (r85812)
+++ branches/release/libs/graph/test/mcgregor_subgraphs_test.cpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -195,10 +195,6 @@
typedef typename boost::graph_traits<Graph>::vertex_descriptor Vertex;
- typedef typename boost::property_map<Graph, boost::vertex_index_t>::type VertexIndexMap;
- typedef typename boost::property_map<Graph, boost::vertex_name_t>::type VertexNameMap;
- typedef typename boost::property_map<Graph, boost::edge_name_t>::type EdgeNameMap;
-
std::stringstream subgraph_string;
BGL_FORALL_VERTICES_T(vertex1, m_graph1, Graph) {
@@ -308,9 +304,6 @@
boost::property<boost::vertex_index_t, unsigned int> >,
boost::property<boost::edge_name_t, unsigned int> > Graph;
- typedef boost::graph_traits<Graph>::vertex_descriptor Vertex;
- typedef boost::graph_traits<Graph>::edge_descriptor Edge;
-
typedef boost::property_map<Graph, boost::vertex_name_t>::type VertexNameMap;
typedef boost::property_map<Graph, boost::edge_name_t>::type EdgeNameMap;
Modified: branches/release/libs/graph/test/mean_geodesic.cpp
==============================================================================
--- branches/release/libs/graph/test/mean_geodesic.cpp Sat Sep 21 15:26:42 2013 (r85812)
+++ branches/release/libs/graph/test/mean_geodesic.cpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -31,8 +31,6 @@
template <typename Graph>
void build_graph(Graph& g, typename vertex_vector<Graph>::type& v)
{
- typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
-
// add vertices
for(size_t i = 0; i < N; ++i) {
v[i] = add_vertex(g);
Modified: branches/release/libs/graph/test/metric_tsp_approx.cpp
==============================================================================
--- branches/release/libs/graph/test/metric_tsp_approx.cpp Sat Sep 21 15:26:42 2013 (r85812)
+++ branches/release/libs/graph/test/metric_tsp_approx.cpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -86,7 +86,6 @@
property <edge_weight_t, double,
property<edge_index_t, int> > > Graph;
typedef graph_traits<Graph>::vertex_descriptor Vertex;
- typedef graph_traits <Graph>::edge_descriptor Edge;
typedef property_map<Graph, edge_weight_t>::type WeightMap;
typedef set<simple_point<double>, cmpPnt<double> > PointSet;
typedef vector< Vertex > Container;
@@ -199,7 +198,6 @@
typedef adjacency_matrix<undirectedS, no_property,
property <edge_weight_t, double> > Graph;
typedef graph_traits<Graph>::vertex_descriptor Vertex;
- typedef graph_traits <Graph>::edge_descriptor Edge;
typedef vector<Vertex> Container;
typedef property_map<Graph, edge_weight_t>::type WeightMap;
typedef property_map<Graph, vertex_index_t>::type VertexMap;
Copied and modified: branches/release/libs/graph/test/min_cost_max_flow_utils.hpp (from r85536, trunk/libs/graph/test/min_cost_max_flow_utils.hpp)
==============================================================================
--- trunk/libs/graph/test/min_cost_max_flow_utils.hpp Sat Aug 31 16:09:11 2013 (r85536, copy source)
+++ branches/release/libs/graph/test/min_cost_max_flow_utils.hpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -1,13 +1,17 @@
-/**
- * @file sample_graph_undirected.hpp
- * @brief
- * @author Piotr Wygocki
- * @version 1.0
- * @date 2013-06-17
- */
+//=======================================================================
+// Copyright 2013 University of Warsaw.
+// Authors: Piotr Wygocki
+//
+// 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 SAMPLE_GRAPH_UNDIRECTED_HPP
#define SAMPLE_GRAPH_UNDIRECTED_HPP
+#include <iostream>
+#include <cstdlib>
#include <boost/graph/adjacency_list.hpp>
@@ -15,7 +19,7 @@
struct SampleGraph {
typedef adjacency_list_traits < vecS, vecS, directedS > Traits;
- typedef adjacency_list < listS, vecS, directedS, no_property,
+ typedef adjacency_list < vecS, vecS, directedS, no_property,
property < edge_capacity_t, long,
property < edge_residual_capacity_t, long,
property < edge_reverse_t, Traits::edge_descriptor,
@@ -26,14 +30,15 @@
typedef property_map < Graph, edge_capacity_t >::type Capacity;
typedef property_map < Graph, edge_residual_capacity_t >::type ResidualCapacity;
typedef property_map < Graph, edge_weight_t >::type Weight;
+ typedef property_map < Graph, edge_reverse_t>::type Reversed;
+ typedef boost::graph_traits<Graph>::vertices_size_type size_type;
+ typedef Traits::vertex_descriptor vertex_descriptor;
-
- template <typename Graph, typename Weight, typename Capacity, typename Reversed, typename ResidualCapacity>
class EdgeAdder {
public:
EdgeAdder(Graph & g, Weight & w, Capacity & c, Reversed & rev, ResidualCapacity & residualCapacity)
: m_g(g), m_w(w), m_cap(c), m_resCap(residualCapacity), m_rev(rev) {}
- void addEdge(int v, int w, int weight, int capacity) {
+ void addEdge(vertex_descriptor v, vertex_descriptor w, long weight, long capacity) {
Traits::edge_descriptor e,f;
e = add(v, w, weight, capacity);
f = add(w, v, -weight, 0);
@@ -41,11 +46,14 @@
m_rev[f] = e;
}
private:
- Traits::edge_descriptor add(int v, int w, int weight, int capacity) {
+ Traits::edge_descriptor add(vertex_descriptor v, vertex_descriptor w, long weight, long capacity) {
bool b;
Traits::edge_descriptor e;
- boost::tie(e, b) = add_edge(v, w, m_g);
- assert(b);
+ boost::tie(e, b) = add_edge(vertex(v, m_g), vertex(w, m_g), m_g);
+ if (!b) {
+ std::cerr << "Edge between " << v << " and " << w << " already exists." << std::endl;
+ std::abort();
+ }
m_cap[e] = capacity;
m_w[e] = weight;
return e;
@@ -58,11 +66,13 @@
};
- static Graph getSampleGraph(unsigned & s, unsigned & t) {
- const boost::graph_traits<Graph>::vertices_size_type N(6);
+ static void getSampleGraph(Graph &g, vertex_descriptor & s, vertex_descriptor & t) {
+ size_type N(6);
typedef property_map < Graph, edge_reverse_t >::type Reversed;
- Graph g(N);
+ for(size_type i = 0; i < N; ++i){
+ add_vertex(g);
+ }
Capacity capacity = get(edge_capacity, g);
Reversed rev = get(edge_reverse, g);
ResidualCapacity residual_capacity = get(edge_residual_capacity, g);
@@ -71,8 +81,7 @@
s = 0;
t = 5;
- EdgeAdder<Graph, Weight, Capacity, Reversed, ResidualCapacity>
- ea(g, weight, capacity, rev, residual_capacity);
+ EdgeAdder ea(g, weight, capacity, rev, residual_capacity);
ea.addEdge(0, 1, 4 ,2);
ea.addEdge(0, 2, 2 ,2);
@@ -84,15 +93,17 @@
ea.addEdge(3, 5, 4 ,20);
ea.addEdge(4, 5, 2 ,20);
-
- return g;
}
-
- static Graph getSampleGraph2(unsigned & s, unsigned & t) {
+
+ static void getSampleGraph2(Graph &g, vertex_descriptor & s, vertex_descriptor & t) {
+
const boost::graph_traits<Graph>::vertices_size_type N(5);
typedef property_map < Graph, edge_reverse_t >::type Reversed;
- Graph g(N);
+ for(size_type i = 0; i < N; ++i){
+ add_vertex(g);
+ }
+
Capacity capacity = get(edge_capacity, g);
Reversed rev = get(edge_reverse, g);
ResidualCapacity residual_capacity = get(edge_residual_capacity, g);
@@ -101,8 +112,7 @@
s = 0;
t = 4;
- EdgeAdder<Graph, Weight, Capacity, Reversed, ResidualCapacity>
- ea(g, weight, capacity, rev, residual_capacity);
+ EdgeAdder ea(g, weight, capacity, rev, residual_capacity);
ea.addEdge(0, 1, 4 ,2);
ea.addEdge(0, 2, 2 ,2);
@@ -110,7 +120,7 @@
ea.addEdge(2, 3, 1 ,1);
ea.addEdge(2, 4, 1 ,1);
ea.addEdge(3, 4, 1 ,1);
-
+
ea.addEdge(1, 0, 2 ,2);
ea.addEdge(2, 0, 1 ,1);
@@ -118,8 +128,6 @@
ea.addEdge(3, 2, 1 ,1);
ea.addEdge(4, 2, 2 ,2);
ea.addEdge(4, 3, 1 ,3);
-
- return g;
}
};
} //boost
Modified: branches/release/libs/graph/test/parallel_edges_loops_test.cpp
==============================================================================
--- branches/release/libs/graph/test/parallel_edges_loops_test.cpp Sat Sep 21 15:26:42 2013 (r85812)
+++ branches/release/libs/graph/test/parallel_edges_loops_test.cpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -195,9 +195,7 @@
typedef graph_traits<graph>::edge_iterator edge_iterator_t;
typedef graph_traits<graph>::vertex_iterator vertex_iterator_t;
typedef graph_traits<graph>::edges_size_type e_size_t;
- typedef graph_traits<graph>::vertices_size_type v_size_t;
typedef graph_traits<graph>::vertex_descriptor vertex_t;
- typedef std::pair<vertex_t, vertex_t> vertex_pair_t;
typedef edge_index_update_visitor<property_map<graph, edge_index_t>::type>
edge_visitor_t;
Modified: branches/release/libs/graph/test/property_iter.cpp
==============================================================================
--- branches/release/libs/graph/test/property_iter.cpp Sat Sep 21 15:26:42 2013 (r85812)
+++ branches/release/libs/graph/test/property_iter.cpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -109,19 +109,9 @@
++E;
}
- typedef boost::graph_property_iter_range< Graph, vertex_id_t>::const_iterator TNodeConstIterator;
- typedef boost::graph_property_iter_range< Graph, vertex_id_t>::const_type TNodeConstIteratorType;
-
typedef boost::graph_property_iter_range< Graph, vertex_id_t>::iterator TNodeIterator;
- typedef boost::graph_property_iter_range< Graph, vertex_id_t>::type TNodeIteratorType;
-
- typedef boost::graph_property_iter_range< Graph, edge_id_t>::const_iterator TLinkConstIterator;
- typedef boost::graph_property_iter_range< Graph, edge_id_t>::const_type TLinkConstIteratorType;
typedef boost::graph_property_iter_range< Graph, edge_id_t>::iterator TLinkIterator;
- typedef boost::graph_property_iter_range< Graph, edge_id_t>::type TLinkIteratorType;
-
- typedef std::pair<TLinkConstIterator, TLinkConstIterator> tLinkConstIteratorPair;
TLinkIterator itEdgeBegin, itEdgeEnd;
Copied and modified: branches/release/libs/graph/test/rcsp_custom_vertex_id.cpp (from r85571, trunk/libs/graph/test/rcsp_custom_vertex_id.cpp)
==============================================================================
--- trunk/libs/graph/test/rcsp_custom_vertex_id.cpp Thu Sep 5 08:57:15 2013 (r85571, copy source)
+++ branches/release/libs/graph/test/rcsp_custom_vertex_id.cpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -1,4 +1,5 @@
//=======================================================================
+// Copyright (c) 2013 Alberto Santini
// Author: Alberto Santini <alberto_at_[hidden]>
//
// Distributed under the Boost Software License, Version 1.0. (See
@@ -67,9 +68,9 @@
VertexProperty vp3(4, 3);
EdgeProperty e12(1);
EdgeProperty e23(2);
-
+
Graph g;
-
+
Vertex v1 = add_vertex(g); g[v1] = vp1;
Vertex v2 = add_vertex(g); g[v2] = vp2;
Vertex v3 = add_vertex(g); g[v3] = vp3;
Modified: branches/release/libs/graph/test/sequential_vertex_coloring.cpp
==============================================================================
--- branches/release/libs/graph/test/sequential_vertex_coloring.cpp Sat Sep 21 15:26:42 2013 (r85812)
+++ branches/release/libs/graph/test/sequential_vertex_coloring.cpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -16,7 +16,6 @@
int test_main(int, char*[])
{
typedef adjacency_list<listS, vecS, undirectedS> Graph;
- typedef graph_traits<Graph>::vertex_descriptor vertex_descriptor;
typedef graph_traits<Graph>::vertices_size_type vertices_size_type;
typedef property_map<Graph, vertex_index_t>::const_type vertex_index_map;
Modified: branches/release/libs/graph/test/stoer_wagner_test.cpp
==============================================================================
--- branches/release/libs/graph/test/stoer_wagner_test.cpp Sat Sep 21 15:26:42 2013 (r85812)
+++ branches/release/libs/graph/test/stoer_wagner_test.cpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -45,9 +45,6 @@
// the example from Stoer & Wagner (1997)
BOOST_AUTO_TEST_CASE(test0)
{
- typedef boost::graph_traits<undirected_graph>::vertex_descriptor vertex_descriptor;
- typedef boost::graph_traits<undirected_graph>::edge_descriptor edge_descriptor;
-
edge_t edges[] = {{0, 1}, {1, 2}, {2, 3},
{0, 4}, {1, 4}, {1, 5}, {2, 6}, {3, 6}, {3, 7}, {4, 5}, {5, 6}, {6, 7}};
weight_type ws[] = {2, 3, 4, 3, 2, 2, 2, 2, 2, 3, 1, 3};
@@ -72,16 +69,12 @@
BOOST_AUTO_TEST_CASE(test1)
{
{ // if only one vertex, can't run `boost::stoer_wagner_min_cut`
- typedef boost::graph_traits<undirected_graph>::vertex_descriptor vertex_descriptor;
- typedef boost::graph_traits<undirected_graph>::edge_descriptor edge_descriptor;
-
undirected_graph g;
add_vertex(g);
BOOST_CHECK_THROW(boost::stoer_wagner_min_cut(g, get(boost::edge_weight, g)), boost::bad_graph);
}{ // three vertices with one multi-edge
typedef boost::graph_traits<undirected_graph>::vertex_descriptor vertex_descriptor;
- typedef boost::graph_traits<undirected_graph>::edge_descriptor edge_descriptor;
edge_t edges[] = {{0, 1}, {1, 2}, {1, 2}, {2, 0}};
weight_type ws[] = {3, 1, 1, 1};
@@ -104,9 +97,6 @@
// example by Daniel Trebbien
BOOST_AUTO_TEST_CASE(test2)
{
- typedef boost::graph_traits<undirected_graph>::vertex_descriptor vertex_descriptor;
- typedef boost::graph_traits<undirected_graph>::edge_descriptor edge_descriptor;
-
edge_t edges[] = {{5, 2}, {0, 6}, {5, 6},
{3, 1}, {0, 1}, {6, 3}, {4, 6}, {2, 4}, {5, 3}};
weight_type ws[] = {1, 3, 4, 6, 4, 1, 2, 5, 2};
@@ -129,9 +119,6 @@
// example by Daniel Trebbien
BOOST_AUTO_TEST_CASE(test3)
{
- typedef boost::graph_traits<undirected_graph>::vertex_descriptor vertex_descriptor;
- typedef boost::graph_traits<undirected_graph>::edge_descriptor edge_descriptor;
-
edge_t edges[] = {{3, 4}, {3, 6}, {3, 5}, {0, 4}, {0, 1}, {0, 6}, {0, 7},
{0, 5}, {0, 2}, {4, 1}, {1, 6}, {1, 5}, {6, 7}, {7, 5}, {5, 2}, {3, 4}};
weight_type ws[] = {0, 3, 1, 3, 1, 2, 6, 1, 8, 1, 1, 80, 2, 1, 1, 4};
@@ -196,7 +183,6 @@
BOOST_AUTO_TEST_CASE(test_prgen_20_70_2)
{
typedef boost::graph_traits<undirected_graph>::vertex_descriptor vertex_descriptor;
- typedef boost::graph_traits<undirected_graph>::edge_descriptor edge_descriptor;
std::ifstream ifs((test_dir + "/prgen_input_graphs/prgen_20_70_2.net").c_str());
undirected_graph g;
@@ -221,7 +207,6 @@
BOOST_AUTO_TEST_CASE(test_prgen_50_40_2)
{
typedef boost::graph_traits<undirected_graph>::vertex_descriptor vertex_descriptor;
- typedef boost::graph_traits<undirected_graph>::edge_descriptor edge_descriptor;
std::ifstream ifs((test_dir + "/prgen_input_graphs/prgen_50_40_2.net").c_str());
undirected_graph g;
@@ -239,7 +224,6 @@
BOOST_AUTO_TEST_CASE(test_prgen_50_70_2)
{
typedef boost::graph_traits<undirected_graph>::vertex_descriptor vertex_descriptor;
- typedef boost::graph_traits<undirected_graph>::edge_descriptor edge_descriptor;
std::ifstream ifs((test_dir + "/prgen_input_graphs/prgen_50_70_2.net").c_str());
undirected_graph g;
Modified: branches/release/libs/graph/test/subgraph.cpp
==============================================================================
--- branches/release/libs/graph/test/subgraph.cpp Sat Sep 21 15:26:42 2013 (r85812)
+++ branches/release/libs/graph/test/subgraph.cpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -27,7 +27,6 @@
> graph_t;
typedef subgraph<graph_t> subgraph_t;
typedef graph_traits<subgraph_t>::vertex_descriptor vertex_t;
- typedef graph_traits<subgraph_t>::edge_descriptor edge_t;
mt19937 gen;
for (int t = 0; t < 100; t += 5) {
Copied and modified: branches/release/libs/graph/test/successive_shortest_path_nonnegative_weights_test.cpp (from r85568, trunk/libs/graph/test/successive_shortest_path_nonnegative_weights_test.cpp)
==============================================================================
--- trunk/libs/graph/test/successive_shortest_path_nonnegative_weights_test.cpp Wed Sep 4 17:39:21 2013 (r85568, copy source)
+++ branches/release/libs/graph/test/successive_shortest_path_nonnegative_weights_test.cpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -18,9 +18,9 @@
BOOST_AUTO_TEST_CASE(path_augmentation_def_test) {
- unsigned s,t;
- boost::SampleGraph::Graph g
- = boost::SampleGraph::getSampleGraph(s, t);
+ boost::SampleGraph::vertex_descriptor s,t;
+ boost::SampleGraph::Graph g;
+ boost::SampleGraph::getSampleGraph(g, s, t);
boost::successive_shortest_path_nonnegative_weights(g, s, t);
@@ -29,9 +29,9 @@
}
BOOST_AUTO_TEST_CASE(path_augmentation_def_test2) {
- unsigned s,t;
- boost::SampleGraph::Graph g
- = boost::SampleGraph::getSampleGraph2(s, t);
+ boost::SampleGraph::vertex_descriptor s,t;
+ boost::SampleGraph::Graph g;
+ boost::SampleGraph::getSampleGraph2(g, s, t);
boost::successive_shortest_path_nonnegative_weights(g, s, t);
@@ -40,9 +40,10 @@
}
BOOST_AUTO_TEST_CASE(path_augmentation_test) {
- unsigned s,t;
+ boost::SampleGraph::vertex_descriptor s,t;
typedef boost::SampleGraph::Graph Graph;
- Graph g = boost::SampleGraph::getSampleGraph(s, t);
+ Graph g;
+ boost::SampleGraph::getSampleGraph(g, s, t);
int N = boost::num_vertices(g);
std::vector<int> dist(N);
@@ -50,12 +51,14 @@
typedef boost::graph_traits<Graph>::edge_descriptor edge_descriptor;
std::vector<edge_descriptor> pred(N);
+ boost::property_map<Graph, boost::vertex_index_t>::const_type
+ idx = get(boost::vertex_index, g);
boost::successive_shortest_path_nonnegative_weights(g, s, t,
- boost::distance_map(&dist[0]).
- predecessor_map(&pred[0]).
- distance_map2(&dist_prev[0]).
- vertex_index_map(boost::identity_property_map()));
+ boost::distance_map(boost::make_iterator_property_map(dist.begin(), idx)).
+ predecessor_map(boost::make_iterator_property_map(pred.begin(), idx)).
+ distance_map2(boost::make_iterator_property_map(dist_prev.begin(), idx)).
+ vertex_index_map(idx));
int cost = boost::find_flow_cost(g);
BOOST_CHECK_EQUAL(cost, 29);
Modified: branches/release/libs/graph/test/test_properties.hpp
==============================================================================
--- branches/release/libs/graph/test/test_properties.hpp Sat Sep 21 15:26:42 2013 (r85812)
+++ branches/release/libs/graph/test/test_properties.hpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -17,9 +17,6 @@
using namespace boost;
std::cout << "...test_graph_bundle\n";
- typedef typename graph_property_type<Graph>::type Property;
- typedef typename graph_bundle_type<Graph>::type Bundle;
-
GraphBundle& b1 = g[graph_bundle];
GraphBundle& b2 = get_property(g);
ignore(b1); ignore(b2);
Modified: branches/release/libs/graph/test/tiernan_all_cycles.cpp
==============================================================================
--- branches/release/libs/graph/test/tiernan_all_cycles.cpp Sat Sep 21 15:26:42 2013 (r85812)
+++ branches/release/libs/graph/test/tiernan_all_cycles.cpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -27,8 +27,6 @@
void cycle(const Path& p, const Graph& g)
{
++cycles;
- typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
- typedef typename graph_traits<Graph>::edge_descriptor Edge;
// Check to make sure that each of the vertices in the path
// is truly connected and that the back is connected to the
// front - it's not validating that we find all paths, just
Modified: branches/release/libs/graph/test/transitive_closure_test.cpp
==============================================================================
--- branches/release/libs/graph/test/transitive_closure_test.cpp Sat Sep 21 15:26:42 2013 (r85812)
+++ branches/release/libs/graph/test/transitive_closure_test.cpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -74,7 +74,7 @@
typename graph_traits<Graph>::adjacency_iterator k, k_end;
for (boost::tie(k, k_end) = adjacent_vertices(*i, g); k != k_end; ++k) {
std::vector<default_color_type> color_map_vec(num_vertices(g));
- if (is_reachable(*k, *i, g, &color_map_vec[0])) {
+ if (is_reachable(*k, *i, g, boost::make_iterator_property_map(color_map_vec.begin(), get(boost::vertex_index, g)))) {
can_reach = true;
break;
}
@@ -93,7 +93,7 @@
}
} else {
std::vector<default_color_type> color_map_vec(num_vertices(g));
- if (is_reachable(*i, *j, g, &color_map_vec[0])) {
+ if (is_reachable(*i, *j, g, boost::make_iterator_property_map(color_map_vec.begin(), get(boost::vertex_index, g)))) {
if (num_tc != 1)
return false;
} else {
@@ -117,16 +117,16 @@
{
progress_timer t;
cout << "transitive_closure" << endl;
- transitive_closure(g1, g1_tc, vertex_index_map(identity_property_map()));
+ transitive_closure(g1, g1_tc, vertex_index_map(get(boost::vertex_index, g1)));
}
if(check_transitive_closure(g1, g1_tc))
return true;
else {
cout << "Original graph was ";
- print_graph(g1, identity_property_map());
+ print_graph(g1, get(boost::vertex_index, g1));
cout << "Result is ";
- print_graph(g1_tc, identity_property_map());
+ print_graph(g1_tc, get(boost::vertex_index, g1_tc));
return false;
}
}
Copied and modified: branches/release/libs/graph/test/undirected_dfs.cpp (from r78030, trunk/libs/graph/test/undirected_dfs.cpp)
==============================================================================
--- trunk/libs/graph/test/undirected_dfs.cpp Mon Apr 16 19:12:50 2012 (r78030, copy source)
+++ branches/release/libs/graph/test/undirected_dfs.cpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -130,9 +130,24 @@
std::vector<int> discover_time(num_vertices(g)),
finish_time(num_vertices(g));
- dfs_test_visitor<ColorMap, vertex_descriptor*,
- int*, int*> vis(color, &parent[0],
- &discover_time[0], &finish_time[0]);
+ // Get vertex index map
+ typedef typename boost::property_map<Graph, boost::vertex_index_t>::const_type idx_type;
+ idx_type idx = get(boost::vertex_index, g);
+
+ typedef
+ boost::iterator_property_map<typename std::vector<vertex_descriptor>::iterator, idx_type>
+ parent_pm_type;
+ parent_pm_type parent_pm(parent.begin(), idx);
+ typedef
+ boost::iterator_property_map<std::vector<int>::iterator, idx_type>
+ time_pm_type;
+ time_pm_type discover_time_pm(discover_time.begin(), idx);
+ time_pm_type finish_time_pm(finish_time.begin(), idx);
+
+ dfs_test_visitor<ColorMap, parent_pm_type,
+ time_pm_type, time_pm_type>
+ vis(color, parent_pm,
+ discover_time_pm, finish_time_pm);
boost::undirected_dfs(g, visitor(vis).color_map(color)
.edge_color_map(e_color));
@@ -155,10 +170,10 @@
|| finish_time[v] < discover_time[u]
|| (discover_time[v] < discover_time[u]
&& finish_time[u] < finish_time[v]
- && boost::is_descendant(u, v, &parent[0]))
+ && boost::is_descendant(u, v, parent_pm))
|| (discover_time[u] < discover_time[v]
&& finish_time[v] < finish_time[u]
- && boost::is_descendant(v, u, &parent[0]))
+ && boost::is_descendant(v, u, parent_pm))
);
}
}
Modified: branches/release/libs/graph_parallel/test/adjlist_redist_test.cpp
==============================================================================
--- branches/release/libs/graph_parallel/test/adjlist_redist_test.cpp Sat Sep 21 15:26:42 2013 (r85812)
+++ branches/release/libs/graph_parallel/test/adjlist_redist_test.cpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -107,7 +107,6 @@
template<typename Graph>
void test_redistribution(int n, double p, int iterations, bool debug_output)
{
- typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor;
RandomGenerator gen;
Graph g(erdos_renyi_iterator<RandomGenerator, Graph>(gen, n, p),
erdos_renyi_iterator<RandomGenerator, Graph>(),
Modified: branches/release/libs/graph_parallel/test/adjlist_remove_test.cpp
==============================================================================
--- branches/release/libs/graph_parallel/test/adjlist_remove_test.cpp Sat Sep 21 15:26:42 2013 (r85812)
+++ branches/release/libs/graph_parallel/test/adjlist_remove_test.cpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -34,7 +34,6 @@
typedef adjacency_list<listS, distributedS<mpi_process_group, vecS>,
bidirectionalS> Graph;
typedef graph_traits<Graph>::vertex_descriptor Vertex;
- typedef graph_traits<Graph>::edge_descriptor Edge;
typedef std::pair<std::size_t, std::size_t> E;
E edges[3] = { E(0,3), E(1,4), E(2,5) };
Modified: branches/release/libs/graph_parallel/test/distributed_betweenness_centrality_test.cpp
==============================================================================
--- branches/release/libs/graph_parallel/test/distributed_betweenness_centrality_test.cpp Sat Sep 21 15:26:42 2013 (r85812)
+++ branches/release/libs/graph_parallel/test/distributed_betweenness_centrality_test.cpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -131,9 +131,6 @@
typedef sorted_erdos_renyi_iterator<minstd_rand, Graph> ERIter;
- typedef graph_traits<Graph>::vertex_descriptor vertex_descriptor;
- typedef graph_traits<Graph>::edge_descriptor edge_descriptor;
-
int n = 100;
double prob = 0.1;
int C = 3;
Modified: branches/release/libs/graph_parallel/test/distributed_connected_components_test.cpp
==============================================================================
--- branches/release/libs/graph_parallel/test/distributed_connected_components_test.cpp Sat Sep 21 15:26:42 2013 (r85812)
+++ branches/release/libs/graph_parallel/test/distributed_connected_components_test.cpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -72,11 +72,6 @@
typedef compressed_sparse_row_graph<directedS, no_property, no_property, no_property,
distributedS<mpi_process_group> > Graph;
- typedef graph_traits<Graph>::vertex_descriptor vertex_descriptor;
- typedef graph_traits<Graph>::vertex_iterator vertex_iterator;
- typedef iterator_property_map<std::vector<vertex_descriptor>::iterator, property_map<Graph, vertex_index_t>::type> ParentMap;
- typedef std::pair<int, int> Edge;
-
minstd_rand gen;
gen.seed(seed);
Modified: branches/release/libs/graph_parallel/test/distributed_csr_algorithm_test.cpp
==============================================================================
--- branches/release/libs/graph_parallel/test/distributed_csr_algorithm_test.cpp Sat Sep 21 15:26:42 2013 (r85812)
+++ branches/release/libs/graph_parallel/test/distributed_csr_algorithm_test.cpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -224,7 +224,6 @@
typedef small_world_iterator<minstd_rand, Digraph> SWIter;
typedef sorted_rmat_iterator<minstd_rand, Digraph> RMATIter;
- typedef graph_traits<Digraph>::vertex_descriptor vertex_descriptor;
typedef graph_traits<Digraph>::edge_descriptor edge_descriptor;
int n = 40;
Modified: branches/release/libs/graph_parallel/test/distributed_csr_test.cpp
==============================================================================
--- branches/release/libs/graph_parallel/test/distributed_csr_test.cpp Sat Sep 21 15:26:42 2013 (r85812)
+++ branches/release/libs/graph_parallel/test/distributed_csr_test.cpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -35,7 +35,7 @@
void concept_checks()
{
- typedef compressed_sparse_row_graph<directedS, void, void, no_property,
+ typedef compressed_sparse_row_graph<directedS, no_property, no_property, no_property,
distributedS<mpi_process_group> >
Digraph;
typedef graph_traits<Digraph>::vertex_descriptor vertex_descriptor;
@@ -81,7 +81,7 @@
concept_checks();
- typedef compressed_sparse_row_graph<directedS, void, void, no_property,
+ typedef compressed_sparse_row_graph<directedS, no_property, no_property, no_property,
distributedS<mpi_process_group> >
Digraph;
Modified: branches/release/libs/graph_parallel/test/distributed_dfs_test.cpp
==============================================================================
--- branches/release/libs/graph_parallel/test/distributed_dfs_test.cpp Sat Sep 21 15:26:42 2013 (r85812)
+++ branches/release/libs/graph_parallel/test/distributed_dfs_test.cpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -118,7 +118,6 @@
// Vertex properties
property<vertex_color_t, default_color_type> >
Graph;
- typedef graph_traits<Graph>::vertices_size_type size_type;
typedef graph_traits<Graph>::vertex_descriptor vertex_descriptor;
// Specify the edges in the graph
Modified: branches/release/libs/graph_parallel/test/distributed_graph_coloring_test.cpp
==============================================================================
--- branches/release/libs/graph_parallel/test/distributed_graph_coloring_test.cpp Sat Sep 21 15:26:42 2013 (r85812)
+++ branches/release/libs/graph_parallel/test/distributed_graph_coloring_test.cpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -42,8 +42,6 @@
distributedS<mpi_process_group, vecS>,
undirectedS> Graph;
- typedef graph_traits<Graph>::vertex_descriptor vertex_descriptor;
- typedef graph_traits<Graph>::vertex_iterator vertex_iterator;
typedef property_map<Graph, vertex_index_t>::type vertex_index_map;
// Build a random number generator
Modified: branches/release/libs/graph_parallel/test/distributed_mst_test.cpp
==============================================================================
--- branches/release/libs/graph_parallel/test/distributed_mst_test.cpp Sat Sep 21 15:26:42 2013 (r85812)
+++ branches/release/libs/graph_parallel/test/distributed_mst_test.cpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -65,8 +65,6 @@
// Edge properties
property<edge_weight_t, int> > Graph;
- typedef graph_traits<Graph>::vertex_descriptor vertex_descriptor;
- typedef graph_traits<Graph>::vertex_iterator vertex_iterator;
typedef graph_traits<Graph>::edge_descriptor edge_descriptor;
typedef std::pair<int, int> E;
Modified: branches/release/libs/graph_parallel/test/distributed_shortest_paths_test.cpp
==============================================================================
--- branches/release/libs/graph_parallel/test/distributed_shortest_paths_test.cpp Sat Sep 21 15:26:42 2013 (r85812)
+++ branches/release/libs/graph_parallel/test/distributed_shortest_paths_test.cpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -169,10 +169,7 @@
VertexProperties,
WeightedEdge> Graph;
- typedef graph_traits<Graph>::vertex_descriptor vertex_descriptor;
- typedef graph_traits<Graph>::vertex_iterator vertex_iterator;
typedef graph_traits<Graph>::vertices_size_type vertices_size_type;
- typedef property_map<Graph, vertex_index_t>::type vertex_index_map;
// Build a random number generator
minstd_rand gen;
Modified: branches/release/libs/graph_parallel/test/distributed_st_connected_test.cpp
==============================================================================
--- branches/release/libs/graph_parallel/test/distributed_st_connected_test.cpp Sat Sep 21 15:26:42 2013 (r85812)
+++ branches/release/libs/graph_parallel/test/distributed_st_connected_test.cpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -48,8 +48,6 @@
// Vertex properties
property<vertex_color_t, default_color_type> >
Graph;
- typedef graph_traits<Graph>::vertices_size_type size_type;
- typedef graph_traits<Graph>::vertex_descriptor vertex_descriptor;
// Specify the edges in the graph
{
Modified: branches/release/libs/graph_parallel/test/distributed_strong_components_test.cpp
==============================================================================
--- branches/release/libs/graph_parallel/test/distributed_strong_components_test.cpp Sat Sep 21 15:26:42 2013 (r85812)
+++ branches/release/libs/graph_parallel/test/distributed_strong_components_test.cpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -75,11 +75,6 @@
bidirectionalS > Graph;
#endif
- typedef graph_traits<Graph>::vertex_descriptor vertex_descriptor;
- typedef graph_traits<Graph>::vertex_iterator vertex_iterator;
- typedef iterator_property_map<std::vector<vertex_descriptor>::iterator, property_map<Graph, vertex_index_t>::type> ParentMap;
- typedef std::pair<int, int> Edge;
-
minstd_rand gen;
gen.seed(seed);
Modified: branches/release/libs/property_map/test/property_map_cc.cpp
==============================================================================
--- branches/release/libs/property_map/test/property_map_cc.cpp Sat Sep 21 15:26:42 2013 (r85812)
+++ branches/release/libs/property_map/test/property_map_cc.cpp 2013-09-21 16:17:00 EDT (Sat, 21 Sep 2013) (r85813)
@@ -107,7 +107,6 @@
{
typedef sgi_assignable_archetype<> Key; // ?
typedef sgi_assignable_archetype<> Value;
- typedef random_access_iterator_archetype<Value> Iterator;
typedef readable_property_map_archetype<Key, std::ptrdiff_t> IndexMap;
typedef shared_array_property_map<Value, IndexMap> PMap;
function_requires<Mutable_LvaluePropertyMapConcept<PMap, Key> >();
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