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