author Alpar Juttner Fri, 09 Aug 2013 14:05:29 +0200 branch 1.2 changeset 1268 19087d4f215d parent 1263 b9887ae63df0 parent 1266 70b199792735 child 1275 e38c9a70375c
Merge bugfix #439 to branch 1.2
 lemon/connectivity.h file | annotate | diff | comparison | revisions test/connectivity_test.cc file | annotate | diff | comparison | revisions
```     1.1 --- a/lemon/connectivity.h	Wed Aug 07 07:09:31 2013 +0200
1.2 +++ b/lemon/connectivity.h	Fri Aug 09 14:05:29 2013 +0200
1.3 @@ -745,14 +745,37 @@
1.4    /// \brief Check whether an undirected graph is bi-node-connected.
1.5    ///
1.6    /// This function checks whether the given undirected graph is
1.7 -  /// bi-node-connected, i.e. any two edges are on same circle.
1.8 +  /// bi-node-connected, i.e. a connected graph without articulation
1.9 +  /// node.
1.10    ///
1.11    /// \return \c true if the graph bi-node-connected.
1.12 -  /// \note By definition, the empty graph is bi-node-connected.
1.13 +  ///
1.14 +  /// \note By definition,
1.15 +  /// \li a graph consisting of zero or one node is bi-node-connected,
1.16 +  /// \li a graph consisting of two isolated nodes
1.17 +  /// is \e not bi-node-connected and
1.18 +  /// \li a graph consisting of two nodes connected by an edge
1.19 +  /// is bi-node-connected.
1.20    ///
1.21    /// \see countBiNodeConnectedComponents(), biNodeConnectedComponents()
1.22    template <typename Graph>
1.23    bool biNodeConnected(const Graph& graph) {
1.24 +    bool hasNonIsolated = false, hasIsolated = false;
1.25 +    for (typename Graph::NodeIt n(graph); n != INVALID; ++n) {
1.26 +      if (typename Graph::OutArcIt(graph, n) == INVALID) {
1.27 +        if (hasIsolated || hasNonIsolated) {
1.28 +          return false;
1.29 +        } else {
1.30 +          hasIsolated = true;
1.31 +        }
1.32 +      } else {
1.33 +        if (hasIsolated) {
1.34 +          return false;
1.35 +        } else {
1.36 +          hasNonIsolated = true;
1.37 +        }
1.38 +      }
1.39 +    }
1.40      return countBiNodeConnectedComponents(graph) <= 1;
1.41    }
1.42
```
```     2.1 --- a/test/connectivity_test.cc	Wed Aug 07 07:09:31 2013 +0200
2.2 +++ b/test/connectivity_test.cc	Fri Aug 09 14:05:29 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);
```