Fix biNodeConnected() function (#439)
authorBalazs Dezso <deba@google.com>
Thu, 08 Aug 2013 22:56:10 +0200
changeset 1089552e3d1242c6
parent 1083 3e711ee55d31
child 1090 70b199792735
Fix biNodeConnected() function (#439)
lemon/connectivity.h
test/connectivity_test.cc
     1.1 --- a/lemon/connectivity.h	Wed Aug 07 06:29:34 2013 +0200
     1.2 +++ b/lemon/connectivity.h	Thu Aug 08 22:56:10 2013 +0200
     1.3 @@ -744,8 +744,9 @@
     1.4    ///
     1.5    /// \brief Check whether an undirected graph is bi-node-connected.
     1.6    ///
     1.7 -  /// This function checks whether the given undirected graph is 
     1.8 -  /// bi-node-connected, i.e. any two edges are on same circle.
     1.9 +  /// This function checks whether the given undirected graph is
    1.10 +  /// bi-node-connected, i.e. a connected graph without articulation
    1.11 +  /// node.
    1.12    ///
    1.13    /// \return \c true if the graph bi-node-connected.
    1.14    /// \note By definition, the empty graph is bi-node-connected.
    1.15 @@ -753,6 +754,22 @@
    1.16    /// \see countBiNodeConnectedComponents(), biNodeConnectedComponents()
    1.17    template <typename Graph>
    1.18    bool biNodeConnected(const Graph& graph) {
    1.19 +    bool hasNonIsolated = false, hasIsolated = false;
    1.20 +    for (typename Graph::NodeIt n(graph); n != INVALID; ++n) {
    1.21 +      if (typename Graph::OutArcIt(graph, n) == INVALID) {
    1.22 +        if (hasIsolated || hasNonIsolated) {
    1.23 +          return false;
    1.24 +        } else {
    1.25 +          hasIsolated = true;
    1.26 +        }
    1.27 +      } else {
    1.28 +        if (hasIsolated) {
    1.29 +          return false;
    1.30 +        } else {
    1.31 +          hasNonIsolated = true;
    1.32 +        }
    1.33 +      }
    1.34 +    }
    1.35      return countBiNodeConnectedComponents(graph) <= 1;
    1.36    }
    1.37  
     2.1 --- a/test/connectivity_test.cc	Wed Aug 07 06:29:34 2013 +0200
     2.2 +++ b/test/connectivity_test.cc	Thu Aug 08 22:56:10 2013 +0200
     2.3 @@ -99,6 +99,23 @@
     2.4    }
     2.5  
     2.6    {
     2.7 +    ListGraph g;
     2.8 +    ListGraph::NodeMap<bool> map(g);
     2.9 +
    2.10 +    ListGraph::Node n1 = g.addNode();
    2.11 +    ListGraph::Node n2 = g.addNode();
    2.12 +
    2.13 +    ListGraph::Edge e1 = g.addEdge(n1, n2);
    2.14 +    ::lemon::ignore_unused_variable_warning(e1);
    2.15 +    check(biNodeConnected(g), "Graph is bi-node-connected");
    2.16 +
    2.17 +    ListGraph::Node n3 = g.addNode();
    2.18 +    ::lemon::ignore_unused_variable_warning(n3);
    2.19 +    check(!biNodeConnected(g), "Graph is not bi-node-connected");
    2.20 +  }
    2.21 +
    2.22 +
    2.23 +  {
    2.24      Digraph d;
    2.25      Digraph::NodeMap<int> order(d);
    2.26      Graph g(d);