Subject: [Boost-commit] svn:boost r75067 - trunk/boost/graph
From: jewillco_at_[hidden]
Date: 2011-10-19 16:03:55
Author: jewillco
Date: 2011-10-19 16:03:54 EDT (Wed, 19 Oct 2011)
New Revision: 75067
URL: http://svn.boost.org/trac/boost/changeset/75067
Log:
Fixed strange use of pred map, and changed algorithm to be more similar to Tarjan paper cited in bibliography; fixes #6033
Text files modified:
trunk/boost/graph/biconnected_components.hpp | 79 +++++++++++++++++++--------------------
1 files changed, 38 insertions(+), 41 deletions(-)
Modified: trunk/boost/graph/biconnected_components.hpp
==============================================================================
--- trunk/boost/graph/biconnected_components.hpp (original)
+++ trunk/boost/graph/biconnected_components.hpp 2011-10-19 16:03:54 EDT (Wed, 19 Oct 2011)
@@ -35,19 +35,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);
}
@@ -68,8 +70,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);
}
@@ -78,11 +86,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);
}
@@ -98,49 +109,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;