Changes in lemon/connectivity.h [440:88ed40ad0d4f:586:7c12061bd271] in lemon-1.2
- File:
-
- 1 edited
-
lemon/connectivity.h (modified) (39 diffs)
Legend:
- Unmodified
- Added
- Removed
-
lemon/connectivity.h
r440 r586 33 33 #include <functional> 34 34 35 /// \ingroup connectivity35 /// \ingroup graph_properties 36 36 /// \file 37 37 /// \brief Connectivity algorithms … … 41 41 namespace lemon { 42 42 43 /// \ingroup connectivity43 /// \ingroup graph_properties 44 44 /// 45 45 /// \brief Check whether the given undirected graph is connected. … … 47 47 /// Check whether the given undirected graph is connected. 48 48 /// \param graph The undirected graph. 49 /// \return %True when there is path between any two nodes in the graph.49 /// \return \c true when there is path between any two nodes in the graph. 50 50 /// \note By definition, the empty graph is connected. 51 51 template <typename Graph> … … 64 64 } 65 65 66 /// \ingroup connectivity66 /// \ingroup graph_properties 67 67 /// 68 68 /// \brief Count the number of connected components of an undirected graph … … 106 106 } 107 107 108 /// \ingroup connectivity108 /// \ingroup graph_properties 109 109 /// 110 110 /// \brief Find the connected components of an undirected graph 111 111 /// 112 112 /// Find the connected components of an undirected graph. 113 /// 114 /// \image html connected_components.png 115 /// \image latex connected_components.eps "Connected components" width=\textwidth 113 116 /// 114 117 /// \param graph The graph. It must be undirected. … … 118 121 /// set continuously. 119 122 /// \return The number of components 120 ///121 123 template <class Graph, class NodeMap> 122 124 int connectedComponents(const Graph &graph, NodeMap &compMap) { … … 228 230 229 231 230 /// \ingroup connectivity232 /// \ingroup graph_properties 231 233 /// 232 234 /// \brief Check whether the given directed graph is strongly connected. … … 235 237 /// graph is strongly connected when any two nodes of the graph are 236 238 /// connected with directed paths in both direction. 237 /// \return %False when the graph is not strongly connected.239 /// \return \c false when the graph is not strongly connected. 238 240 /// \see connected 239 241 /// … … 286 288 } 287 289 288 /// \ingroup connectivity290 /// \ingroup graph_properties 289 291 /// 290 292 /// \brief Count the strongly connected components of a directed graph … … 350 352 } 351 353 352 /// \ingroup connectivity354 /// \ingroup graph_properties 353 355 /// 354 356 /// \brief Find the strongly connected components of a directed graph … … 362 364 /// a lower. 363 365 /// 366 /// \image html strongly_connected_components.png 367 /// \image latex strongly_connected_components.eps "Strongly connected components" width=\textwidth 368 /// 364 369 /// \param digraph The digraph. 365 370 /// \retval compMap A writable node map. The values will be set from 0 to … … 368 373 /// will be set continuously. 369 374 /// \return The number of components 370 ///371 375 template <typename Digraph, typename NodeMap> 372 376 int stronglyConnectedComponents(const Digraph& digraph, NodeMap& compMap) { … … 417 421 } 418 422 419 /// \ingroup connectivity423 /// \ingroup graph_properties 420 424 /// 421 425 /// \brief Find the cut arcs of the strongly connected components. … … 701 705 int countBiNodeConnectedComponents(const Graph& graph); 702 706 703 /// \ingroup connectivity707 /// \ingroup graph_properties 704 708 /// 705 709 /// \brief Checks the graph is bi-node-connected. … … 710 714 /// 711 715 /// \param graph The graph. 712 /// \return %True when the graph bi-node-connected.716 /// \return \c true when the graph bi-node-connected. 713 717 template <typename Graph> 714 718 bool biNodeConnected(const Graph& graph) { … … 716 720 } 717 721 718 /// \ingroup connectivity722 /// \ingroup graph_properties 719 723 /// 720 724 /// \brief Count the biconnected components. … … 751 755 } 752 756 753 /// \ingroup connectivity757 /// \ingroup graph_properties 754 758 /// 755 759 /// \brief Find the bi-node-connected components. … … 759 763 /// relation on the undirected edges. Two undirected edge are in relationship 760 764 /// when they are on same circle. 765 /// 766 /// \image html node_biconnected_components.png 767 /// \image latex node_biconnected_components.eps "bi-node-connected components" width=\textwidth 761 768 /// 762 769 /// \param graph The graph. … … 766 773 /// will be set continuously. 767 774 /// \return The number of components. 768 ///769 775 template <typename Graph, typename EdgeMap> 770 776 int biNodeConnectedComponents(const Graph& graph, … … 794 800 } 795 801 796 /// \ingroup connectivity802 /// \ingroup graph_properties 797 803 /// 798 804 /// \brief Find the bi-node-connected cut nodes. … … 1024 1030 int countBiEdgeConnectedComponents(const Graph& graph); 1025 1031 1026 /// \ingroup connectivity1032 /// \ingroup graph_properties 1027 1033 /// 1028 1034 /// \brief Checks that the graph is bi-edge-connected. … … 1039 1045 } 1040 1046 1041 /// \ingroup connectivity1047 /// \ingroup graph_properties 1042 1048 /// 1043 1049 /// \brief Count the bi-edge-connected components. … … 1074 1080 } 1075 1081 1076 /// \ingroup connectivity1082 /// \ingroup graph_properties 1077 1083 /// 1078 1084 /// \brief Find the bi-edge-connected components. … … 1082 1088 /// relation on the nodes. Two nodes are in relationship when they are 1083 1089 /// connected at least two edge-disjoint paths. 1090 /// 1091 /// \image html edge_biconnected_components.png 1092 /// \image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth 1084 1093 /// 1085 1094 /// \param graph The graph. … … 1089 1098 /// will be set continuously. 1090 1099 /// \return The number of components. 1091 ///1092 1100 template <typename Graph, typename NodeMap> 1093 1101 int biEdgeConnectedComponents(const Graph& graph, NodeMap& compMap) { … … 1116 1124 } 1117 1125 1118 /// \ingroup connectivity1126 /// \ingroup graph_properties 1119 1127 /// 1120 1128 /// \brief Find the bi-edge-connected cut edges. … … 1180 1188 } 1181 1189 1182 /// \ingroup connectivity1190 /// \ingroup graph_properties 1183 1191 /// 1184 1192 /// \brief Sort the nodes of a DAG into topolgical order. … … 1219 1227 } 1220 1228 1221 /// \ingroup connectivity1229 /// \ingroup graph_properties 1222 1230 /// 1223 1231 /// \brief Sort the nodes of a DAG into topolgical order. … … 1231 1239 /// of the map will be set exactly once, the values will be set descending 1232 1240 /// order. 1233 /// \return %False when the graph is not DAG.1241 /// \return \c false when the graph is not DAG. 1234 1242 /// 1235 1243 /// \see topologicalSort … … 1274 1282 } 1275 1283 1276 /// \ingroup connectivity1284 /// \ingroup graph_properties 1277 1285 /// 1278 1286 /// \brief Check that the given directed graph is a DAG. … … 1280 1288 /// Check that the given directed graph is a DAG. The DAG is 1281 1289 /// an Directed Acyclic Digraph. 1282 /// \return %False when the graph is not DAG.1290 /// \return \c false when the graph is not DAG. 1283 1291 /// \see acyclic 1284 1292 template <typename Digraph> … … 1316 1324 } 1317 1325 1318 /// \ingroup connectivity1326 /// \ingroup graph_properties 1319 1327 /// 1320 1328 /// \brief Check that the given undirected graph is acyclic. … … 1322 1330 /// Check that the given undirected graph acyclic. 1323 1331 /// \param graph The undirected graph. 1324 /// \return %True when there is no circle in the graph.1332 /// \return \c true when there is no circle in the graph. 1325 1333 /// \see dag 1326 1334 template <typename Graph> … … 1350 1358 } 1351 1359 1352 /// \ingroup connectivity1360 /// \ingroup graph_properties 1353 1361 /// 1354 1362 /// \brief Check that the given undirected graph is tree. … … 1356 1364 /// Check that the given undirected graph is tree. 1357 1365 /// \param graph The undirected graph. 1358 /// \return %True when the graph is acyclic and connected.1366 /// \return \c true when the graph is acyclic and connected. 1359 1367 template <typename Graph> 1360 1368 bool tree(const Graph& graph) { … … 1442 1450 } 1443 1451 1444 /// \ingroup connectivity1452 /// \ingroup graph_properties 1445 1453 /// 1446 1454 /// \brief Check if the given undirected graph is bipartite or not … … 1449 1457 /// or not. The \ref Bfs algorithm is used to calculate the result. 1450 1458 /// \param graph The undirected graph. 1451 /// \return %True if \c graph is bipartite, %false otherwise.1459 /// \return \c true if \c graph is bipartite, \c false otherwise. 1452 1460 /// \sa bipartitePartitions 1453 1461 template<typename Graph> … … 1479 1487 } 1480 1488 1481 /// \ingroup connectivity1489 /// \ingroup graph_properties 1482 1490 /// 1483 1491 /// \brief Check if the given undirected graph is bipartite or not … … 1487 1495 /// During the execution, the \c partMap will be set as the two 1488 1496 /// partitions of the graph. 1497 /// 1498 /// \image html bipartite_partitions.png 1499 /// \image latex bipartite_partitions.eps "Bipartite partititions" width=\textwidth 1500 /// 1489 1501 /// \param graph The undirected graph. 1490 1502 /// \retval partMap A writable bool map of nodes. It will be set as the 1491 1503 /// two partitions of the graph. 1492 /// \return %True if \c graph is bipartite, %false otherwise.1504 /// \return \c true if \c graph is bipartite, \c false otherwise. 1493 1505 template<typename Graph, typename NodeMap> 1494 1506 inline bool bipartitePartitions(const Graph &graph, NodeMap &partMap){
Note: See TracChangeset
for help on using the changeset viewer.
