Changeset 1268:19087d4f215d in lemon
 Timestamp:
 08/09/13 14:05:29 (6 years ago)
 Branch:
 1.2
 Parents:
 1263:b9887ae63df0 (diff), 1266:70b199792735 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.  Phase:
 public
 Files:

 4 edited
Legend:
 Unmodified
 Added
 Removed

lemon/connectivity.h
r956 r1268 746 746 /// 747 747 /// This function checks whether the given undirected graph is 748 /// binodeconnected, i.e. any two edges are on same circle. 748 /// binodeconnected, i.e. a connected graph without articulation 749 /// node. 749 750 /// 750 751 /// \return \c true if the graph binodeconnected. 751 /// \note By definition, the empty graph is binodeconnected. 752 /// 753 /// \note By definition, 754 /// \li a graph consisting of zero or one node is binodeconnected, 755 /// \li a graph consisting of two isolated nodes 756 /// is \e not binodeconnected and 757 /// \li a graph consisting of two nodes connected by an edge 758 /// is binodeconnected. 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 } 
lemon/connectivity.h
r1266 r1268 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 200320 095 * Copyright (C) 20032010 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). … … 259 259 /// \return \c true if the digraph is strongly connected. 260 260 /// \note By definition, the empty digraph is strongly connected. 261 /// 261 /// 262 262 /// \see countStronglyConnectedComponents(), stronglyConnectedComponents() 263 263 /// \see connected() … … 311 311 /// \ingroup graph_properties 312 312 /// 313 /// \brief Count the number of strongly connected components of a 313 /// \brief Count the number of strongly connected components of a 314 314 /// directed graph 315 315 /// … … 782 782 /// \ingroup graph_properties 783 783 /// 784 /// \brief Count the number of binodeconnected components of an 784 /// \brief Count the number of binodeconnected components of an 785 785 /// undirected graph. 786 786 /// … … 836 836 /// \retval compMap A writable edge map. The values will be set from 0 837 837 /// to the number of the binodeconnected components minus one. Each 838 /// value of the map will be set exactly once, and the values of a 838 /// value of the map will be set exactly once, and the values of a 839 839 /// certain component will be set continuously. 840 840 /// \return The number of binodeconnected components. … … 882 882 /// 883 883 /// \param graph The undirected graph. 884 /// \retval cutMap A writable node map. The values will be set to 884 /// \retval cutMap A writable node map. The values will be set to 885 885 /// \c true for the nodes that separate two or more components 886 886 /// (exactly once for each cut node), and will not be changed for … … 1109 1109 /// \brief Check whether an undirected graph is biedgeconnected. 1110 1110 /// 1111 /// This function checks whether the given undirected graph is 1111 /// This function checks whether the given undirected graph is 1112 1112 /// biedgeconnected, i.e. any two nodes are connected with at least 1113 1113 /// two edgedisjoint paths. … … 1216 1216 /// 1217 1217 /// This function finds the biedgeconnected cut edges in the given 1218 /// undirected graph. 1218 /// undirected graph. 1219 1219 /// 1220 1220 /// The biedgeconnected components are the classes of an equivalence … … 1373 1373 /// \param digraph The digraph. 1374 1374 /// \retval order A readable and writable node map. The values will be 1375 /// set from 0 to the number of the nodes in the digraph minus one. 1375 /// set from 0 to the number of the nodes in the digraph minus one. 1376 1376 /// Each value of the map will be set exactly once, and the values will 1377 1377 /// be set descending order. 
test/connectivity_test.cc
r1259 r1268 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 binodeconnected"); 111 112 ListGraph::Node n3 = g.addNode(); 113 ::lemon::ignore_unused_variable_warning(n3); 114 check(!biNodeConnected(g), "Graph is not binodeconnected"); 115 } 116 100 117 101 118 { 
test/connectivity_test.cc
r1265 r1268 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 200320 095 * Copyright (C) 20032010 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). … … 30 30 typedef ListDigraph Digraph; 31 31 typedef Undirector<Digraph> Graph; 32 32 33 33 { 34 34 Digraph d; 35 35 Digraph::NodeMap<int> order(d); 36 36 Graph g(d); 37 37 38 38 check(stronglyConnected(d), "The empty digraph is strongly connected"); 39 39 check(countStronglyConnectedComponents(d) == 0, … … 49 49 check(countBiEdgeConnectedComponents(g) == 0, 50 50 "The empty graph has 0 biedgeconnected component"); 51 51 52 52 check(dag(d), "The empty digraph is DAG."); 53 53 check(checkedTopologicalSort(d, order), "The empty digraph is DAG."); … … 84 84 check(countBiEdgeConnectedComponents(g) == 1, 85 85 "This graph has 1 biedgeconnected component"); 86 86 87 87 check(dag(d), "This digraph is DAG."); 88 88 check(checkedTopologicalSort(d, order), "This digraph is DAG."); … … 120 120 Digraph::NodeMap<int> order(d); 121 121 Graph g(d); 122 122 123 123 Digraph::Node n1 = d.addNode(); 124 124 Digraph::Node n2 = d.addNode(); … … 127 127 Digraph::Node n5 = d.addNode(); 128 128 Digraph::Node n6 = d.addNode(); 129 129 130 130 d.addArc(n1, n3); 131 131 d.addArc(n3, n2); … … 155 155 check(!parallelFree(g), "This graph is not parallelfree."); 156 156 check(!simpleGraph(g), "This graph is not simple."); 157 157 158 158 d.addArc(n3, n3); 159 159 160 160 check(!loopFree(d), "This digraph is not loopfree."); 161 161 check(!loopFree(g), "This graph is not loopfree."); 162 162 check(!simpleGraph(d), "This digraph is not simple."); 163 163 164 164 d.addArc(n3, n2); 165 165 166 166 check(!parallelFree(d), "This digraph is not parallelfree."); 167 167 } 168 168 169 169 { 170 170 Digraph d; 171 171 Digraph::ArcMap<bool> cutarcs(d, false); 172 172 Graph g(d); 173 173 174 174 Digraph::Node n1 = d.addNode(); 175 175 Digraph::Node n2 = d.addNode(); … … 191 191 d.addArc(n6, n7); 192 192 d.addArc(n7, n6); 193 193 194 194 check(!stronglyConnected(d), "This digraph is not strongly connected"); 195 195 check(countStronglyConnectedComponents(d) == 3, … … 254 254 Digraph d; 255 255 Digraph::NodeMap<int> order(d); 256 256 257 257 Digraph::Node belt = d.addNode(); 258 258 Digraph::Node trousers = d.addNode(); … … 275 275 d.addArc(shirt, necktie); 276 276 d.addArc(necktie, coat); 277 277 278 278 check(dag(d), "This digraph is DAG."); 279 279 topologicalSort(d, order); … … 287 287 ListGraph g; 288 288 ListGraph::NodeMap<bool> map(g); 289 289 290 290 ListGraph::Node n1 = g.addNode(); 291 291 ListGraph::Node n2 = g.addNode(); … … 303 303 g.addEdge(n4, n7); 304 304 g.addEdge(n5, n7); 305 305 306 306 check(bipartite(g), "This graph is bipartite"); 307 307 check(bipartitePartitions(g, map), "This graph is bipartite"); 308 308 309 309 check(map[n1] == map[n2] && map[n1] == map[n6] && map[n1] == map[n7], 310 310 "Wrong bipartitePartitions()");
Note: See TracChangeset
for help on using the changeset viewer.