Changeset 1089:552e3d1242c6 in lemon-main

Timestamp:

08/08/13 22:56:10 (11 years ago)

Author:

Balazs Dezso <deba@…>

Branch:

default

Phase:

public

Message:

Fix biNodeConnected() function (#439)

Files:

• lemon/connectivity.h (modified) (2 diffs)
• test/connectivity_test.cc (modified) (1 diff)

lemon/connectivity.h

@@ -745 +745 @@
   /// \brief Check whether an undirected graph is bi-node-connected.
   ///
-  /// This function checks whether the given undirected graph is 
-  /// bi-node-connected, i.e. any two edges are on same circle.
+  /// This function checks whether the given undirected graph is
+  /// bi-node-connected, i.e. a connected graph without articulation
+  /// node.
   ///
   /// \return \c true if the graph bi-node-connected.
@@ -754 +755 @@
   template <typename Graph>
   bool biNodeConnected(const Graph& graph) {
+    bool hasNonIsolated = false, hasIsolated = false;
+    for (typename Graph::NodeIt n(graph); n != INVALID; ++n) {
+      if (typename Graph::OutArcIt(graph, n) == INVALID) {
+        if (hasIsolated || hasNonIsolated) {
+          return false;
+        } else {
+          hasIsolated = true;
+        }
+      } else {
+        if (hasIsolated) {
+          return false;
+        } else {
+          hasNonIsolated = true;
+        }
+      }
+    }
     return countBiNodeConnectedComponents(graph) <= 1;
   }

test/connectivity_test.cc

@@ -98 +98 @@
     check(simpleGraph(g), "This graph is simple.");
   }
+
+  {
+    ListGraph g;
+    ListGraph::NodeMap<bool> map(g);
+
+    ListGraph::Node n1 = g.addNode();
+    ListGraph::Node n2 = g.addNode();
+
+    ListGraph::Edge e1 = g.addEdge(n1, n2);
+    ::lemon::ignore_unused_variable_warning(e1);
+    check(biNodeConnected(g), "Graph is bi-node-connected");
+
+    ListGraph::Node n3 = g.addNode();
+    ::lemon::ignore_unused_variable_warning(n3);
+    check(!biNodeConnected(g), "Graph is not bi-node-connected");
+  }
+
 
   {