Changes in / [651:3adf5e2d1e62:652:e2f99a473998] in lemon-1.2
- Files:
-
- 1 added
- 4 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/connectivity.h
r586 r648 43 43 /// \ingroup graph_properties 44 44 /// 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. 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. 50 51 /// \note By definition, the empty graph is connected. 52 /// 53 /// \see countConnectedComponents(), connectedComponents() 54 /// \see stronglyConnected() 51 55 template <typename Graph> 52 56 bool connected(const Graph& graph) { … … 68 72 /// \brief Count the number of connected components of an undirected graph 69 73 /// 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 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. 74 82 /// \note By definition, the empty graph consists 75 83 /// of zero connected components. 84 /// 85 /// \see connected(), connectedComponents() 76 86 template <typename Graph> 77 87 int countConnectedComponents(const Graph &graph) { … … 110 120 /// \brief Find the connected components of an undirected graph 111 121 /// 112 /// Find the connected components of an undirected graph. 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. 113 128 /// 114 129 /// \image html connected_components.png 115 130 /// \image latex connected_components.eps "Connected components" width=\textwidth 116 131 /// 117 /// \param graph The graph. It must be undirected.132 /// \param graph The undirected graph. 118 133 /// \retval compMap A writable node map. The values will be set from 0 to 119 /// the number of the connected components minus one. Each value sof the map120 /// will be set exactly once, the values of a certain component will be134 /// the number of the connected components minus one. Each value of the map 135 /// will be set exactly once, and the values of a certain component will be 121 136 /// set continuously. 122 /// \return The number of components 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() 123 142 template <class Graph, class NodeMap> 124 143 int connectedComponents(const Graph &graph, NodeMap &compMap) { … … 232 251 /// \ingroup graph_properties 233 252 /// 234 /// \brief Check whether the givendirected graph is strongly connected.235 /// 236 /// Check whether the given directed graph is strongly connected. The237 /// graph is strongly connected when any two nodes of thegraph are253 /// \brief Check whether a directed graph is strongly connected. 254 /// 255 /// This function checks whether the given directed graph is strongly 256 /// connected, i.e. any two nodes of the digraph are 238 257 /// connected with directed paths in both direction. 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. 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() 243 264 template <typename Digraph> 244 265 bool stronglyConnected(const Digraph& digraph) { … … 271 292 RDigraph rdigraph(digraph); 272 293 273 typedef DfsVisitor< Digraph> RVisitor;294 typedef DfsVisitor<RDigraph> RVisitor; 274 295 RVisitor rvisitor; 275 296 … … 290 311 /// \ingroup graph_properties 291 312 /// 292 /// \brief Count the strongly connected components of a directed graph 293 /// 294 /// Count the strongly connected components of a directed graph. 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 /// 295 319 /// The strongly connected components are the classes of an 296 /// equivalence relation on the nodes of thegraph. Two nodes are in320 /// equivalence relation on the nodes of a digraph. Two nodes are in 297 321 /// the same class if they are connected with directed paths in both 298 322 /// direction. 299 323 /// 300 /// \param digraph The graph. 301 /// \return The number of components 302 /// \note By definition, the empty graph has zero 324 /// \return The number of strongly connected components. 325 /// \note By definition, the empty digraph has zero 303 326 /// strongly connected components. 327 /// 328 /// \see stronglyConnected(), stronglyConnectedComponents() 304 329 template <typename Digraph> 305 330 int countStronglyConnectedComponents(const Digraph& digraph) { … … 356 381 /// \brief Find the strongly connected components of a directed graph 357 382 /// 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. 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. 365 392 /// 366 393 /// \image html strongly_connected_components.png … … 370 397 /// \retval compMap A writable node map. The values will be set from 0 to 371 398 /// the number of the strongly connected components minus one. Each value 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 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() 375 406 template <typename Digraph, typename NodeMap> 376 407 int stronglyConnectedComponents(const Digraph& digraph, NodeMap& compMap) { … … 425 456 /// \brief Find the cut arcs of the strongly connected components. 426 457 /// 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. 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. 431 465 /// The strongly connected components are separated by the cut arcs. 432 466 /// 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 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() 438 474 template <typename Digraph, typename ArcMap> 439 int stronglyConnectedCutArcs(const Digraph& graph, ArcMap& cutMap) {475 int stronglyConnectedCutArcs(const Digraph& digraph, ArcMap& cutMap) { 440 476 checkConcept<concepts::Digraph, Digraph>(); 441 477 typedef typename Digraph::Node Node; … … 449 485 typedef typename Container::iterator Iterator; 450 486 451 Container nodes(countNodes( graph));487 Container nodes(countNodes(digraph)); 452 488 typedef LeaveOrderVisitor<Digraph, Iterator> Visitor; 453 489 Visitor visitor(nodes.begin()); 454 490 455 DfsVisit<Digraph, Visitor> dfs( graph, visitor);491 DfsVisit<Digraph, Visitor> dfs(digraph, visitor); 456 492 dfs.init(); 457 for (NodeIt it( graph); it != INVALID; ++it) {493 for (NodeIt it(digraph); it != INVALID; ++it) { 458 494 if (!dfs.reached(it)) { 459 495 dfs.addSource(it); … … 465 501 typedef ReverseDigraph<const Digraph> RDigraph; 466 502 467 RDigraph r graph(graph);503 RDigraph rdigraph(digraph); 468 504 469 505 int cutNum = 0; 470 506 471 507 typedef StronglyConnectedCutArcsVisitor<RDigraph, ArcMap> RVisitor; 472 RVisitor rvisitor(r graph, cutMap, cutNum);473 474 DfsVisit<RDigraph, RVisitor> rdfs(r graph, rvisitor);508 RVisitor rvisitor(rdigraph, cutMap, cutNum); 509 510 DfsVisit<RDigraph, RVisitor> rdfs(rdigraph, rvisitor); 475 511 476 512 rdfs.init(); … … 707 743 /// \ingroup graph_properties 708 744 /// 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. 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() 717 754 template <typename Graph> 718 755 bool biNodeConnected(const Graph& graph) { … … 722 759 /// \ingroup graph_properties 723 760 /// 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. 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() 733 774 template <typename Graph> 734 775 int countBiNodeConnectedComponents(const Graph& graph) { … … 757 798 /// \ingroup graph_properties 758 799 /// 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. 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. 765 808 /// 766 809 /// \image html node_biconnected_components.png 767 810 /// \image latex node_biconnected_components.eps "bi-node-connected components" width=\textwidth 768 811 /// 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. 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() 775 820 template <typename Graph, typename EdgeMap> 776 821 int biNodeConnectedComponents(const Graph& graph, … … 802 847 /// \ingroup graph_properties 803 848 /// 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. 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. 815 865 /// \return The number of the cut nodes. 866 /// 867 /// \see biNodeConnected(), biNodeConnectedComponents() 816 868 template <typename Graph, typename NodeMap> 817 869 int biNodeConnectedCutNodes(const Graph& graph, NodeMap& cutMap) { … … 1032 1084 /// \ingroup graph_properties 1033 1085 /// 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. 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() 1042 1096 template <typename Graph> 1043 1097 bool biEdgeConnected(const Graph& graph) { … … 1047 1101 /// \ingroup graph_properties 1048 1102 /// 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. 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() 1058 1117 template <typename Graph> 1059 1118 int countBiEdgeConnectedComponents(const Graph& graph) { … … 1082 1141 /// \ingroup graph_properties 1083 1142 /// 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. 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. 1090 1152 /// 1091 1153 /// \image html edge_biconnected_components.png 1092 1154 /// \image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth 1093 1155 /// 1094 /// \param graph The graph.1156 /// \param graph The undirected graph. 1095 1157 /// \retval compMap A writable node map. The values will be set from 0 to 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. 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() 1100 1164 template <typename Graph, typename NodeMap> 1101 1165 int biEdgeConnectedComponents(const Graph& graph, NodeMap& compMap) { … … 1126 1190 /// \ingroup graph_properties 1127 1191 /// 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. 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. 1140 1208 /// \return The number of cut edges. 1209 /// 1210 /// \see biEdgeConnected(), biEdgeConnectedComponents() 1141 1211 template <typename Graph, typename EdgeMap> 1142 1212 int biEdgeConnectedCutEdges(const Graph& graph, EdgeMap& cutMap) { … … 1190 1260 /// \ingroup graph_properties 1191 1261 /// 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; 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) { 1206 1270 1207 1271 checkConcept<concepts::Digraph, Digraph>(); 1208 checkConcept<concepts::WriteMap<typename Digraph::Node, int>, NodeMap>();1209 1272 1210 1273 typedef typename Digraph::Node Node; … … 1212 1275 typedef typename Digraph::Arc Arc; 1213 1276 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); 1284 1285 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 1214 1327 TopologicalSortVisitor<Digraph, NodeMap> 1215 visitor(order, countNodes( graph));1328 visitor(order, countNodes(digraph)); 1216 1329 1217 1330 DfsVisit<Digraph, TopologicalSortVisitor<Digraph, NodeMap> > 1218 dfs( graph, visitor);1331 dfs(digraph, visitor); 1219 1332 1220 1333 dfs.init(); 1221 for (NodeIt it( graph); it != INVALID; ++it) {1334 for (NodeIt it(digraph); it != INVALID; ++it) { 1222 1335 if (!dfs.reached(it)) { 1223 1336 dfs.addSource(it); … … 1231 1344 /// \brief Sort the nodes of a DAG into topolgical order. 1232 1345 /// 1233 /// Sort the nodes of a DAG into topolgical order. It also checks1234 /// 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 set1238 /// from 0 to the number of the nodes in the graph minus one. Each values1239 /// of the map will be set exactly once, the values will be set descending1240 /// order.1241 /// \return \c false when the graph is not DAG.1242 /// 1243 /// \see topologicalSort1244 /// \see dag 1346 /// This function sorts the nodes of the given acyclic digraph (DAG) 1347 /// into topolgical order and also checks whether the given digraph 1348 /// is DAG. 1349 /// 1350 /// \param digraph The digraph. 1351 /// \retval order A readable and writable node map. The values will be 1352 /// 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 will 1354 /// be set descending order. 1355 /// \return \c false if the digraph is not DAG. 1356 /// 1357 /// \see dag(), topologicalSort() 1245 1358 template <typename Digraph, typename NodeMap> 1246 1359 bool checkedTopologicalSort(const Digraph& digraph, NodeMap& order) { … … 1284 1397 /// \ingroup graph_properties 1285 1398 /// 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 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() 1334 1404 template <typename Graph> 1335 1405 bool acyclic(const Graph& graph) { … … 1344 1414 dfs.addSource(it); 1345 1415 while (!dfs.emptyQueue()) { 1346 Arc edge= dfs.nextArc();1347 Node source = graph.source( edge);1348 Node target = graph.target( edge);1416 Arc arc = dfs.nextArc(); 1417 Node source = graph.source(arc); 1418 Node target = graph.target(arc); 1349 1419 if (dfs.reached(target) && 1350 dfs.predArc(source) != graph.oppositeArc( edge)) {1420 dfs.predArc(source) != graph.oppositeArc(arc)) { 1351 1421 return false; 1352 1422 } … … 1360 1430 /// \ingroup graph_properties 1361 1431 /// 1362 /// \brief Check that the given undirected graph is tree.1363 /// 1364 /// Check thatthe given undirected graph is tree.1365 /// \ param graph The undirected graph.1366 /// \ return \c true when the graph is acyclic and connected.1432 /// \brief Check whether an undirected graph is tree. 1433 /// 1434 /// This function checks whether the given undirected graph is tree. 1435 /// \return \c true if the graph is acyclic and connected. 1436 /// \see acyclic(), connected() 1367 1437 template <typename Graph> 1368 1438 bool tree(const Graph& graph) { … … 1371 1441 typedef typename Graph::NodeIt NodeIt; 1372 1442 typedef typename Graph::Arc Arc; 1443 if (NodeIt(graph) == INVALID) return true; 1373 1444 Dfs<Graph> dfs(graph); 1374 1445 dfs.init(); 1375 1446 dfs.addSource(NodeIt(graph)); 1376 1447 while (!dfs.emptyQueue()) { 1377 Arc edge= dfs.nextArc();1378 Node source = graph.source( edge);1379 Node target = graph.target( edge);1448 Arc arc = dfs.nextArc(); 1449 Node source = graph.source(arc); 1450 Node target = graph.target(arc); 1380 1451 if (dfs.reached(target) && 1381 dfs.predArc(source) != graph.oppositeArc( edge)) {1452 dfs.predArc(source) != graph.oppositeArc(arc)) { 1382 1453 return false; 1383 1454 } … … 1452 1523 /// \ingroup graph_properties 1453 1524 /// 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 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() 1461 1531 template<typename Graph> 1462 inlinebool bipartite(const Graph &graph){1532 bool bipartite(const Graph &graph){ 1463 1533 using namespace _connectivity_bits; 1464 1534 … … 1489 1559 /// \ingroup graph_properties 1490 1560 /// 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. 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. 1497 1565 /// 1498 1566 /// \image html bipartite_partitions.png … … 1500 1568 /// 1501 1569 /// \param graph The undirected graph. 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. 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() 1505 1576 template<typename Graph, typename NodeMap> 1506 inlinebool bipartitePartitions(const Graph &graph, NodeMap &partMap){1577 bool bipartitePartitions(const Graph &graph, NodeMap &partMap){ 1507 1578 using namespace _connectivity_bits; 1508 1579 1509 1580 checkConcept<concepts::Graph, Graph>(); 1581 checkConcept<concepts::WriteMap<typename Graph::Node, bool>, NodeMap>(); 1510 1582 1511 1583 typedef typename Graph::Node Node; … … 1532 1604 } 1533 1605 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; 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; 1541 1616 } 1542 1617 return true; 1543 1618 } 1544 1619 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 } 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; 1559 1636 } 1560 1637 return true; 1561 1638 } 1562 1639 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); 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; 1581 1659 } 1582 1660 return true; -
lemon/euler.h
r592 r648 245 245 246 246 247 ///Check if the given graph is \eEulerian247 ///Check if the given graph is Eulerian 248 248 249 249 /// \ingroup graph_properties 250 ///This function checks if the given graph is \eEulerian.250 ///This function checks if the given graph is Eulerian. 251 251 ///It works for both directed and undirected graphs. 252 252 /// -
test/CMakeLists.txt
r627 r649 10 10 bfs_test 11 11 circulation_test 12 connectivity_test 12 13 counter_test 13 14 dfs_test -
test/Makefile.am
r611 r649 10 10 test/bfs_test \ 11 11 test/circulation_test \ 12 test/connectivity_test \ 12 13 test/counter_test \ 13 14 test/dfs_test \ … … 55 56 test_circulation_test_SOURCES = test/circulation_test.cc 56 57 test_counter_test_SOURCES = test/counter_test.cc 58 test_connectivity_test_SOURCES = test/connectivity_test.cc 57 59 test_dfs_test_SOURCES = test/dfs_test.cc 58 60 test_digraph_test_SOURCES = test/digraph_test.cc
Note: See TracChangeset
for help on using the changeset viewer.