743 /// \ingroup graph_properties |
743 /// \ingroup graph_properties |
744 /// |
744 /// |
745 /// \brief Check whether an undirected graph is bi-node-connected. |
745 /// \brief Check whether an undirected graph is bi-node-connected. |
746 /// |
746 /// |
747 /// This function checks whether the given undirected graph is |
747 /// This function checks whether the given undirected graph is |
748 /// bi-node-connected, i.e. any two edges are on same circle. |
748 /// bi-node-connected, i.e. a connected graph without articulation |
|
749 /// node. |
749 /// |
750 /// |
750 /// \return \c true if the graph bi-node-connected. |
751 /// \return \c true if the graph bi-node-connected. |
751 /// \note By definition, the empty graph is bi-node-connected. |
752 /// |
|
753 /// \note By definition, |
|
754 /// \li a graph consisting of zero or one node is bi-node-connected, |
|
755 /// \li a graph consisting of two isolated nodes |
|
756 /// is \e not bi-node-connected and |
|
757 /// \li a graph consisting of two nodes connected by an edge |
|
758 /// is bi-node-connected. |
752 /// |
759 /// |
753 /// \see countBiNodeConnectedComponents(), biNodeConnectedComponents() |
760 /// \see countBiNodeConnectedComponents(), biNodeConnectedComponents() |
754 template <typename Graph> |
761 template <typename Graph> |
755 bool biNodeConnected(const Graph& graph) { |
762 bool biNodeConnected(const Graph& graph) { |
|
763 bool hasNonIsolated = false, hasIsolated = false; |
|
764 for (typename Graph::NodeIt n(graph); n != INVALID; ++n) { |
|
765 if (typename Graph::OutArcIt(graph, n) == INVALID) { |
|
766 if (hasIsolated || hasNonIsolated) { |
|
767 return false; |
|
768 } else { |
|
769 hasIsolated = true; |
|
770 } |
|
771 } else { |
|
772 if (hasIsolated) { |
|
773 return false; |
|
774 } else { |
|
775 hasNonIsolated = true; |
|
776 } |
|
777 } |
|
778 } |
756 return countBiNodeConnectedComponents(graph) <= 1; |
779 return countBiNodeConnectedComponents(graph) <= 1; |
757 } |
780 } |
758 |
781 |
759 /// \ingroup graph_properties |
782 /// \ingroup graph_properties |
760 /// |
783 /// |