1.1 --- a/lemon/connectivity.h Thu Mar 28 14:52:43 2013 +0100
1.2 +++ b/lemon/connectivity.h Fri Aug 09 14:07:27 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