Changes in / [653:682941948726:650:a8dfe89b7719] in lemon-main
- Files:
-
- 1 deleted
- 7 edited
-
doc/groups.dox (modified) (2 diffs)
-
doc/mainpage.dox (modified) (1 diff)
-
lemon/connectivity.h (modified) (30 diffs)
-
lemon/euler.h (modified) (1 diff)
-
lemon/matching.h (modified) (2 diffs)
-
test/CMakeLists.txt (modified) (1 diff)
-
test/Makefile.am (modified) (2 diffs)
-
test/connectivity_test.cc (deleted)
Legend:
- Unmodified
- Added
- Removed
-
doc/groups.dox
r651 r640 336 336 In most cases the \ref Preflow "Preflow" algorithm provides the 337 337 fastest method for computing a maximum flow. All implementations 338 also provide functions to query the minimum cut, which is the dual 339 problem of maximum flow. 340 341 \ref Circulation is a preflow push-relabel algorithm implemented directly 342 for finding feasible circulations, which is a somewhat different problem, 343 but it is strongly related to maximum flow. 344 For more information, see \ref Circulation. 338 provides functions to also query the minimum cut, which is the dual 339 problem of the maximum flow. 345 340 */ 346 341 … … 547 542 @defgroup spantree Minimum Spanning Tree Algorithms 548 543 @ingroup algs 549 \brief Algorithms for finding minimum cost spanning trees and arborescences.550 551 This group contains the algorithms for finding minimum cost spanning552 tree s and arborescences.544 \brief Algorithms for finding a minimum cost spanning tree in a graph. 545 546 This group contains the algorithms for finding a minimum cost spanning 547 tree in a graph. 553 548 */ 554 549 -
doc/mainpage.dox
r651 r559 42 42 \subsection howtoread How to read the documentation 43 43 44 If you would like to get to know the library, see 44 If you want to get a quick start and see the most important features then 45 take a look at our \ref quicktour 46 "Quick Tour to LEMON" which will guide you along. 47 48 If you already feel like using our library, see the 45 49 <a class="el" href="http://lemon.cs.elte.hu/pub/tutorial/">LEMON Tutorial</a>. 46 50 47 If you know what you are looking for ,then try to find it under the51 If you know what you are looking for then try to find it under the 48 52 <a class="el" href="modules.html">Modules</a> section. 49 53 -
lemon/connectivity.h
r648 r586 43 43 /// \ingroup graph_properties 44 44 /// 45 /// \brief Check whether an undirected graph is connected. 46 /// 47 /// This function checks whether the given undirected graph is connected, 48 /// i.e. there is a path between any two nodes in the graph. 49 /// 50 /// \return \c true if the graph is connected. 45 /// \brief Check whether the given undirected graph is connected. 46 /// 47 /// Check whether the given undirected graph is connected. 48 /// \param graph The undirected graph. 49 /// \return \c true when there is path between any two nodes in the graph. 51 50 /// \note By definition, the empty graph is connected. 52 ///53 /// \see countConnectedComponents(), connectedComponents()54 /// \see stronglyConnected()55 51 template <typename Graph> 56 52 bool connected(const Graph& graph) { … … 72 68 /// \brief Count the number of connected components of an undirected graph 73 69 /// 74 /// This function counts the number of connected components of the given 75 /// undirected graph. 76 /// 77 /// The connected components are the classes of an equivalence relation 78 /// on the nodes of an undirected graph. Two nodes are in the same class 79 /// if they are connected with a path. 80 /// 81 /// \return The number of connected components. 70 /// Count the number of connected components of an undirected graph 71 /// 72 /// \param graph The graph. It must be undirected. 73 /// \return The number of components 82 74 /// \note By definition, the empty graph consists 83 75 /// of zero connected components. 84 ///85 /// \see connected(), connectedComponents()86 76 template <typename Graph> 87 77 int countConnectedComponents(const Graph &graph) { … … 120 110 /// \brief Find the connected components of an undirected graph 121 111 /// 122 /// This function finds the connected components of the given undirected 123 /// graph. 124 /// 125 /// The connected components are the classes of an equivalence relation 126 /// on the nodes of an undirected graph. Two nodes are in the same class 127 /// if they are connected with a path. 112 /// Find the connected components of an undirected graph. 128 113 /// 129 114 /// \image html connected_components.png 130 115 /// \image latex connected_components.eps "Connected components" width=\textwidth 131 116 /// 132 /// \param graph The undirected graph.117 /// \param graph The graph. It must be undirected. 133 118 /// \retval compMap A writable node map. The values will be set from 0 to 134 /// the number of the connected components minus one. Each value of the map135 /// will be set exactly once, andthe values of a certain component will be119 /// the number of the connected components minus one. Each values of the map 120 /// will be set exactly once, the values of a certain component will be 136 121 /// set continuously. 137 /// \return The number of connected components. 138 /// \note By definition, the empty graph consists 139 /// of zero connected components. 140 /// 141 /// \see connected(), countConnectedComponents() 122 /// \return The number of components 142 123 template <class Graph, class NodeMap> 143 124 int connectedComponents(const Graph &graph, NodeMap &compMap) { … … 251 232 /// \ingroup graph_properties 252 233 /// 253 /// \brief Check whether adirected graph is strongly connected.254 /// 255 /// This function checks whether the given directed graph is strongly256 /// connected, i.e. any two nodes of the digraph are234 /// \brief Check whether the given directed graph is strongly connected. 235 /// 236 /// Check whether the given directed graph is strongly connected. The 237 /// graph is strongly connected when any two nodes of the graph are 257 238 /// connected with directed paths in both direction. 258 /// 259 /// \return \c true if the digraph is strongly connected. 260 /// \note By definition, the empty digraph is strongly connected. 261 /// 262 /// \see countStronglyConnectedComponents(), stronglyConnectedComponents() 263 /// \see connected() 239 /// \return \c false when the graph is not strongly connected. 240 /// \see connected 241 /// 242 /// \note By definition, the empty graph is strongly connected. 264 243 template <typename Digraph> 265 244 bool stronglyConnected(const Digraph& digraph) { … … 292 271 RDigraph rdigraph(digraph); 293 272 294 typedef DfsVisitor< RDigraph> RVisitor;273 typedef DfsVisitor<Digraph> RVisitor; 295 274 RVisitor rvisitor; 296 275 … … 311 290 /// \ingroup graph_properties 312 291 /// 313 /// \brief Count the number of strongly connected components of a 314 /// directed graph 315 /// 316 /// This function counts the number of strongly connected components of 317 /// the given directed graph. 318 /// 292 /// \brief Count the strongly connected components of a directed graph 293 /// 294 /// Count the strongly connected components of a directed graph. 319 295 /// The strongly connected components are the classes of an 320 /// equivalence relation on the nodes of a digraph. Two nodes are in296 /// equivalence relation on the nodes of the graph. Two nodes are in 321 297 /// the same class if they are connected with directed paths in both 322 298 /// direction. 323 299 /// 324 /// \return The number of strongly connected components. 325 /// \note By definition, the empty digraph has zero 300 /// \param digraph The graph. 301 /// \return The number of components 302 /// \note By definition, the empty graph has zero 326 303 /// strongly connected components. 327 ///328 /// \see stronglyConnected(), stronglyConnectedComponents()329 304 template <typename Digraph> 330 305 int countStronglyConnectedComponents(const Digraph& digraph) { … … 381 356 /// \brief Find the strongly connected components of a directed graph 382 357 /// 383 /// This function finds the strongly connected components of the given 384 /// directed graph. In addition, the numbering of the components will 385 /// satisfy that there is no arc going from a higher numbered component 386 /// to a lower one (i.e. it provides a topological order of the components). 387 /// 388 /// The strongly connected components are the classes of an 389 /// equivalence relation on the nodes of a digraph. Two nodes are in 390 /// the same class if they are connected with directed paths in both 391 /// direction. 358 /// Find the strongly connected components of a directed graph. The 359 /// strongly connected components are the classes of an equivalence 360 /// relation on the nodes of the graph. Two nodes are in 361 /// relationship when there are directed paths between them in both 362 /// direction. In addition, the numbering of components will satisfy 363 /// that there is no arc going from a higher numbered component to 364 /// a lower. 392 365 /// 393 366 /// \image html strongly_connected_components.png … … 397 370 /// \retval compMap A writable node map. The values will be set from 0 to 398 371 /// the number of the strongly connected components minus one. Each value 399 /// of the map will be set exactly once, and the values of a certain 400 /// component will be set continuously. 401 /// \return The number of strongly connected components. 402 /// \note By definition, the empty digraph has zero 403 /// strongly connected components. 404 /// 405 /// \see stronglyConnected(), countStronglyConnectedComponents() 372 /// of the map will be set exactly once, the values of a certain component 373 /// will be set continuously. 374 /// \return The number of components 406 375 template <typename Digraph, typename NodeMap> 407 376 int stronglyConnectedComponents(const Digraph& digraph, NodeMap& compMap) { … … 456 425 /// \brief Find the cut arcs of the strongly connected components. 457 426 /// 458 /// This function finds the cut arcs of the strongly connected components 459 /// of the given digraph. 460 /// 461 /// The strongly connected components are the classes of an 462 /// equivalence relation on the nodes of a digraph. Two nodes are in 463 /// the same class if they are connected with directed paths in both 464 /// direction. 427 /// Find the cut arcs of the strongly connected components. 428 /// The strongly connected components are the classes of an equivalence 429 /// relation on the nodes of the graph. Two nodes are in relationship 430 /// when there are directed paths between them in both direction. 465 431 /// The strongly connected components are separated by the cut arcs. 466 432 /// 467 /// \param digraph The digraph. 468 /// \retval cutMap A writable arc map. The values will be set to \c true 469 /// for the cut arcs (exactly once for each cut arc), and will not be 470 /// changed for other arcs. 471 /// \return The number of cut arcs. 472 /// 473 /// \see stronglyConnected(), stronglyConnectedComponents() 433 /// \param graph The graph. 434 /// \retval cutMap A writable node map. The values will be set true when the 435 /// arc is a cut arc. 436 /// 437 /// \return The number of cut arcs 474 438 template <typename Digraph, typename ArcMap> 475 int stronglyConnectedCutArcs(const Digraph& digraph, ArcMap& cutMap) {439 int stronglyConnectedCutArcs(const Digraph& graph, ArcMap& cutMap) { 476 440 checkConcept<concepts::Digraph, Digraph>(); 477 441 typedef typename Digraph::Node Node; … … 485 449 typedef typename Container::iterator Iterator; 486 450 487 Container nodes(countNodes( digraph));451 Container nodes(countNodes(graph)); 488 452 typedef LeaveOrderVisitor<Digraph, Iterator> Visitor; 489 453 Visitor visitor(nodes.begin()); 490 454 491 DfsVisit<Digraph, Visitor> dfs( digraph, visitor);455 DfsVisit<Digraph, Visitor> dfs(graph, visitor); 492 456 dfs.init(); 493 for (NodeIt it( digraph); it != INVALID; ++it) {457 for (NodeIt it(graph); it != INVALID; ++it) { 494 458 if (!dfs.reached(it)) { 495 459 dfs.addSource(it); … … 501 465 typedef ReverseDigraph<const Digraph> RDigraph; 502 466 503 RDigraph r digraph(digraph);467 RDigraph rgraph(graph); 504 468 505 469 int cutNum = 0; 506 470 507 471 typedef StronglyConnectedCutArcsVisitor<RDigraph, ArcMap> RVisitor; 508 RVisitor rvisitor(r digraph, cutMap, cutNum);509 510 DfsVisit<RDigraph, RVisitor> rdfs(r digraph, rvisitor);472 RVisitor rvisitor(rgraph, cutMap, cutNum); 473 474 DfsVisit<RDigraph, RVisitor> rdfs(rgraph, rvisitor); 511 475 512 476 rdfs.init(); … … 743 707 /// \ingroup graph_properties 744 708 /// 745 /// \brief Check whether an undirected graph is bi-node-connected. 746 /// 747 /// This function checks whether the given undirected graph is 748 /// bi-node-connected, i.e. any two edges are on same circle. 749 /// 750 /// \return \c true if the graph bi-node-connected. 751 /// \note By definition, the empty graph is bi-node-connected. 752 /// 753 /// \see countBiNodeConnectedComponents(), biNodeConnectedComponents() 709 /// \brief Checks the graph is bi-node-connected. 710 /// 711 /// This function checks that the undirected graph is bi-node-connected 712 /// graph. The graph is bi-node-connected if any two undirected edge is 713 /// on same circle. 714 /// 715 /// \param graph The graph. 716 /// \return \c true when the graph bi-node-connected. 754 717 template <typename Graph> 755 718 bool biNodeConnected(const Graph& graph) { … … 759 722 /// \ingroup graph_properties 760 723 /// 761 /// \brief Count the number of bi-node-connected components of an 762 /// undirected graph. 763 /// 764 /// This function counts the number of bi-node-connected components of 765 /// the given undirected graph. 766 /// 767 /// The bi-node-connected components are the classes of an equivalence 768 /// relation on the edges of a undirected graph. Two edges are in the 769 /// same class if they are on same circle. 770 /// 771 /// \return The number of bi-node-connected components. 772 /// 773 /// \see biNodeConnected(), biNodeConnectedComponents() 724 /// \brief Count the biconnected components. 725 /// 726 /// This function finds the bi-node-connected components in an undirected 727 /// graph. The biconnected components are the classes of an equivalence 728 /// relation on the undirected edges. Two undirected edge is in relationship 729 /// when they are on same circle. 730 /// 731 /// \param graph The graph. 732 /// \return The number of components. 774 733 template <typename Graph> 775 734 int countBiNodeConnectedComponents(const Graph& graph) { … … 798 757 /// \ingroup graph_properties 799 758 /// 800 /// \brief Find the bi-node-connected components of an undirected graph. 801 /// 802 /// This function finds the bi-node-connected components of the given 803 /// undirected graph. 804 /// 805 /// The bi-node-connected components are the classes of an equivalence 806 /// relation on the edges of a undirected graph. Two edges are in the 807 /// same class if they are on same circle. 759 /// \brief Find the bi-node-connected components. 760 /// 761 /// This function finds the bi-node-connected components in an undirected 762 /// graph. The bi-node-connected components are the classes of an equivalence 763 /// relation on the undirected edges. Two undirected edge are in relationship 764 /// when they are on same circle. 808 765 /// 809 766 /// \image html node_biconnected_components.png 810 767 /// \image latex node_biconnected_components.eps "bi-node-connected components" width=\textwidth 811 768 /// 812 /// \param graph The undirected graph. 813 /// \retval compMap A writable edge map. The values will be set from 0 814 /// to the number of the bi-node-connected components minus one. Each 815 /// value of the map will be set exactly once, and the values of a 816 /// certain component will be set continuously. 817 /// \return The number of bi-node-connected components. 818 /// 819 /// \see biNodeConnected(), countBiNodeConnectedComponents() 769 /// \param graph The graph. 770 /// \retval compMap A writable uedge map. The values will be set from 0 771 /// to the number of the biconnected components minus one. Each values 772 /// of the map will be set exactly once, the values of a certain component 773 /// will be set continuously. 774 /// \return The number of components. 820 775 template <typename Graph, typename EdgeMap> 821 776 int biNodeConnectedComponents(const Graph& graph, … … 847 802 /// \ingroup graph_properties 848 803 /// 849 /// \brief Find the bi-node-connected cut nodes in an undirected graph. 850 /// 851 /// This function finds the bi-node-connected cut nodes in the given 852 /// undirected graph. 853 /// 854 /// The bi-node-connected components are the classes of an equivalence 855 /// relation on the edges of a undirected graph. Two edges are in the 856 /// same class if they are on same circle. 857 /// The bi-node-connected components are separted by the cut nodes of 858 /// the components. 859 /// 860 /// \param graph The undirected graph. 861 /// \retval cutMap A writable node map. The values will be set to 862 /// \c true for the nodes that separate two or more components 863 /// (exactly once for each cut node), and will not be changed for 864 /// other nodes. 804 /// \brief Find the bi-node-connected cut nodes. 805 /// 806 /// This function finds the bi-node-connected cut nodes in an undirected 807 /// graph. The bi-node-connected components are the classes of an equivalence 808 /// relation on the undirected edges. Two undirected edges are in 809 /// relationship when they are on same circle. The biconnected components 810 /// are separted by nodes which are the cut nodes of the components. 811 /// 812 /// \param graph The graph. 813 /// \retval cutMap A writable edge map. The values will be set true when 814 /// the node separate two or more components. 865 815 /// \return The number of the cut nodes. 866 ///867 /// \see biNodeConnected(), biNodeConnectedComponents()868 816 template <typename Graph, typename NodeMap> 869 817 int biNodeConnectedCutNodes(const Graph& graph, NodeMap& cutMap) { … … 1084 1032 /// \ingroup graph_properties 1085 1033 /// 1086 /// \brief Check whether an undirected graph is bi-edge-connected. 1087 /// 1088 /// This function checks whether the given undirected graph is 1089 /// bi-edge-connected, i.e. any two nodes are connected with at least 1090 /// two edge-disjoint paths. 1091 /// 1092 /// \return \c true if the graph is bi-edge-connected. 1093 /// \note By definition, the empty graph is bi-edge-connected. 1094 /// 1095 /// \see countBiEdgeConnectedComponents(), biEdgeConnectedComponents() 1034 /// \brief Checks that the graph is bi-edge-connected. 1035 /// 1036 /// This function checks that the graph is bi-edge-connected. The undirected 1037 /// graph is bi-edge-connected when any two nodes are connected with two 1038 /// edge-disjoint paths. 1039 /// 1040 /// \param graph The undirected graph. 1041 /// \return The number of components. 1096 1042 template <typename Graph> 1097 1043 bool biEdgeConnected(const Graph& graph) { … … 1101 1047 /// \ingroup graph_properties 1102 1048 /// 1103 /// \brief Count the number of bi-edge-connected components of an 1104 /// undirected graph. 1105 /// 1106 /// This function counts the number of bi-edge-connected components of 1107 /// the given undirected graph. 1108 /// 1109 /// The bi-edge-connected components are the classes of an equivalence 1110 /// relation on the nodes of an undirected graph. Two nodes are in the 1111 /// same class if they are connected with at least two edge-disjoint 1112 /// paths. 1113 /// 1114 /// \return The number of bi-edge-connected components. 1115 /// 1116 /// \see biEdgeConnected(), biEdgeConnectedComponents() 1049 /// \brief Count the bi-edge-connected components. 1050 /// 1051 /// This function count the bi-edge-connected components in an undirected 1052 /// graph. The bi-edge-connected components are the classes of an equivalence 1053 /// relation on the nodes. Two nodes are in relationship when they are 1054 /// connected with at least two edge-disjoint paths. 1055 /// 1056 /// \param graph The undirected graph. 1057 /// \return The number of components. 1117 1058 template <typename Graph> 1118 1059 int countBiEdgeConnectedComponents(const Graph& graph) { … … 1141 1082 /// \ingroup graph_properties 1142 1083 /// 1143 /// \brief Find the bi-edge-connected components of an undirected graph. 1144 /// 1145 /// This function finds the bi-edge-connected components of the given 1146 /// undirected graph. 1147 /// 1148 /// The bi-edge-connected components are the classes of an equivalence 1149 /// relation on the nodes of an undirected graph. Two nodes are in the 1150 /// same class if they are connected with at least two edge-disjoint 1151 /// paths. 1084 /// \brief Find the bi-edge-connected components. 1085 /// 1086 /// This function finds the bi-edge-connected components in an undirected 1087 /// graph. The bi-edge-connected components are the classes of an equivalence 1088 /// relation on the nodes. Two nodes are in relationship when they are 1089 /// connected at least two edge-disjoint paths. 1152 1090 /// 1153 1091 /// \image html edge_biconnected_components.png 1154 1092 /// \image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth 1155 1093 /// 1156 /// \param graph The undirectedgraph.1094 /// \param graph The graph. 1157 1095 /// \retval compMap A writable node map. The values will be set from 0 to 1158 /// the number of the bi-edge-connected components minus one. Each value 1159 /// of the map will be set exactly once, and the values of a certain 1160 /// component will be set continuously. 1161 /// \return The number of bi-edge-connected components. 1162 /// 1163 /// \see biEdgeConnected(), countBiEdgeConnectedComponents() 1096 /// the number of the biconnected components minus one. Each values 1097 /// of the map will be set exactly once, the values of a certain component 1098 /// will be set continuously. 1099 /// \return The number of components. 1164 1100 template <typename Graph, typename NodeMap> 1165 1101 int biEdgeConnectedComponents(const Graph& graph, NodeMap& compMap) { … … 1190 1126 /// \ingroup graph_properties 1191 1127 /// 1192 /// \brief Find the bi-edge-connected cut edges in an undirected graph. 1193 /// 1194 /// This function finds the bi-edge-connected cut edges in the given 1195 /// undirected graph. 1196 /// 1197 /// The bi-edge-connected components are the classes of an equivalence 1198 /// relation on the nodes of an undirected graph. Two nodes are in the 1199 /// same class if they are connected with at least two edge-disjoint 1200 /// paths. 1201 /// The bi-edge-connected components are separted by the cut edges of 1202 /// the components. 1203 /// 1204 /// \param graph The undirected graph. 1205 /// \retval cutMap A writable edge map. The values will be set to \c true 1206 /// for the cut edges (exactly once for each cut edge), and will not be 1207 /// changed for other edges. 1128 /// \brief Find the bi-edge-connected cut edges. 1129 /// 1130 /// This function finds the bi-edge-connected components in an undirected 1131 /// graph. The bi-edge-connected components are the classes of an equivalence 1132 /// relation on the nodes. Two nodes are in relationship when they are 1133 /// connected with at least two edge-disjoint paths. The bi-edge-connected 1134 /// components are separted by edges which are the cut edges of the 1135 /// components. 1136 /// 1137 /// \param graph The graph. 1138 /// \retval cutMap A writable node map. The values will be set true when the 1139 /// edge is a cut edge. 1208 1140 /// \return The number of cut edges. 1209 ///1210 /// \see biEdgeConnected(), biEdgeConnectedComponents()1211 1141 template <typename Graph, typename EdgeMap> 1212 1142 int biEdgeConnectedCutEdges(const Graph& graph, EdgeMap& cutMap) { … … 1260 1190 /// \ingroup graph_properties 1261 1191 /// 1262 /// \brief Check whether a digraph is DAG. 1263 /// 1264 /// This function checks whether the given digraph is DAG, i.e. 1265 /// \e Directed \e Acyclic \e Graph. 1266 /// \return \c true if there is no directed cycle in the digraph. 1267 /// \see acyclic() 1268 template <typename Digraph> 1269 bool dag(const Digraph& digraph) { 1192 /// \brief Sort the nodes of a DAG into topolgical order. 1193 /// 1194 /// Sort the nodes of a DAG into topolgical order. 1195 /// 1196 /// \param graph The graph. It must be directed and acyclic. 1197 /// \retval order A writable node map. The values will be set from 0 to 1198 /// the number of the nodes in the graph minus one. Each values of the map 1199 /// will be set exactly once, the values will be set descending order. 1200 /// 1201 /// \see checkedTopologicalSort 1202 /// \see dag 1203 template <typename Digraph, typename NodeMap> 1204 void topologicalSort(const Digraph& graph, NodeMap& order) { 1205 using namespace _connectivity_bits; 1270 1206 1271 1207 checkConcept<concepts::Digraph, Digraph>(); 1208 checkConcept<concepts::WriteMap<typename Digraph::Node, int>, NodeMap>(); 1272 1209 1273 1210 typedef typename Digraph::Node Node; … … 1275 1212 typedef typename Digraph::Arc Arc; 1276 1213 1277 typedef typename Digraph::template NodeMap<bool> ProcessedMap; 1278 1279 typename Dfs<Digraph>::template SetProcessedMap<ProcessedMap>:: 1280 Create dfs(digraph); 1281 1282 ProcessedMap processed(digraph); 1283 dfs.processedMap(processed); 1214 TopologicalSortVisitor<Digraph, NodeMap> 1215 visitor(order, countNodes(graph)); 1216 1217 DfsVisit<Digraph, TopologicalSortVisitor<Digraph, NodeMap> > 1218 dfs(graph, visitor); 1284 1219 1285 1220 dfs.init(); 1286 for (NodeIt it(digraph); it != INVALID; ++it) { 1287 if (!dfs.reached(it)) { 1288 dfs.addSource(it); 1289 while (!dfs.emptyQueue()) { 1290 Arc arc = dfs.nextArc(); 1291 Node target = digraph.target(arc); 1292 if (dfs.reached(target) && !processed[target]) { 1293 return false; 1294 } 1295 dfs.processNextArc(); 1296 } 1297 } 1298 } 1299 return true; 1300 } 1301 1302 /// \ingroup graph_properties 1303 /// 1304 /// \brief Sort the nodes of a DAG into topolgical order. 1305 /// 1306 /// This function sorts the nodes of the given acyclic digraph (DAG) 1307 /// into topolgical order. 1308 /// 1309 /// \param digraph The digraph, which must be DAG. 1310 /// \retval order A writable node map. The values will be set from 0 to 1311 /// the number of the nodes in the digraph minus one. Each value of the 1312 /// map will be set exactly once, and the values will be set descending 1313 /// order. 1314 /// 1315 /// \see dag(), checkedTopologicalSort() 1316 template <typename Digraph, typename NodeMap> 1317 void topologicalSort(const Digraph& digraph, NodeMap& order) { 1318 using namespace _connectivity_bits; 1319 1320 checkConcept<concepts::Digraph, Digraph>(); 1321 checkConcept<concepts::WriteMap<typename Digraph::Node, int>, NodeMap>(); 1322 1323 typedef typename Digraph::Node Node; 1324 typedef typename Digraph::NodeIt NodeIt; 1325 typedef typename Digraph::Arc Arc; 1326 1327 TopologicalSortVisitor<Digraph, NodeMap> 1328 visitor(order, countNodes(digraph)); 1329 1330 DfsVisit<Digraph, TopologicalSortVisitor<Digraph, NodeMap> > 1331 dfs(digraph, visitor); 1332 1333 dfs.init(); 1334 for (NodeIt it(digraph); it != INVALID; ++it) { 1221 for (NodeIt it(graph); it != INVALID; ++it) { 1335 1222 if (!dfs.reached(it)) { 1336 1223 dfs.addSource(it); … … 1344 1231 /// \brief Sort the nodes of a DAG into topolgical order. 1345 1232 /// 1346 /// This function sorts the nodes of the given acyclic digraph (DAG)1347 /// into topolgical order and also checks whether the given digraph1348 /// is DAG.1349 /// 1350 /// \ param digraph The digraph.1351 /// \retval order A readable and writable node map. The values will be1352 /// set from 0 to the number of the nodes in the digraph minus one.1353 /// Each value of the map will be set exactly once, and the values will1354 /// be set descending order.1355 /// \return \c false if the digraph is not DAG.1356 /// 1357 /// \see dag (), topologicalSort()1233 /// Sort the nodes of a DAG into topolgical order. It also checks 1234 /// that the given graph is DAG. 1235 /// 1236 /// \param digraph The graph. It must be directed and acyclic. 1237 /// \retval order A readable - writable node map. The values will be set 1238 /// from 0 to the number of the nodes in the graph minus one. Each values 1239 /// of the map will be set exactly once, the values will be set descending 1240 /// order. 1241 /// \return \c false when the graph is not DAG. 1242 /// 1243 /// \see topologicalSort 1244 /// \see dag 1358 1245 template <typename Digraph, typename NodeMap> 1359 1246 bool checkedTopologicalSort(const Digraph& digraph, NodeMap& order) { … … 1397 1284 /// \ingroup graph_properties 1398 1285 /// 1399 /// \brief Check whether an undirected graph is acyclic. 1400 /// 1401 /// This function checks whether the given undirected graph is acyclic. 1402 /// \return \c true if there is no cycle in the graph. 1403 /// \see dag() 1286 /// \brief Check that the given directed graph is a DAG. 1287 /// 1288 /// Check that the given directed graph is a DAG. The DAG is 1289 /// an Directed Acyclic Digraph. 1290 /// \return \c false when the graph is not DAG. 1291 /// \see acyclic 1292 template <typename Digraph> 1293 bool dag(const Digraph& digraph) { 1294 1295 checkConcept<concepts::Digraph, Digraph>(); 1296 1297 typedef typename Digraph::Node Node; 1298 typedef typename Digraph::NodeIt NodeIt; 1299 typedef typename Digraph::Arc Arc; 1300 1301 typedef typename Digraph::template NodeMap<bool> ProcessedMap; 1302 1303 typename Dfs<Digraph>::template SetProcessedMap<ProcessedMap>:: 1304 Create dfs(digraph); 1305 1306 ProcessedMap processed(digraph); 1307 dfs.processedMap(processed); 1308 1309 dfs.init(); 1310 for (NodeIt it(digraph); it != INVALID; ++it) { 1311 if (!dfs.reached(it)) { 1312 dfs.addSource(it); 1313 while (!dfs.emptyQueue()) { 1314 Arc edge = dfs.nextArc(); 1315 Node target = digraph.target(edge); 1316 if (dfs.reached(target) && !processed[target]) { 1317 return false; 1318 } 1319 dfs.processNextArc(); 1320 } 1321 } 1322 } 1323 return true; 1324 } 1325 1326 /// \ingroup graph_properties 1327 /// 1328 /// \brief Check that the given undirected graph is acyclic. 1329 /// 1330 /// Check that the given undirected graph acyclic. 1331 /// \param graph The undirected graph. 1332 /// \return \c true when there is no circle in the graph. 1333 /// \see dag 1404 1334 template <typename Graph> 1405 1335 bool acyclic(const Graph& graph) { … … 1414 1344 dfs.addSource(it); 1415 1345 while (!dfs.emptyQueue()) { 1416 Arc arc= dfs.nextArc();1417 Node source = graph.source( arc);1418 Node target = graph.target( arc);1346 Arc edge = dfs.nextArc(); 1347 Node source = graph.source(edge); 1348 Node target = graph.target(edge); 1419 1349 if (dfs.reached(target) && 1420 dfs.predArc(source) != graph.oppositeArc( arc)) {1350 dfs.predArc(source) != graph.oppositeArc(edge)) { 1421 1351 return false; 1422 1352 } … … 1430 1360 /// \ingroup graph_properties 1431 1361 /// 1432 /// \brief Check whether an undirected graph is tree.1433 /// 1434 /// This function checks whetherthe given undirected graph is tree.1435 /// \ return \c true if the graph is acyclic and connected.1436 /// \ see acyclic(), connected()1362 /// \brief Check that the given undirected graph is tree. 1363 /// 1364 /// Check that the given undirected graph is tree. 1365 /// \param graph The undirected graph. 1366 /// \return \c true when the graph is acyclic and connected. 1437 1367 template <typename Graph> 1438 1368 bool tree(const Graph& graph) { … … 1441 1371 typedef typename Graph::NodeIt NodeIt; 1442 1372 typedef typename Graph::Arc Arc; 1443 if (NodeIt(graph) == INVALID) return true;1444 1373 Dfs<Graph> dfs(graph); 1445 1374 dfs.init(); 1446 1375 dfs.addSource(NodeIt(graph)); 1447 1376 while (!dfs.emptyQueue()) { 1448 Arc arc= dfs.nextArc();1449 Node source = graph.source( arc);1450 Node target = graph.target( arc);1377 Arc edge = dfs.nextArc(); 1378 Node source = graph.source(edge); 1379 Node target = graph.target(edge); 1451 1380 if (dfs.reached(target) && 1452 dfs.predArc(source) != graph.oppositeArc( arc)) {1381 dfs.predArc(source) != graph.oppositeArc(edge)) { 1453 1382 return false; 1454 1383 } … … 1523 1452 /// \ingroup graph_properties 1524 1453 /// 1525 /// \brief Check whether an undirected graph is bipartite. 1526 /// 1527 /// The function checks whether the given undirected graph is bipartite. 1528 /// \return \c true if the graph is bipartite. 1529 /// 1530 /// \see bipartitePartitions() 1454 /// \brief Check if the given undirected graph is bipartite or not 1455 /// 1456 /// The function checks if the given undirected \c graph graph is bipartite 1457 /// or not. The \ref Bfs algorithm is used to calculate the result. 1458 /// \param graph The undirected graph. 1459 /// \return \c true if \c graph is bipartite, \c false otherwise. 1460 /// \sa bipartitePartitions 1531 1461 template<typename Graph> 1532 bool bipartite(const Graph &graph){1462 inline bool bipartite(const Graph &graph){ 1533 1463 using namespace _connectivity_bits; 1534 1464 … … 1559 1489 /// \ingroup graph_properties 1560 1490 /// 1561 /// \brief Find the bipartite partitions of an undirected graph. 1562 /// 1563 /// This function checks whether the given undirected graph is bipartite 1564 /// and gives back the bipartite partitions. 1491 /// \brief Check if the given undirected graph is bipartite or not 1492 /// 1493 /// The function checks if the given undirected graph is bipartite 1494 /// or not. The \ref Bfs algorithm is used to calculate the result. 1495 /// During the execution, the \c partMap will be set as the two 1496 /// partitions of the graph. 1565 1497 /// 1566 1498 /// \image html bipartite_partitions.png … … 1568 1500 /// 1569 1501 /// \param graph The undirected graph. 1570 /// \retval partMap A writable node map of \c bool (or convertible) value 1571 /// type. The values will be set to \c true for one component and 1572 /// \c false for the other one. 1573 /// \return \c true if the graph is bipartite, \c false otherwise. 1574 /// 1575 /// \see bipartite() 1502 /// \retval partMap A writable bool map of nodes. It will be set as the 1503 /// two partitions of the graph. 1504 /// \return \c true if \c graph is bipartite, \c false otherwise. 1576 1505 template<typename Graph, typename NodeMap> 1577 bool bipartitePartitions(const Graph &graph, NodeMap &partMap){1506 inline bool bipartitePartitions(const Graph &graph, NodeMap &partMap){ 1578 1507 using namespace _connectivity_bits; 1579 1508 1580 1509 checkConcept<concepts::Graph, Graph>(); 1581 checkConcept<concepts::WriteMap<typename Graph::Node, bool>, NodeMap>();1582 1510 1583 1511 typedef typename Graph::Node Node; … … 1604 1532 } 1605 1533 1606 /// \ingroup graph_properties 1607 /// 1608 /// \brief Check whether the given graph contains no loop arcs/edges. 1609 /// 1610 /// This function returns \c true if there are no loop arcs/edges in 1611 /// the given graph. It works for both directed and undirected graphs. 1612 template <typename Graph> 1613 bool loopFree(const Graph& graph) { 1614 for (typename Graph::ArcIt it(graph); it != INVALID; ++it) { 1615 if (graph.source(it) == graph.target(it)) return false; 1534 /// \brief Returns true when there are not loop edges in the graph. 1535 /// 1536 /// Returns true when there are not loop edges in the graph. 1537 template <typename Digraph> 1538 bool loopFree(const Digraph& digraph) { 1539 for (typename Digraph::ArcIt it(digraph); it != INVALID; ++it) { 1540 if (digraph.source(it) == digraph.target(it)) return false; 1616 1541 } 1617 1542 return true; 1618 1543 } 1619 1544 1620 /// \ingroup graph_properties 1621 /// 1622 /// \brief Check whether the given graph contains no parallel arcs/edges. 1623 /// 1624 /// This function returns \c true if there are no parallel arcs/edges in 1625 /// the given graph. It works for both directed and undirected graphs. 1626 template <typename Graph> 1627 bool parallelFree(const Graph& graph) { 1628 typename Graph::template NodeMap<int> reached(graph, 0); 1629 int cnt = 1; 1630 for (typename Graph::NodeIt n(graph); n != INVALID; ++n) { 1631 for (typename Graph::OutArcIt a(graph, n); a != INVALID; ++a) { 1632 if (reached[graph.target(a)] == cnt) return false; 1633 reached[graph.target(a)] = cnt; 1634 } 1635 ++cnt; 1545 /// \brief Returns true when there are not parallel edges in the graph. 1546 /// 1547 /// Returns true when there are not parallel edges in the graph. 1548 template <typename Digraph> 1549 bool parallelFree(const Digraph& digraph) { 1550 typename Digraph::template NodeMap<bool> reached(digraph, false); 1551 for (typename Digraph::NodeIt n(digraph); n != INVALID; ++n) { 1552 for (typename Digraph::OutArcIt a(digraph, n); a != INVALID; ++a) { 1553 if (reached[digraph.target(a)]) return false; 1554 reached.set(digraph.target(a), true); 1555 } 1556 for (typename Digraph::OutArcIt a(digraph, n); a != INVALID; ++a) { 1557 reached.set(digraph.target(a), false); 1558 } 1636 1559 } 1637 1560 return true; 1638 1561 } 1639 1562 1640 /// \ingroup graph_properties 1641 /// 1642 /// \brief Check whether the given graph is simple. 1643 /// 1644 /// This function returns \c true if the given graph is simple, i.e. 1645 /// it contains no loop arcs/edges and no parallel arcs/edges. 1646 /// The function works for both directed and undirected graphs. 1647 /// \see loopFree(), parallelFree() 1648 template <typename Graph> 1649 bool simpleGraph(const Graph& graph) { 1650 typename Graph::template NodeMap<int> reached(graph, 0); 1651 int cnt = 1; 1652 for (typename Graph::NodeIt n(graph); n != INVALID; ++n) { 1653 reached[n] = cnt; 1654 for (typename Graph::OutArcIt a(graph, n); a != INVALID; ++a) { 1655 if (reached[graph.target(a)] == cnt) return false; 1656 reached[graph.target(a)] = cnt; 1657 } 1658 ++cnt; 1563 /// \brief Returns true when there are not loop edges and parallel 1564 /// edges in the graph. 1565 /// 1566 /// Returns true when there are not loop edges and parallel edges in 1567 /// the graph. 1568 template <typename Digraph> 1569 bool simpleDigraph(const Digraph& digraph) { 1570 typename Digraph::template NodeMap<bool> reached(digraph, false); 1571 for (typename Digraph::NodeIt n(digraph); n != INVALID; ++n) { 1572 reached.set(n, true); 1573 for (typename Digraph::OutArcIt a(digraph, n); a != INVALID; ++a) { 1574 if (reached[digraph.target(a)]) return false; 1575 reached.set(digraph.target(a), true); 1576 } 1577 for (typename Digraph::OutArcIt a(digraph, n); a != INVALID; ++a) { 1578 reached.set(digraph.target(a), false); 1579 } 1580 reached.set(n, false); 1659 1581 } 1660 1582 return true; -
lemon/euler.h
r648 r592 245 245 246 246 247 ///Check if the given graph is Eulerian247 ///Check if the given graph is \e Eulerian 248 248 249 249 /// \ingroup graph_properties 250 ///This function checks if the given graph is Eulerian.250 ///This function checks if the given graph is \e Eulerian. 251 251 ///It works for both directed and undirected graphs. 252 252 /// -
lemon/matching.h
r651 r594 500 500 /// This function runs the original Edmonds' algorithm. 501 501 /// 502 /// \pre \ref init(), \ref greedyInit() or \ref matchingInit() must be502 /// \pre \ref Init(), \ref greedyInit() or \ref matchingInit() must be 503 503 /// called before using this function. 504 504 void startSparse() { … … 519 519 /// shrinks, therefore resulting in a faster algorithm for dense graphs. 520 520 /// 521 /// \pre \ref init(), \ref greedyInit() or \ref matchingInit() must be521 /// \pre \ref Init(), \ref greedyInit() or \ref matchingInit() must be 522 522 /// called before using this function. 523 523 void startDense() { -
test/CMakeLists.txt
r649 r627 10 10 bfs_test 11 11 circulation_test 12 connectivity_test13 12 counter_test 14 13 dfs_test -
test/Makefile.am
r649 r611 10 10 test/bfs_test \ 11 11 test/circulation_test \ 12 test/connectivity_test \13 12 test/counter_test \ 14 13 test/dfs_test \ … … 56 55 test_circulation_test_SOURCES = test/circulation_test.cc 57 56 test_counter_test_SOURCES = test/counter_test.cc 58 test_connectivity_test_SOURCES = test/connectivity_test.cc59 57 test_dfs_test_SOURCES = test/dfs_test.cc 60 58 test_digraph_test_SOURCES = test/digraph_test.cc
Note: See TracChangeset
for help on using the changeset viewer.
