742 |
742 |
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 /// \note By definition, the empty graph is bi-node-connected. |
752 /// |
753 /// |
753 /// \see countBiNodeConnectedComponents(), biNodeConnectedComponents() |
754 /// \see countBiNodeConnectedComponents(), biNodeConnectedComponents() |
754 template <typename Graph> |
755 template <typename Graph> |
755 bool biNodeConnected(const Graph& graph) { |
756 bool biNodeConnected(const Graph& graph) { |
|
757 bool hasNonIsolated = false, hasIsolated = false; |
|
758 for (typename Graph::NodeIt n(graph); n != INVALID; ++n) { |
|
759 if (typename Graph::OutArcIt(graph, n) == INVALID) { |
|
760 if (hasIsolated || hasNonIsolated) { |
|
761 return false; |
|
762 } else { |
|
763 hasIsolated = true; |
|
764 } |
|
765 } else { |
|
766 if (hasIsolated) { |
|
767 return false; |
|
768 } else { |
|
769 hasNonIsolated = true; |
|
770 } |
|
771 } |
|
772 } |
756 return countBiNodeConnectedComponents(graph) <= 1; |
773 return countBiNodeConnectedComponents(graph) <= 1; |
757 } |
774 } |
758 |
775 |
759 /// \ingroup graph_properties |
776 /// \ingroup graph_properties |
760 /// |
777 /// |