[Boost-commit] svn:boost r75067 - trunk/boost/graph

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;