Changes in lemon/connectivity.h [633:7c12061bd271:463:88ed40ad0d4f] in lemon
- File:
-
- 1 edited
-
lemon/connectivity.h (modified) (39 diffs)
Legend:
- Unmodified
- Added
- Removed
-
lemon/connectivity.h
r633 r463 33 33 #include <functional> 34 34 35 /// \ingroup graph_properties35 /// \ingroup connectivity 36 36 /// \file 37 37 /// \brief Connectivity algorithms … … 41 41 namespace lemon { 42 42 43 /// \ingroup graph_properties43 /// \ingroup connectivity 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 \c true when there is path between any two nodes in the graph.49 /// \return %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 graph_properties66 /// \ingroup connectivity 67 67 /// 68 68 /// \brief Count the number of connected components of an undirected graph … … 106 106 } 107 107 108 /// \ingroup graph_properties108 /// \ingroup connectivity 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.png115 /// \image latex connected_components.eps "Connected components" width=\textwidth116 113 /// 117 114 /// \param graph The graph. It must be undirected. … … 121 118 /// set continuously. 122 119 /// \return The number of components 120 /// 123 121 template <class Graph, class NodeMap> 124 122 int connectedComponents(const Graph &graph, NodeMap &compMap) { … … 230 228 231 229 232 /// \ingroup graph_properties230 /// \ingroup connectivity 233 231 /// 234 232 /// \brief Check whether the given directed graph is strongly connected. … … 237 235 /// graph is strongly connected when any two nodes of the graph are 238 236 /// connected with directed paths in both direction. 239 /// \return \c false when the graph is not strongly connected.237 /// \return %False when the graph is not strongly connected. 240 238 /// \see connected 241 239 /// … … 288 286 } 289 287 290 /// \ingroup graph_properties288 /// \ingroup connectivity 291 289 /// 292 290 /// \brief Count the strongly connected components of a directed graph … … 352 350 } 353 351 354 /// \ingroup graph_properties352 /// \ingroup connectivity 355 353 /// 356 354 /// \brief Find the strongly connected components of a directed graph … … 364 362 /// a lower. 365 363 /// 366 /// \image html strongly_connected_components.png367 /// \image latex strongly_connected_components.eps "Strongly connected components" width=\textwidth368 ///369 364 /// \param digraph The digraph. 370 365 /// \retval compMap A writable node map. The values will be set from 0 to … … 373 368 /// will be set continuously. 374 369 /// \return The number of components 370 /// 375 371 template <typename Digraph, typename NodeMap> 376 372 int stronglyConnectedComponents(const Digraph& digraph, NodeMap& compMap) { … … 421 417 } 422 418 423 /// \ingroup graph_properties419 /// \ingroup connectivity 424 420 /// 425 421 /// \brief Find the cut arcs of the strongly connected components. … … 705 701 int countBiNodeConnectedComponents(const Graph& graph); 706 702 707 /// \ingroup graph_properties703 /// \ingroup connectivity 708 704 /// 709 705 /// \brief Checks the graph is bi-node-connected. … … 714 710 /// 715 711 /// \param graph The graph. 716 /// \return \c true when the graph bi-node-connected.712 /// \return %True when the graph bi-node-connected. 717 713 template <typename Graph> 718 714 bool biNodeConnected(const Graph& graph) { … … 720 716 } 721 717 722 /// \ingroup graph_properties718 /// \ingroup connectivity 723 719 /// 724 720 /// \brief Count the biconnected components. … … 755 751 } 756 752 757 /// \ingroup graph_properties753 /// \ingroup connectivity 758 754 /// 759 755 /// \brief Find the bi-node-connected components. … … 763 759 /// relation on the undirected edges. Two undirected edge are in relationship 764 760 /// when they are on same circle. 765 ///766 /// \image html node_biconnected_components.png767 /// \image latex node_biconnected_components.eps "bi-node-connected components" width=\textwidth768 761 /// 769 762 /// \param graph The graph. … … 773 766 /// will be set continuously. 774 767 /// \return The number of components. 768 /// 775 769 template <typename Graph, typename EdgeMap> 776 770 int biNodeConnectedComponents(const Graph& graph, … … 800 794 } 801 795 802 /// \ingroup graph_properties796 /// \ingroup connectivity 803 797 /// 804 798 /// \brief Find the bi-node-connected cut nodes. … … 1030 1024 int countBiEdgeConnectedComponents(const Graph& graph); 1031 1025 1032 /// \ingroup graph_properties1026 /// \ingroup connectivity 1033 1027 /// 1034 1028 /// \brief Checks that the graph is bi-edge-connected. … … 1045 1039 } 1046 1040 1047 /// \ingroup graph_properties1041 /// \ingroup connectivity 1048 1042 /// 1049 1043 /// \brief Count the bi-edge-connected components. … … 1080 1074 } 1081 1075 1082 /// \ingroup graph_properties1076 /// \ingroup connectivity 1083 1077 /// 1084 1078 /// \brief Find the bi-edge-connected components. … … 1088 1082 /// relation on the nodes. Two nodes are in relationship when they are 1089 1083 /// connected at least two edge-disjoint paths. 1090 ///1091 /// \image html edge_biconnected_components.png1092 /// \image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth1093 1084 /// 1094 1085 /// \param graph The graph. … … 1098 1089 /// will be set continuously. 1099 1090 /// \return The number of components. 1091 /// 1100 1092 template <typename Graph, typename NodeMap> 1101 1093 int biEdgeConnectedComponents(const Graph& graph, NodeMap& compMap) { … … 1124 1116 } 1125 1117 1126 /// \ingroup graph_properties1118 /// \ingroup connectivity 1127 1119 /// 1128 1120 /// \brief Find the bi-edge-connected cut edges. … … 1188 1180 } 1189 1181 1190 /// \ingroup graph_properties1182 /// \ingroup connectivity 1191 1183 /// 1192 1184 /// \brief Sort the nodes of a DAG into topolgical order. … … 1227 1219 } 1228 1220 1229 /// \ingroup graph_properties1221 /// \ingroup connectivity 1230 1222 /// 1231 1223 /// \brief Sort the nodes of a DAG into topolgical order. … … 1239 1231 /// of the map will be set exactly once, the values will be set descending 1240 1232 /// order. 1241 /// \return \c false when the graph is not DAG.1233 /// \return %False when the graph is not DAG. 1242 1234 /// 1243 1235 /// \see topologicalSort … … 1282 1274 } 1283 1275 1284 /// \ingroup graph_properties1276 /// \ingroup connectivity 1285 1277 /// 1286 1278 /// \brief Check that the given directed graph is a DAG. … … 1288 1280 /// Check that the given directed graph is a DAG. The DAG is 1289 1281 /// an Directed Acyclic Digraph. 1290 /// \return \c false when the graph is not DAG.1282 /// \return %False when the graph is not DAG. 1291 1283 /// \see acyclic 1292 1284 template <typename Digraph> … … 1324 1316 } 1325 1317 1326 /// \ingroup graph_properties1318 /// \ingroup connectivity 1327 1319 /// 1328 1320 /// \brief Check that the given undirected graph is acyclic. … … 1330 1322 /// Check that the given undirected graph acyclic. 1331 1323 /// \param graph The undirected graph. 1332 /// \return \c true when there is no circle in the graph.1324 /// \return %True when there is no circle in the graph. 1333 1325 /// \see dag 1334 1326 template <typename Graph> … … 1358 1350 } 1359 1351 1360 /// \ingroup graph_properties1352 /// \ingroup connectivity 1361 1353 /// 1362 1354 /// \brief Check that the given undirected graph is tree. … … 1364 1356 /// Check that the given undirected graph is tree. 1365 1357 /// \param graph The undirected graph. 1366 /// \return \c true when the graph is acyclic and connected.1358 /// \return %True when the graph is acyclic and connected. 1367 1359 template <typename Graph> 1368 1360 bool tree(const Graph& graph) { … … 1450 1442 } 1451 1443 1452 /// \ingroup graph_properties1444 /// \ingroup connectivity 1453 1445 /// 1454 1446 /// \brief Check if the given undirected graph is bipartite or not … … 1457 1449 /// or not. The \ref Bfs algorithm is used to calculate the result. 1458 1450 /// \param graph The undirected graph. 1459 /// \return \c true if \c graph is bipartite, \cfalse otherwise.1451 /// \return %True if \c graph is bipartite, %false otherwise. 1460 1452 /// \sa bipartitePartitions 1461 1453 template<typename Graph> … … 1487 1479 } 1488 1480 1489 /// \ingroup graph_properties1481 /// \ingroup connectivity 1490 1482 /// 1491 1483 /// \brief Check if the given undirected graph is bipartite or not … … 1495 1487 /// During the execution, the \c partMap will be set as the two 1496 1488 /// partitions of the graph. 1497 ///1498 /// \image html bipartite_partitions.png1499 /// \image latex bipartite_partitions.eps "Bipartite partititions" width=\textwidth1500 ///1501 1489 /// \param graph The undirected graph. 1502 1490 /// \retval partMap A writable bool map of nodes. It will be set as the 1503 1491 /// two partitions of the graph. 1504 /// \return \c true if \c graph is bipartite, \cfalse otherwise.1492 /// \return %True if \c graph is bipartite, %false otherwise. 1505 1493 template<typename Graph, typename NodeMap> 1506 1494 inline bool bipartitePartitions(const Graph &graph, NodeMap &partMap){
Note: See TracChangeset
for help on using the changeset viewer.
