Changes in / [985:b9887ae63df0:988:19087d4f215d] in lemon-1.2
- Files:
-
- 2 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/connectivity.h
r877 r988 746 746 /// 747 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 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 760 /// \see countBiNodeConnectedComponents(), biNodeConnectedComponents() 754 761 template <typename Graph> 755 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 779 return countBiNodeConnectedComponents(graph) <= 1; 757 780 } -
test/connectivity_test.cc
r983 r988 98 98 check(simpleGraph(g), "This graph is simple."); 99 99 } 100 101 { 102 ListGraph g; 103 ListGraph::NodeMap<bool> map(g); 104 105 ListGraph::Node n1 = g.addNode(); 106 ListGraph::Node n2 = g.addNode(); 107 108 ListGraph::Edge e1 = g.addEdge(n1, n2); 109 ::lemon::ignore_unused_variable_warning(e1); 110 check(biNodeConnected(g), "Graph is bi-node-connected"); 111 112 ListGraph::Node n3 = g.addNode(); 113 ::lemon::ignore_unused_variable_warning(n3); 114 check(!biNodeConnected(g), "Graph is not bi-node-connected"); 115 } 116 100 117 101 118 {
Note: See TracChangeset
for help on using the changeset viewer.