1.1 --- a/lemon/connectivity.h Tue Apr 14 10:40:33 2009 +0100
1.2 +++ b/lemon/connectivity.h Wed Apr 15 04:26:13 2009 +0200
1.3 @@ -32,7 +32,7 @@
1.4 #include <stack>
1.5 #include <functional>
1.6
1.7 -/// \ingroup connectivity
1.8 +/// \ingroup graph_properties
1.9 /// \file
1.10 /// \brief Connectivity algorithms
1.11 ///
1.12 @@ -40,7 +40,7 @@
1.13
1.14 namespace lemon {
1.15
1.16 - /// \ingroup connectivity
1.17 + /// \ingroup graph_properties
1.18 ///
1.19 /// \brief Check whether the given undirected graph is connected.
1.20 ///
1.21 @@ -63,7 +63,7 @@
1.22 return true;
1.23 }
1.24
1.25 - /// \ingroup connectivity
1.26 + /// \ingroup graph_properties
1.27 ///
1.28 /// \brief Count the number of connected components of an undirected graph
1.29 ///
1.30 @@ -105,19 +105,21 @@
1.31 return compNum;
1.32 }
1.33
1.34 - /// \ingroup connectivity
1.35 + /// \ingroup graph_properties
1.36 ///
1.37 /// \brief Find the connected components of an undirected graph
1.38 ///
1.39 /// Find the connected components of an undirected graph.
1.40 ///
1.41 + /// \image html connected_components.png
1.42 + /// \image latex connected_components.eps "Connected components" width=\textwidth
1.43 + ///
1.44 /// \param graph The graph. It must be undirected.
1.45 /// \retval compMap A writable node map. The values will be set from 0 to
1.46 /// the number of the connected components minus one. Each values of the map
1.47 /// will be set exactly once, the values of a certain component will be
1.48 /// set continuously.
1.49 /// \return The number of components
1.50 - ///
1.51 template <class Graph, class NodeMap>
1.52 int connectedComponents(const Graph &graph, NodeMap &compMap) {
1.53 checkConcept<concepts::Graph, Graph>();
1.54 @@ -227,7 +229,7 @@
1.55 }
1.56
1.57
1.58 - /// \ingroup connectivity
1.59 + /// \ingroup graph_properties
1.60 ///
1.61 /// \brief Check whether the given directed graph is strongly connected.
1.62 ///
1.63 @@ -285,7 +287,7 @@
1.64 return true;
1.65 }
1.66
1.67 - /// \ingroup connectivity
1.68 + /// \ingroup graph_properties
1.69 ///
1.70 /// \brief Count the strongly connected components of a directed graph
1.71 ///
1.72 @@ -349,7 +351,7 @@
1.73 return compNum;
1.74 }
1.75
1.76 - /// \ingroup connectivity
1.77 + /// \ingroup graph_properties
1.78 ///
1.79 /// \brief Find the strongly connected components of a directed graph
1.80 ///
1.81 @@ -361,13 +363,15 @@
1.82 /// that there is no arc going from a higher numbered component to
1.83 /// a lower.
1.84 ///
1.85 + /// \image html strongly_connected_components.png
1.86 + /// \image latex strongly_connected_components.eps "Strongly connected components" width=\textwidth
1.87 + ///
1.88 /// \param digraph The digraph.
1.89 /// \retval compMap A writable node map. The values will be set from 0 to
1.90 /// the number of the strongly connected components minus one. Each value
1.91 /// of the map will be set exactly once, the values of a certain component
1.92 /// will be set continuously.
1.93 /// \return The number of components
1.94 - ///
1.95 template <typename Digraph, typename NodeMap>
1.96 int stronglyConnectedComponents(const Digraph& digraph, NodeMap& compMap) {
1.97 checkConcept<concepts::Digraph, Digraph>();
1.98 @@ -416,7 +420,7 @@
1.99 return compNum;
1.100 }
1.101
1.102 - /// \ingroup connectivity
1.103 + /// \ingroup graph_properties
1.104 ///
1.105 /// \brief Find the cut arcs of the strongly connected components.
1.106 ///
1.107 @@ -700,7 +704,7 @@
1.108 template <typename Graph>
1.109 int countBiNodeConnectedComponents(const Graph& graph);
1.110
1.111 - /// \ingroup connectivity
1.112 + /// \ingroup graph_properties
1.113 ///
1.114 /// \brief Checks the graph is bi-node-connected.
1.115 ///
1.116 @@ -715,7 +719,7 @@
1.117 return countBiNodeConnectedComponents(graph) <= 1;
1.118 }
1.119
1.120 - /// \ingroup connectivity
1.121 + /// \ingroup graph_properties
1.122 ///
1.123 /// \brief Count the biconnected components.
1.124 ///
1.125 @@ -750,7 +754,7 @@
1.126 return compNum;
1.127 }
1.128
1.129 - /// \ingroup connectivity
1.130 + /// \ingroup graph_properties
1.131 ///
1.132 /// \brief Find the bi-node-connected components.
1.133 ///
1.134 @@ -759,13 +763,15 @@
1.135 /// relation on the undirected edges. Two undirected edge are in relationship
1.136 /// when they are on same circle.
1.137 ///
1.138 + /// \image html node_biconnected_components.png
1.139 + /// \image latex node_biconnected_components.eps "bi-node-connected components" width=\textwidth
1.140 + ///
1.141 /// \param graph The graph.
1.142 /// \retval compMap A writable uedge map. The values will be set from 0
1.143 /// to the number of the biconnected components minus one. Each values
1.144 /// of the map will be set exactly once, the values of a certain component
1.145 /// will be set continuously.
1.146 /// \return The number of components.
1.147 - ///
1.148 template <typename Graph, typename EdgeMap>
1.149 int biNodeConnectedComponents(const Graph& graph,
1.150 EdgeMap& compMap) {
1.151 @@ -793,7 +799,7 @@
1.152 return compNum;
1.153 }
1.154
1.155 - /// \ingroup connectivity
1.156 + /// \ingroup graph_properties
1.157 ///
1.158 /// \brief Find the bi-node-connected cut nodes.
1.159 ///
1.160 @@ -1023,7 +1029,7 @@
1.161 template <typename Graph>
1.162 int countBiEdgeConnectedComponents(const Graph& graph);
1.163
1.164 - /// \ingroup connectivity
1.165 + /// \ingroup graph_properties
1.166 ///
1.167 /// \brief Checks that the graph is bi-edge-connected.
1.168 ///
1.169 @@ -1038,7 +1044,7 @@
1.170 return countBiEdgeConnectedComponents(graph) <= 1;
1.171 }
1.172
1.173 - /// \ingroup connectivity
1.174 + /// \ingroup graph_properties
1.175 ///
1.176 /// \brief Count the bi-edge-connected components.
1.177 ///
1.178 @@ -1073,7 +1079,7 @@
1.179 return compNum;
1.180 }
1.181
1.182 - /// \ingroup connectivity
1.183 + /// \ingroup graph_properties
1.184 ///
1.185 /// \brief Find the bi-edge-connected components.
1.186 ///
1.187 @@ -1082,13 +1088,15 @@
1.188 /// relation on the nodes. Two nodes are in relationship when they are
1.189 /// connected at least two edge-disjoint paths.
1.190 ///
1.191 + /// \image html edge_biconnected_components.png
1.192 + /// \image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth
1.193 + ///
1.194 /// \param graph The graph.
1.195 /// \retval compMap A writable node map. The values will be set from 0 to
1.196 /// the number of the biconnected components minus one. Each values
1.197 /// of the map will be set exactly once, the values of a certain component
1.198 /// will be set continuously.
1.199 /// \return The number of components.
1.200 - ///
1.201 template <typename Graph, typename NodeMap>
1.202 int biEdgeConnectedComponents(const Graph& graph, NodeMap& compMap) {
1.203 checkConcept<concepts::Graph, Graph>();
1.204 @@ -1115,7 +1123,7 @@
1.205 return compNum;
1.206 }
1.207
1.208 - /// \ingroup connectivity
1.209 + /// \ingroup graph_properties
1.210 ///
1.211 /// \brief Find the bi-edge-connected cut edges.
1.212 ///
1.213 @@ -1179,7 +1187,7 @@
1.214
1.215 }
1.216
1.217 - /// \ingroup connectivity
1.218 + /// \ingroup graph_properties
1.219 ///
1.220 /// \brief Sort the nodes of a DAG into topolgical order.
1.221 ///
1.222 @@ -1218,7 +1226,7 @@
1.223 }
1.224 }
1.225
1.226 - /// \ingroup connectivity
1.227 + /// \ingroup graph_properties
1.228 ///
1.229 /// \brief Sort the nodes of a DAG into topolgical order.
1.230 ///
1.231 @@ -1273,7 +1281,7 @@
1.232 return true;
1.233 }
1.234
1.235 - /// \ingroup connectivity
1.236 + /// \ingroup graph_properties
1.237 ///
1.238 /// \brief Check that the given directed graph is a DAG.
1.239 ///
1.240 @@ -1315,7 +1323,7 @@
1.241 return true;
1.242 }
1.243
1.244 - /// \ingroup connectivity
1.245 + /// \ingroup graph_properties
1.246 ///
1.247 /// \brief Check that the given undirected graph is acyclic.
1.248 ///
1.249 @@ -1349,7 +1357,7 @@
1.250 return true;
1.251 }
1.252
1.253 - /// \ingroup connectivity
1.254 + /// \ingroup graph_properties
1.255 ///
1.256 /// \brief Check that the given undirected graph is tree.
1.257 ///
1.258 @@ -1441,7 +1449,7 @@
1.259 };
1.260 }
1.261
1.262 - /// \ingroup connectivity
1.263 + /// \ingroup graph_properties
1.264 ///
1.265 /// \brief Check if the given undirected graph is bipartite or not
1.266 ///
1.267 @@ -1478,7 +1486,7 @@
1.268 return true;
1.269 }
1.270
1.271 - /// \ingroup connectivity
1.272 + /// \ingroup graph_properties
1.273 ///
1.274 /// \brief Check if the given undirected graph is bipartite or not
1.275 ///
1.276 @@ -1486,6 +1494,10 @@
1.277 /// or not. The \ref Bfs algorithm is used to calculate the result.
1.278 /// During the execution, the \c partMap will be set as the two
1.279 /// partitions of the graph.
1.280 + ///
1.281 + /// \image html bipartite_partitions.png
1.282 + /// \image latex bipartite_partitions.eps "Bipartite partititions" width=\textwidth
1.283 + ///
1.284 /// \param graph The undirected graph.
1.285 /// \retval partMap A writable bool map of nodes. It will be set as the
1.286 /// two partitions of the graph.