Changeset 1091:9eac00ea588f in lemon-main

Timestamp:

08/09/13 14:07:27 (11 years ago)

Author:

Alpar Juttner <alpar@…>

Branch:

default

Parents:

1088:4000b7ef4e01 (diff), 1090:70b199792735 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.

Phase:

public

Message:

Merge bugfix #439

Files:

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

lemon/connectivity.h

@@ -746 +746 @@
   ///
   /// This function checks whether the given undirected graph is
-  /// bi-node-connected, i.e. any two edges are on same circle.
+  /// bi-node-connected, i.e. a connected graph without articulation
+  /// node.
   ///
   /// \return \c true if the graph bi-node-connected.
-  /// \note By definition, the empty graph is bi-node-connected.
+  ///
+  /// \note By definition,
+  /// \li a graph consisting of zero or one node is bi-node-connected,
+  /// \li a graph consisting of two isolated nodes
+  /// is \e not bi-node-connected and
+  /// \li a graph consisting of two nodes connected by an edge
+  /// is bi-node-connected.
   ///
   /// \see countBiNodeConnectedComponents(), biNodeConnectedComponents()
   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;
   }

lemon/connectivity.h

@@ -3 +3 @@
  * This file is a part of LEMON, a generic C++ optimization library.
  *
- * Copyright (C) 2003-2009
+ * Copyright (C) 2003-2010
  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
  * (Egervary Research Group on Combinatorial Optimization, EGRES).
@@ -259 +259 @@
   /// \return \c true if the digraph is strongly connected.
   /// \note By definition, the empty digraph is strongly connected.
-  /// 
+  ///
   /// \see countStronglyConnectedComponents(), stronglyConnectedComponents()
   /// \see connected()
@@ -311 +311 @@
   /// \ingroup graph_properties
   ///
-  /// \brief Count the number of strongly connected components of a 
+  /// \brief Count the number of strongly connected components of a
   /// directed graph
   ///
@@ -782 +782 @@
   /// \ingroup graph_properties
   ///
-  /// \brief Count the number of bi-node-connected components of an 
+  /// \brief Count the number of bi-node-connected components of an
   /// undirected graph.
   ///
@@ -836 +836 @@
   /// \retval compMap A writable edge map. The values will be set from 0
   /// to the number of the bi-node-connected components minus one. Each
-  /// value of the map will be set exactly once, and the values of a 
+  /// value of the map will be set exactly once, and the values of a
   /// certain component will be set continuously.
   /// \return The number of bi-node-connected components.
@@ -882 +882 @@
   ///
   /// \param graph The undirected graph.
-  /// \retval cutMap A writable node map. The values will be set to 
+  /// \retval cutMap A writable node map. The values will be set to
   /// \c true for the nodes that separate two or more components
   /// (exactly once for each cut node), and will not be changed for
@@ -1109 +1109 @@
   /// \brief Check whether an undirected graph is bi-edge-connected.
   ///
-  /// This function checks whether the given undirected graph is 
+  /// This function checks whether the given undirected graph is
   /// bi-edge-connected, i.e. any two nodes are connected with at least
   /// two edge-disjoint paths.
@@ -1216 +1216 @@
   ///
   /// This function finds the bi-edge-connected cut edges in the given
-  /// undirected graph. 
+  /// undirected graph.
   ///
   /// The bi-edge-connected components are the classes of an equivalence
@@ -1373 +1373 @@
   /// \param digraph The digraph.
   /// \retval order A readable and writable node map. The values will be
-  /// set from 0 to the number of the nodes in the digraph minus one. 
+  /// set from 0 to the number of the nodes in the digraph minus one.
   /// Each value of the map will be set exactly once, and the values will
   /// be set descending order.

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");
+  }
+
 
   {

test/connectivity_test.cc

@@ -3 +3 @@
  * This file is a part of LEMON, a generic C++ optimization library.
  *
- * Copyright (C) 2003-2009
+ * Copyright (C) 2003-2010
  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
  * (Egervary Research Group on Combinatorial Optimization, EGRES).
@@ -30 +30 @@
   typedef ListDigraph Digraph;
   typedef Undirector<Digraph> Graph;
-  
+
   {
     Digraph d;
     Digraph::NodeMap<int> order(d);
     Graph g(d);
-    
+
     check(stronglyConnected(d), "The empty digraph is strongly connected");
     check(countStronglyConnectedComponents(d) == 0,
@@ -49 +49 @@
     check(countBiEdgeConnectedComponents(g) == 0,
           "The empty graph has 0 bi-edge-connected component");
-          
+
     check(dag(d), "The empty digraph is DAG.");
     check(checkedTopologicalSort(d, order), "The empty digraph is DAG.");
@@ -84 +84 @@
     check(countBiEdgeConnectedComponents(g) == 1,
           "This graph has 1 bi-edge-connected component");
-          
+
     check(dag(d), "This digraph is DAG.");
     check(checkedTopologicalSort(d, order), "This digraph is DAG.");
@@ -120 +120 @@
     Digraph::NodeMap<int> order(d);
     Graph g(d);
-    
+
     Digraph::Node n1 = d.addNode();
     Digraph::Node n2 = d.addNode();
@@ -127 +127 @@
     Digraph::Node n5 = d.addNode();
     Digraph::Node n6 = d.addNode();
-    
+
     d.addArc(n1, n3);
     d.addArc(n3, n2);
@@ -155 +155 @@
     check(!parallelFree(g), "This graph is not parallel-free.");
     check(!simpleGraph(g), "This graph is not simple.");
-    
+
     d.addArc(n3, n3);
-    
+
     check(!loopFree(d), "This digraph is not loop-free.");
     check(!loopFree(g), "This graph is not loop-free.");
     check(!simpleGraph(d), "This digraph is not simple.");
-    
+
     d.addArc(n3, n2);
-    
+
     check(!parallelFree(d), "This digraph is not parallel-free.");
   }
-  
+
   {
     Digraph d;
     Digraph::ArcMap<bool> cutarcs(d, false);
     Graph g(d);
-    
+
     Digraph::Node n1 = d.addNode();
     Digraph::Node n2 = d.addNode();
@@ -191 +191 @@
     d.addArc(n6, n7);
     d.addArc(n7, n6);
-   
+
     check(!stronglyConnected(d), "This digraph is not strongly connected");
     check(countStronglyConnectedComponents(d) == 3,
@@ -254 +254 @@
     Digraph d;
     Digraph::NodeMap<int> order(d);
-    
+
     Digraph::Node belt = d.addNode();
     Digraph::Node trousers = d.addNode();
@@ -275 +275 @@
     d.addArc(shirt, necktie);
     d.addArc(necktie, coat);
-    
+
     check(dag(d), "This digraph is DAG.");
     topologicalSort(d, order);
@@ -287 +287 @@
     ListGraph g;
     ListGraph::NodeMap<bool> map(g);
-    
+
     ListGraph::Node n1 = g.addNode();
     ListGraph::Node n2 = g.addNode();
@@ -303 +303 @@
     g.addEdge(n4, n7);
     g.addEdge(n5, n7);
-   
+
     check(bipartite(g), "This graph is bipartite");
     check(bipartitePartitions(g, map), "This graph is bipartite");
-    
+
     check(map[n1] == map[n2] && map[n1] == map[n6] && map[n1] == map[n7],
           "Wrong bipartitePartitions()");