|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r76536 - in branches/release: . boost boost/algorithm/string boost/algorithm/string/detail boost/archive boost/bimap boost/config boost/date_time boost/date_time/posix_time boost/detail boost/dynamic_bitset boost/function boost/functional boost/fusion boost/geometry boost/geometry/domains boost/geometry/io boost/geometry/io/dsv boost/gil boost/graph boost/graph/detail boost/heap boost/icl boost/integer boost/interprocess boost/intrusive boost/io boost/iostreams boost/iterator boost/locale boost/msm boost/msm/back boost/msm/front boost/msm/front/detail boost/msm/front/euml boost/msm/mpl_graph boost/numeric/ublas boost/pool boost/preprocessor boost/program_options boost/program_options/detail boost/property_tree boost/range boost/regex boost/serialization boost/signals boost/signals2 boost/spirit boost/spirit/home boost/spirit/home/karma boost/spirit/home/support boost/statechart boost/system boost/thread boost/tr1 boost/type_traits boost/typeof boost/unordered boost/utility boost/uuid boost/variant boost/wave boost/xpressive doc libs libs/algorithm/minmax libs/algorithm/string libs/algorithm/string/doc libs/array libs/array/test libs/bimap libs/config libs/date_time libs/date_time/data libs/date_time/example/gregorian libs/date_time/example/local_time libs/date_time/example/posix_time libs/date_time/example/tutorial libs/date_time/test/posix_time libs/date_time/xmldoc libs/detail libs/function libs/functional libs/fusion libs/geometry libs/geometry/doc libs/graph/doc libs/graph/test libs/graph_parallel libs/heap libs/icl libs/icl/doc libs/icl/doc/html libs/icl/doc/html/header/boost/icl libs/icl/test libs/icl/test/test_doc_code_ libs/integer libs/interprocess libs/intrusive libs/io libs/io/doc libs/iostreams libs/iterator libs/locale libs/locale/src libs/mpi/build libs/mpl/doc/refmanual libs/mpl/doc/src/refmanual libs/msm libs/numeric/ublas libs/numeric/ublas/doc libs/parameter/doc/html libs/phoenix/doc libs/phoenix/doc/examples libs/pool libs/preprocessor libs/program_options libs/program_options/test libs/property_tree libs/range libs/regex libs/serialization libs/serialization/example libs/serialization/src libs/serialization/test libs/signals libs/signals2 libs/signals2/doc libs/spirit libs/spirit/classic/example libs/spirit/doc libs/spirit/example libs/spirit/phoenix libs/spirit/test libs/spirit/test/qi libs/statechart libs/static_assert libs/system libs/thread libs/thread/test libs/timer libs/tr1 libs/type_traits libs/typeof/doc libs/unordered libs/utility libs/utility/swap/test libs/uuid libs/wave more status tools tools/bcp tools/boostbook tools/build/v2 tools/build/v2/tools tools/inspect tools/quickbook tools/regression tools/regression/src tools/release tools/wave
From: jewillco_at_[hidden]
Date: 2012-01-15 18:52:47
Author: jewillco
Date: 2012-01-15 18:52:45 EST (Sun, 15 Jan 2012)
New Revision: 76536
URL: http://svn.boost.org/trac/boost/changeset/76536
Log:
Merged r75066, r75067, r75124, r75140, r75165, r75861, r75862, r75863, r75878, r75906, r75970, r75973, r75974, and r76394 from trunk
Added:
branches/release/libs/graph/doc/edge_predecessor_recorder.html
- copied unchanged from r75862, /trunk/libs/graph/doc/edge_predecessor_recorder.html
Properties modified:
branches/release/ (props changed)
branches/release/INSTALL (props changed)
branches/release/Jamroot (props changed)
branches/release/LICENSE_1_0.txt (props changed)
branches/release/boost/ (props changed)
branches/release/boost-build.jam (props changed)
branches/release/boost.css (props changed)
branches/release/boost.png (props changed)
branches/release/boost/algorithm/string/ (props changed)
branches/release/boost/algorithm/string/detail/case_conv.hpp (props changed)
branches/release/boost/algorithm/string/detail/classification.hpp (props changed)
branches/release/boost/archive/ (props changed)
branches/release/boost/array.hpp (props changed)
branches/release/boost/bimap/ (props changed)
branches/release/boost/concept_check.hpp (props changed)
branches/release/boost/config/ (props changed)
branches/release/boost/config.hpp (props changed)
branches/release/boost/cregex.hpp (props changed)
branches/release/boost/cstdint.hpp (props changed)
branches/release/boost/current_function.hpp (props changed)
branches/release/boost/date_time/c_time.hpp (props changed)
branches/release/boost/date_time/date_formatting.hpp (props changed)
branches/release/boost/date_time/filetime_functions.hpp (props changed)
branches/release/boost/date_time/gregorian_calendar.ipp (props changed)
branches/release/boost/date_time/posix_time/time_serialize.hpp (props changed)
branches/release/boost/date_time/strings_from_facet.hpp (props changed)
branches/release/boost/date_time/time_facet.hpp (props changed)
branches/release/boost/date_time/tz_db_base.hpp (props changed)
branches/release/boost/detail/ (props changed)
branches/release/boost/detail/fenv.hpp (props changed)
branches/release/boost/detail/interlocked.hpp (props changed)
branches/release/boost/dynamic_bitset/dynamic_bitset.hpp (props changed)
branches/release/boost/function/ (props changed)
branches/release/boost/function/function_template.hpp (props changed)
branches/release/boost/functional/ (props changed)
branches/release/boost/fusion/ (props changed)
branches/release/boost/geometry/ (props changed)
branches/release/boost/geometry/domains/ (props changed)
branches/release/boost/geometry/io/ (props changed)
branches/release/boost/geometry/io/dsv/ (props changed)
branches/release/boost/gil/ (props changed)
branches/release/boost/graph/ (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/interprocess/ (props changed)
branches/release/boost/intrusive/ (props changed)
branches/release/boost/io/ (props changed)
branches/release/boost/iostreams/ (props changed)
branches/release/boost/iterator/ (props changed)
branches/release/boost/iterator/iterator_facade.hpp (props changed)
branches/release/boost/locale/ (props changed)
branches/release/boost/locale.hpp (props changed)
branches/release/boost/math_fwd.hpp (props changed)
branches/release/boost/msm/ (props changed)
branches/release/boost/msm/active_state_switching_policies.hpp (props changed)
branches/release/boost/msm/back/ (props changed)
branches/release/boost/msm/back/args.hpp (props changed)
branches/release/boost/msm/back/bind_helpers.hpp (props changed)
branches/release/boost/msm/back/common_types.hpp (props changed)
branches/release/boost/msm/back/copy_policies.hpp (props changed)
branches/release/boost/msm/back/default_compile_policy.hpp (props changed)
branches/release/boost/msm/back/dispatch_table.hpp (props changed)
branches/release/boost/msm/back/favor_compile_time.hpp (props changed)
branches/release/boost/msm/back/fold_to_list.hpp (props changed)
branches/release/boost/msm/back/history_policies.hpp (props changed)
branches/release/boost/msm/back/metafunctions.hpp (props changed)
branches/release/boost/msm/back/mpl_graph_fsm_check.hpp (props changed)
branches/release/boost/msm/back/no_fsm_check.hpp (props changed)
branches/release/boost/msm/back/queue_container_circular.hpp (props changed)
branches/release/boost/msm/back/queue_container_deque.hpp (props changed)
branches/release/boost/msm/back/state_machine.hpp (props changed)
branches/release/boost/msm/back/tools.hpp (props changed)
branches/release/boost/msm/common.hpp (props changed)
branches/release/boost/msm/front/ (props changed)
branches/release/boost/msm/front/common_states.hpp (props changed)
branches/release/boost/msm/front/completion_event.hpp (props changed)
branches/release/boost/msm/front/detail/ (props changed)
branches/release/boost/msm/front/detail/common_states.hpp (props changed)
branches/release/boost/msm/front/detail/row2_helper.hpp (props changed)
branches/release/boost/msm/front/euml/ (props changed)
branches/release/boost/msm/front/euml/algorithm.hpp (props changed)
branches/release/boost/msm/front/euml/common.hpp (props changed)
branches/release/boost/msm/front/euml/container.hpp (props changed)
branches/release/boost/msm/front/euml/euml.hpp (props changed)
branches/release/boost/msm/front/euml/euml_typeof.hpp (props changed)
branches/release/boost/msm/front/euml/guard_grammar.hpp (props changed)
branches/release/boost/msm/front/euml/iteration.hpp (props changed)
branches/release/boost/msm/front/euml/operator.hpp (props changed)
branches/release/boost/msm/front/euml/phoenix_placeholders.hpp (props changed)
branches/release/boost/msm/front/euml/querying.hpp (props changed)
branches/release/boost/msm/front/euml/state_grammar.hpp (props changed)
branches/release/boost/msm/front/euml/stl.hpp (props changed)
branches/release/boost/msm/front/euml/stt_grammar.hpp (props changed)
branches/release/boost/msm/front/euml/transformation.hpp (props changed)
branches/release/boost/msm/front/functor_row.hpp (props changed)
branches/release/boost/msm/front/internal_row.hpp (props changed)
branches/release/boost/msm/front/row2.hpp (props changed)
branches/release/boost/msm/front/state_machine_def.hpp (props changed)
branches/release/boost/msm/front/states.hpp (props changed)
branches/release/boost/msm/mpl_graph/ (props changed)
branches/release/boost/msm/msm_grammar.hpp (props changed)
branches/release/boost/msm/proto_config.hpp (props changed)
branches/release/boost/msm/row_tags.hpp (props changed)
branches/release/boost/numeric/ublas/ (props changed)
branches/release/boost/numeric/ublas/functional.hpp (props changed)
branches/release/boost/pool/ (props changed)
branches/release/boost/preprocessor/ (props changed)
branches/release/boost/program_options/ (props changed)
branches/release/boost/program_options/detail/parsers.hpp (props changed)
branches/release/boost/program_options/parsers.hpp (props changed)
branches/release/boost/property_tree/ (props changed)
branches/release/boost/range/ (props changed)
branches/release/boost/regex/ (props changed)
branches/release/boost/regex.h (props changed)
branches/release/boost/regex.hpp (props changed)
branches/release/boost/regex_fwd.hpp (props changed)
branches/release/boost/serialization/ (props changed)
branches/release/boost/signals/ (props changed)
branches/release/boost/signals2/ (props changed)
branches/release/boost/signals2.hpp (props changed)
branches/release/boost/spirit/ (props changed)
branches/release/boost/spirit/home/ (props changed)
branches/release/boost/spirit/home/karma/ (props changed)
branches/release/boost/spirit/home/support/attributes.hpp (props changed)
branches/release/boost/statechart/ (props changed)
branches/release/boost/static_assert.hpp (props changed)
branches/release/boost/system/ (props changed)
branches/release/boost/thread/ (props changed)
branches/release/boost/thread.hpp (props changed)
branches/release/boost/timer.hpp (props changed)
branches/release/boost/token_functions.hpp (props changed)
branches/release/boost/tr1/ (props changed)
branches/release/boost/type_traits/ (props changed)
branches/release/boost/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/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/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/array/ (props changed)
branches/release/libs/array/test/array0.cpp (props changed)
branches/release/libs/array/test/array2.cpp (props changed)
branches/release/libs/array/test/array6.cpp (props changed)
branches/release/libs/bimap/ (props changed)
branches/release/libs/config/ (props changed)
branches/release/libs/date_time/ (props changed)
branches/release/libs/date_time/data/date_time_zonespec.csv (props changed)
branches/release/libs/date_time/example/gregorian/days_between_new_years.cpp (props changed)
branches/release/libs/date_time/example/gregorian/days_since_year_start.cpp (props changed)
branches/release/libs/date_time/example/gregorian/days_till_new_year.cpp (props changed)
branches/release/libs/date_time/example/gregorian/month_add.cpp (props changed)
branches/release/libs/date_time/example/local_time/flight.cpp (props changed)
branches/release/libs/date_time/example/local_time/local_date_time.cpp (props changed)
branches/release/libs/date_time/example/posix_time/print_hours.cpp (props changed)
branches/release/libs/date_time/example/posix_time/time_math.cpp (props changed)
branches/release/libs/date_time/example/tutorial/io_tutorial.cpp (props changed)
branches/release/libs/date_time/test/posix_time/testtime_facet.cpp (props changed)
branches/release/libs/date_time/test/posix_time/testtime_input_facet.cpp (props changed)
branches/release/libs/date_time/xmldoc/date_class.xml (props changed)
branches/release/libs/date_time/xmldoc/usage_examples.xml (props changed)
branches/release/libs/detail/ (props changed)
branches/release/libs/function/ (props changed)
branches/release/libs/functional/ (props changed)
branches/release/libs/fusion/ (props changed)
branches/release/libs/geometry/ (props changed)
branches/release/libs/geometry/doc/release_notes.qbk (props changed)
branches/release/libs/geometry/index.html (props changed)
branches/release/libs/graph/doc/ (props changed)
branches/release/libs/graph_parallel/ (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/header/boost/icl/ (props changed)
branches/release/libs/icl/test/ (props changed)
branches/release/libs/icl/test/test_doc_code_/ (props changed)
branches/release/libs/integer/ (props changed)
branches/release/libs/interprocess/ (props changed)
branches/release/libs/intrusive/ (props changed)
branches/release/libs/io/ (props changed)
branches/release/libs/io/doc/ (props changed)
branches/release/libs/iostreams/ (props changed)
branches/release/libs/iterator/ (props changed)
branches/release/libs/libraries.htm (props changed)
branches/release/libs/locale/ (props changed)
branches/release/libs/locale/src/ (props changed)
branches/release/libs/maintainers.txt (props changed)
branches/release/libs/mpi/build/ (props changed)
branches/release/libs/mpl/doc/refmanual/broken-compiler-workarounds.html (props changed)
branches/release/libs/mpl/doc/refmanual/categorized-index-concepts.html (props changed)
branches/release/libs/mpl/doc/refmanual/cfg-no-preprocessed-headers.html (props changed)
branches/release/libs/mpl/doc/refmanual/composition-and-argument-binding.html (props changed)
branches/release/libs/mpl/doc/refmanual/data-types-concepts.html (props changed)
branches/release/libs/mpl/doc/refmanual/data-types-miscellaneous.html (props changed)
branches/release/libs/mpl/doc/refmanual/extensible-associative-sequence.html (props changed)
branches/release/libs/mpl/doc/refmanual/inserter-class.html (props changed)
branches/release/libs/mpl/doc/refmanual/tag-dispatched-metafunction.html (props changed)
branches/release/libs/mpl/doc/refmanual/trivial-metafunctions-summary.html (props changed)
branches/release/libs/mpl/doc/src/refmanual/Iterators-Iterator.rst (props changed)
branches/release/libs/msm/ (props changed)
branches/release/libs/numeric/ublas/ (props changed)
branches/release/libs/numeric/ublas/doc/ (props changed)
branches/release/libs/parameter/doc/html/index.html (props changed)
branches/release/libs/phoenix/doc/basics.qbk (props changed)
branches/release/libs/phoenix/doc/examples/extending_actors.qbk (props changed)
branches/release/libs/phoenix/doc/organisation.qbk (props changed)
branches/release/libs/pool/ (props changed)
branches/release/libs/preprocessor/ (props changed)
branches/release/libs/program_options/ (props changed)
branches/release/libs/program_options/test/parsers_test.cpp (props changed)
branches/release/libs/property_tree/ (props changed)
branches/release/libs/range/ (props changed)
branches/release/libs/regex/ (props changed)
branches/release/libs/serialization/ (props changed)
branches/release/libs/serialization/example/ (props changed)
branches/release/libs/serialization/src/ (props changed)
branches/release/libs/serialization/test/test_diamond_complex.cpp (props changed)
branches/release/libs/signals/ (props changed)
branches/release/libs/signals2/ (props changed)
branches/release/libs/signals2/doc/ (props changed)
branches/release/libs/spirit/ (props changed)
branches/release/libs/spirit/classic/example/ (props changed)
branches/release/libs/spirit/doc/ (props changed)
branches/release/libs/spirit/example/ (props changed)
branches/release/libs/spirit/phoenix/ (props changed)
branches/release/libs/spirit/test/ (props changed)
branches/release/libs/spirit/test/qi/optional.cpp (props changed)
branches/release/libs/statechart/ (props changed)
branches/release/libs/static_assert/ (props changed)
branches/release/libs/system/ (props changed)
branches/release/libs/thread/ (props changed)
branches/release/libs/thread/test/ (props changed)
branches/release/libs/timer/ (props changed)
branches/release/libs/tr1/ (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/swap.html (props changed)
branches/release/libs/utility/swap/test/std_bitset.cpp (props changed)
branches/release/libs/utility/value_init.htm (props changed)
branches/release/libs/utility/value_init_test.cpp (props changed)
branches/release/libs/uuid/ (props changed)
branches/release/libs/wave/ (props changed)
branches/release/more/ (props changed)
branches/release/rst.css (props changed)
branches/release/status/ (props changed)
branches/release/status/Jamfile.v2 (props changed)
branches/release/status/expected_results.xml (props changed)
branches/release/status/explicit-failures-markup.xml (props changed)
branches/release/status/explicit-failures.xsd (props changed)
branches/release/tools/ (props changed)
branches/release/tools/bcp/ (props changed)
branches/release/tools/boostbook/ (props changed)
branches/release/tools/build/v2/ (props changed)
branches/release/tools/build/v2/tools/mpi.jam (props changed)
branches/release/tools/inspect/ (props changed)
branches/release/tools/quickbook/ (props changed)
branches/release/tools/regression/ (props changed)
branches/release/tools/regression/src/library_status.cpp (props changed)
branches/release/tools/release/ (props changed)
branches/release/tools/wave/ (props changed)
Text files modified:
branches/release/boost/graph/biconnected_components.hpp | 79 +++++++++++++++++++--------------------
branches/release/boost/graph/chrobak_payne_drawing.hpp | 1
branches/release/boost/graph/copy.hpp | 29 ++++++++++++++
branches/release/boost/graph/detail/adjacency_list.hpp | 11 -----
branches/release/boost/graph/directed_graph.hpp | 2
branches/release/boost/graph/isomorphism.hpp | 4 +-
branches/release/boost/graph/kamada_kawai_spring_layout.hpp | 4 +-
branches/release/boost/graph/leda_graph.hpp | 8 ++--
branches/release/boost/graph/undirected_graph.hpp | 2
branches/release/libs/graph/doc/distance_recorder.html | 2
branches/release/libs/graph/doc/isomorphism-impl.w | 2
branches/release/libs/graph/doc/predecessor_recorder.html | 4 +-
branches/release/libs/graph/doc/prim_minimum_spanning_tree.html | 1
branches/release/libs/graph/doc/table_of_contents.html | 1
branches/release/libs/graph/test/Jamfile.v2 | 24 ++++++------
branches/release/libs/graph/test/biconnected_components_test.cpp | 49 ++++++++++++++++--------
16 files changed, 128 insertions(+), 95 deletions(-)
Modified: branches/release/boost/graph/biconnected_components.hpp
==============================================================================
--- branches/release/boost/graph/biconnected_components.hpp (original)
+++ branches/release/boost/graph/biconnected_components.hpp 2012-01-15 18:52:45 EST (Sun, 15 Jan 2012)
@@ -36,19 +36,21 @@
(ComponentMap comp, std::size_t& c, DiscoverTimeMap dtm,
std::size_t& dfs_time, LowPointMap lowpt, PredecessorMap pred,
OutputIterator out, Stack& S, DFSVisitor vis)
- : comp(comp), c(c), dtm(dtm), dfs_time(dfs_time), lowpt(lowpt),
+ : comp(comp), c(c), children_of_root(0), dtm(dtm),
+ dfs_time(dfs_time), lowpt(lowpt),
pred(pred), out(out), S(S), vis(vis) { }
template <typename Vertex, typename Graph>
void initialize_vertex(const Vertex& u, Graph& g)
{
+ put(pred, u, u);
vis.initialize_vertex(u, g);
}
template <typename Vertex, typename Graph>
void start_vertex(const Vertex& u, Graph& g)
{
- put(pred, u, u);
+ children_of_root = 0;
vis.start_vertex(u, g);
}
@@ -69,8 +71,14 @@
template <typename Edge, typename Graph>
void tree_edge(const Edge& e, Graph& g)
{
+ typename boost::graph_traits<Graph>::vertex_descriptor src = source(e, g);
+ typename boost::graph_traits<Graph>::vertex_descriptor tgt = target(e, g);
+
S.push(e);
- put(pred, target(e, g), source(e, g));
+ put(pred, tgt, src);
+ if ( get(pred, src) == src ) {
+ ++children_of_root;
+ }
vis.tree_edge(e, g);
}
@@ -79,11 +87,14 @@
{
BOOST_USING_STD_MIN();
- if ( target(e, g) != get(pred, source(e, g)) ) {
+ typename boost::graph_traits<Graph>::vertex_descriptor src = source(e, g);
+ typename boost::graph_traits<Graph>::vertex_descriptor tgt = target(e, g);
+ if ( ( tgt != get(pred, src) || get(pred, src) == src ) &&
+ get(dtm, tgt) < get(dtm, src) ) {
S.push(e);
- put(lowpt, source(e, g),
- min BOOST_PREVENT_MACRO_SUBSTITUTION(get(lowpt, source(e, g)),
- get(dtm, target(e, g))));
+ put(lowpt, src,
+ min BOOST_PREVENT_MACRO_SUBSTITUTION(get(lowpt, src),
+ get(dtm, tgt)));
}
vis.back_edge(e, g);
}
@@ -99,49 +110,35 @@
{
BOOST_USING_STD_MIN();
Vertex parent = get(pred, u);
- const std::size_t dtm_of_dubious_parent = get(dtm, parent);
- bool is_art_point = false;
- if ( dtm_of_dubious_parent > get(dtm, u) ) {
- parent = get(pred, parent);
- is_art_point = true;
- put(pred, get(pred, u), u);
- put(pred, u, parent);
+ if (parent == u) { // Root of tree is special
+ if (children_of_root >= 2) {
+ *out++ = u;
+ }
+ return;
}
-
- if ( parent == u ) { // at top
- if ( get(dtm, u) + 1 == dtm_of_dubious_parent )
- is_art_point = false;
- } else {
- put(lowpt, parent,
- min BOOST_PREVENT_MACRO_SUBSTITUTION(get(lowpt, parent),
- get(lowpt, u)));
-
- if (get(lowpt, u) >= get(dtm, parent)) {
- if ( get(dtm, parent) > get(dtm, get(pred, parent)) ) {
- put(pred, u, get(pred, parent));
- put(pred, parent, u);
- }
-
- while ( get(dtm, source(S.top(), g)) >= get(dtm, u) ) {
- put(comp, S.top(), c);
- S.pop();
- }
+ put(lowpt, parent,
+ min BOOST_PREVENT_MACRO_SUBSTITUTION(get(lowpt, parent),
+ get(lowpt, u)));
+ if ( get(lowpt, u) >= get(dtm, parent) ) {
+ if ( get(pred, parent) != parent ) {
+ *out++ = parent;
+ }
+ while ( get(dtm, source(S.top(), g)) >= get(dtm, u) ) {
put(comp, S.top(), c);
- S.pop();
- ++c;
- if ( S.empty() ) {
- put(pred, u, parent);
- put(pred, parent, u);
- }
+ S.pop();
}
+ assert (source(S.top(), g) == parent);
+ assert (target(S.top(), g) == u);
+ put(comp, S.top(), c);
+ S.pop();
+ ++c;
}
- if ( is_art_point )
- *out++ = u;
vis.finish_vertex(u, g);
}
ComponentMap comp;
std::size_t& c;
+ std::size_t children_of_root;
DiscoverTimeMap dtm;
std::size_t& dfs_time;
LowPointMap lowpt;
Modified: branches/release/boost/graph/chrobak_payne_drawing.hpp
==============================================================================
--- branches/release/boost/graph/chrobak_payne_drawing.hpp (original)
+++ branches/release/boost/graph/chrobak_payne_drawing.hpp 2012-01-15 18:52:45 EST (Sun, 15 Jan 2012)
@@ -11,6 +11,7 @@
#include <vector>
#include <list>
+#include <stack>
#include <boost/config.hpp>
#include <boost/utility.hpp> //for next and prior
#include <boost/graph/graph_traits.hpp>
Modified: branches/release/boost/graph/copy.hpp
==============================================================================
--- branches/release/boost/graph/copy.hpp (original)
+++ branches/release/boost/graph/copy.hpp 2012-01-15 18:52:45 EST (Sun, 15 Jan 2012)
@@ -69,6 +69,33 @@
}
};
+ // Add a reverse_graph_edge_descriptor wrapper if the Graph is a
+ // reverse_graph but the edge descriptor is from the original graph (this
+ // case comes from the fact that transpose_graph uses reverse_graph
+ // internally but doesn't expose the different edge descriptor type to the
+ // user).
+ template <typename Desc, typename Graph>
+ struct add_reverse_edge_descriptor {
+ typedef Desc type;
+ static Desc convert(const Desc& d) {return d;}
+ };
+
+ template <typename Desc, typename G, typename GR>
+ struct add_reverse_edge_descriptor<Desc, boost::reverse_graph<G, GR> > {
+ typedef reverse_graph_edge_descriptor<Desc> type;
+ static reverse_graph_edge_descriptor<Desc> convert(const Desc& d) {
+ return reverse_graph_edge_descriptor<Desc>(d);
+ }
+ };
+
+ template <typename Desc, typename G, typename GR>
+ struct add_reverse_edge_descriptor<reverse_graph_edge_descriptor<Desc>, boost::reverse_graph<G, GR> > {
+ typedef reverse_graph_edge_descriptor<Desc> type;
+ static reverse_graph_edge_descriptor<Desc> convert(const reverse_graph_edge_descriptor<Desc>& d) {
+ return d;
+ }
+ };
+
// Default edge and vertex property copiers
template <typename Graph1, typename Graph2>
@@ -79,7 +106,7 @@
template <typename Edge1, typename Edge2>
void operator()(const Edge1& e1, Edge2& e2) const {
- put(edge_all_map2, e2, get(edge_all_map1, e1));
+ put(edge_all_map2, e2, get(edge_all_map1, add_reverse_edge_descriptor<Edge1, Graph1>::convert(e1)));
}
typename property_map<Graph1, edge_all_t>::const_type edge_all_map1;
mutable typename property_map<Graph2, edge_all_t>::type edge_all_map2;
Modified: branches/release/boost/graph/detail/adjacency_list.hpp
==============================================================================
--- branches/release/boost/graph/detail/adjacency_list.hpp (original)
+++ branches/release/boost/graph/detail/adjacency_list.hpp 2012-01-15 18:52:45 EST (Sun, 15 Jan 2012)
@@ -2759,17 +2759,6 @@
#if !defined(BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION)
namespace boost {
- #if BOOST_WORKAROUND( _STLPORT_VERSION, >= 0x500 )
- // STLport 5 already defines a hash<void*> specialization.
- #else
- template <>
- struct hash< void* > // Need this when vertex_descriptor=void*
- {
- std::size_t
- operator()(void* v) const { return (std::size_t)v; }
- };
- #endif
-
template <typename V>
struct hash< boost::detail::stored_edge<V> >
{
Modified: branches/release/boost/graph/directed_graph.hpp
==============================================================================
--- branches/release/boost/graph/directed_graph.hpp (original)
+++ branches/release/boost/graph/directed_graph.hpp 2012-01-15 18:52:45 EST (Sun, 15 Jan 2012)
@@ -410,7 +410,7 @@
typename DIRECTED_GRAPH::vertex_descriptor
vertex(typename DIRECTED_GRAPH::vertices_size_type n,
DIRECTED_GRAPH const& g)
-{ return vertex(g.impl()); }
+{ return vertex(n, g.impl()); }
template <DIRECTED_GRAPH_PARAMS>
std::pair<typename DIRECTED_GRAPH::edge_descriptor, bool>
Modified: branches/release/boost/graph/isomorphism.hpp
==============================================================================
--- branches/release/boost/graph/isomorphism.hpp (original)
+++ branches/release/boost/graph/isomorphism.hpp 2012-01-15 18:52:45 EST (Sun, 15 Jan 2012)
@@ -154,7 +154,7 @@
{
std::vector<size_type> multiplicity(max_invariant, 0);
BGL_FORALL_VERTICES_T(v, G1, Graph1)
- ++multiplicity[invariant1(v)];
+ ++multiplicity.at(invariant1(v));
sort(V_mult, compare_multiplicity(invariant1, &multiplicity[0]));
}
@@ -303,7 +303,7 @@
}
// The largest possible vertex invariant number
size_type max BOOST_PREVENT_MACRO_SUBSTITUTION () const {
- return (m_max_vertex_in_degree + 2) * m_max_vertex_out_degree + 1;
+ return (m_max_vertex_in_degree + 1) * (m_max_vertex_out_degree + 1);
}
private:
InDegreeMap m_in_degree_map;
Modified: branches/release/boost/graph/kamada_kawai_spring_layout.hpp
==============================================================================
--- branches/release/boost/graph/kamada_kawai_spring_layout.hpp (original)
+++ branches/release/boost/graph/kamada_kawai_spring_layout.hpp 2012-01-15 18:52:45 EST (Sun, 15 Jan 2012)
@@ -218,7 +218,7 @@
detail::graph::compute_edge_length(g, distance, index,
edge_or_side_length);
- std::cerr << "edge_length = " << edge_length << std::endl;
+ // std::cerr << "edge_length = " << edge_length << std::endl;
// Compute l_{ij} and k_{ij}
const weight_type K = spring_constant;
@@ -275,7 +275,7 @@
E += .5 * k_ij * (dist - l_ij) * (dist - l_ij);
}
}
- std::cerr << "E = " << E << std::endl;
+ // std::cerr << "E = " << E << std::endl;
// Compute the elements of the Jacobian
// From
Modified: branches/release/boost/graph/leda_graph.hpp
==============================================================================
--- branches/release/boost/graph/leda_graph.hpp (original)
+++ branches/release/boost/graph/leda_graph.hpp 2012-01-15 18:52:45 EST (Sun, 15 Jan 2012)
@@ -17,9 +17,9 @@
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/properties.hpp>
-#include <LEDA/graph.h>
-#include <LEDA/node_array.h>
-#include <LEDA/node_map.h>
+#include <LEDA/graph/graph.h>
+#include <LEDA/graph/node_array.h>
+#include <LEDA/graph/node_map.h>
// The functions and classes in this file allows the user to
// treat a LEDA GRAPH object as a boost graph "as is". No
@@ -884,7 +884,7 @@
inline
typename boost::property_traits<
typename boost::property_map<leda::GRAPH<vtype, etype>,PropertyTag>::const_type
-::value_type
+ >::value_type
get(PropertyTag p, const leda::GRAPH<vtype, etype>& g, const Key& key) {
return get(get(p, g), key);
}
Modified: branches/release/boost/graph/undirected_graph.hpp
==============================================================================
--- branches/release/boost/graph/undirected_graph.hpp (original)
+++ branches/release/boost/graph/undirected_graph.hpp 2012-01-15 18:52:45 EST (Sun, 15 Jan 2012)
@@ -413,7 +413,7 @@
typename UNDIRECTED_GRAPH::vertex_descriptor
vertex(typename UNDIRECTED_GRAPH::vertices_size_type n,
UNDIRECTED_GRAPH const& g)
-{ return vertex(g.impl()); }
+{ return vertex(n, g.impl()); }
template <UNDIRECTED_GRAPH_PARAMS>
std::pair<typename UNDIRECTED_GRAPH::edge_descriptor, bool>
Modified: branches/release/libs/graph/doc/distance_recorder.html
==============================================================================
--- branches/release/libs/graph/doc/distance_recorder.html (original)
+++ branches/release/libs/graph/doc/distance_recorder.html 2012-01-15 18:52:45 EST (Sun, 15 Jan 2012)
@@ -153,7 +153,7 @@
<a href="./visitor_concepts.html">Visitor concepts</a>
<p>
The following are other event visitors: <a
- href="./distance_recorder.html"><tt>predecessor_recorder</tt></a>,
+ href="./predecessor_recorder.html"><tt>predecessor_recorder</tt></a>,
<a href="./time_stamper.html"><tt>time_stamper</tt></a>,
and property_writer.
Modified: branches/release/libs/graph/doc/isomorphism-impl.w
==============================================================================
--- branches/release/libs/graph/doc/isomorphism-impl.w (original)
+++ branches/release/libs/graph/doc/isomorphism-impl.w 2012-01-15 18:52:45 EST (Sun, 15 Jan 2012)
@@ -174,7 +174,7 @@
number. The number of vertices in a graph with the same vertex
invariant number $i$ is called the \emph{invariant multiplicity} for
$i$. In this implementation, by default we use the out-degree of the
-vertex as the vertex invariant, though the user can also supply there
+vertex as the vertex invariant, though the user can also supply their
own invariant function. The ability of the invariant function to prune
the search space varies widely with the type of graph.
Modified: branches/release/libs/graph/doc/predecessor_recorder.html
==============================================================================
--- branches/release/libs/graph/doc/predecessor_recorder.html (original)
+++ branches/release/libs/graph/doc/predecessor_recorder.html 2012-01-15 18:52:45 EST (Sun, 15 Jan 2012)
@@ -31,7 +31,7 @@
<p>
<tt>predecessor_recorder</tt> can be used with graph algorithms by
-wrapping it with the algorithm specific adaptor, such as <a
+wrapping it with an algorithm-specific adaptor, such as <a
href="./bfs_visitor.html"><tt>bfs_visitor</tt></a> and <a
href="./dfs_visitor.html"><tt>dfs_visitor</tt></a>. Also, this event
visitor can be combined with other event visitors using
@@ -44,7 +44,7 @@
predecessor to itself, thereby identifying the root vertex as the only
vertex which is its own parent. When using an algorithm like
depth-first search that creates a forest (multiple search trees) it
-is useful to intialize the predecessor of every vertex to itself. This
+is useful to initialize the predecessor of every vertex to itself. This
way all the root nodes can be distinguished.
Modified: branches/release/libs/graph/doc/prim_minimum_spanning_tree.html
==============================================================================
--- branches/release/libs/graph/doc/prim_minimum_spanning_tree.html (original)
+++ branches/release/libs/graph/doc/prim_minimum_spanning_tree.html 2012-01-15 18:52:45 EST (Sun, 15 Jan 2012)
@@ -67,6 +67,7 @@
<b>for</b> each vertex <i>u</i> <i>in</i> <i>V[G]</i>
<i>color[u] :=</i> WHITE
<i>d[u] :=</i> <i>infinity</i>
+ <b>end for</b>
<i>color[s] :=</i> GRAY
<i>d[s] := 0</i>
ENQUEUE(<i>PQ</i>, <i>s</i>)
Modified: branches/release/libs/graph/doc/table_of_contents.html
==============================================================================
--- branches/release/libs/graph/doc/table_of_contents.html (original)
+++ branches/release/libs/graph/doc/table_of_contents.html 2012-01-15 18:52:45 EST (Sun, 15 Jan 2012)
@@ -90,6 +90,7 @@
<li>Event Visitors
<OL>
<LI>predecessor_recorder
+ <LI>edge_predecessor_recorder
<LI>distance_recorder
<LI>time_stamper
<LI>property_writer
Modified: branches/release/libs/graph/test/Jamfile.v2
==============================================================================
--- branches/release/libs/graph/test/Jamfile.v2 (original)
+++ branches/release/libs/graph/test/Jamfile.v2 2012-01-15 18:52:45 EST (Sun, 15 Jan 2012)
@@ -8,6 +8,7 @@
# LEDA (also top level directory) at the command line of jam using -s
import modules ;
+import path ;
path-constant TEST_DIR : . ;
@@ -124,23 +125,22 @@
;
# Run SDB tests only when -sSDB= is set.
-if [ modules.peek : SDB ] != ""
+local SDB = [ modules.peek : SDB ] ;
+if $(SDB)
{
- local SDB_DEPENDENCIES =
- <include>$(SGB) <library-file>$(SGB)/libgb.a ;
+ local sdb-root = [ path.root [ path.make $(SDB) ] [ path.pwd ] ] ;
- compile stanford_graph_cc.cpp
- $(SDB_DEPENDENCIES) ;
+ compile stanford_graph_cc.cpp :
+ <include>$(sdb-root) ;
}
# Run LEDA tests only when -sLEDA= is set.
-if [ modules.peek : LEDA ] != ""
+local LEDA = [ modules.peek : LEDA ] ;
+if $(LEDA)
{
- local LEDA_DEPENDENCIES =
- <include>$(LEDA)/incl
- <library-file>$(LEDA)/libG.a
- ;
+ local leda-root = [ path.root [ path.make $(LEDA) ] [ path.pwd ] ] ;
+ local leda-include = [ path.join $(leda-root) incl ] ;
- compile leda_graph_cc.cpp
- $(LEDA_DEPENDENCIES) ;
+ compile leda_graph_cc.cpp :
+ <include>$(leda-include) ;
}
Modified: branches/release/libs/graph/test/biconnected_components_test.cpp
==============================================================================
--- branches/release/libs/graph/test/biconnected_components_test.cpp (original)
+++ branches/release/libs/graph/test/biconnected_components_test.cpp 2012-01-15 18:52:45 EST (Sun, 15 Jan 2012)
@@ -77,23 +77,11 @@
} else std::cout << "OK." << std::endl;
}
-int test_main(int argc, char* argv[])
-{
- std::size_t n = 100;
- std::size_t m = 500;
- std::size_t seed = 1;
+typedef adjacency_list<listS, vecS, undirectedS,
+ no_property, EdgeProperty> Graph;
+typedef graph_traits<Graph>::vertex_descriptor Vertex;
- if (argc > 1) n = lexical_cast<std::size_t>(argv[1]);
- if (argc > 2) m = lexical_cast<std::size_t>(argv[2]);
- if (argc > 3) seed = lexical_cast<std::size_t>(argv[3]);
-
- typedef adjacency_list<listS, vecS, undirectedS,
- no_property, EdgeProperty> Graph;
- typedef graph_traits<Graph>::vertex_descriptor Vertex;
-
- Graph g(n);
- minstd_rand gen(seed);
- generate_random_graph(g, n, m, gen);
+bool test_graph(Graph& g) { // Returns false on failure
std::vector<Vertex> art_points;
std::cout << "Computing biconnected components & articulation points... ";
@@ -127,5 +115,34 @@
out << "}\n";
}
+ return any_errors;
+}
+
+int test_main(int argc, char* argv[])
+{
+ std::size_t n = 100;
+ std::size_t m = 500;
+ std::size_t seed = 1;
+
+ if (argc > 1) n = lexical_cast<std::size_t>(argv[1]);
+ if (argc > 2) m = lexical_cast<std::size_t>(argv[2]);
+ if (argc > 3) seed = lexical_cast<std::size_t>(argv[3]);
+
+ {
+ Graph g(n);
+ minstd_rand gen(seed);
+ generate_random_graph(g, n, m, gen);
+ if (test_graph(g)) return 1;
+ }
+
+ {
+ Graph g(4);
+ add_edge(2, 3, g);
+ add_edge(0, 3, g);
+ add_edge(0, 2, g);
+ add_edge(1, 0, g);
+ if (test_graph(g)) return 1;
+ }
+
return 0;
}
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