1.1 --- a/lemon/connectivity.h Mon Jan 12 23:11:39 2009 +0100
1.2 +++ b/lemon/connectivity.h Thu Nov 05 15:48:01 2009 +0100
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,14 +40,18 @@
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 + /// \brief Check whether an undirected graph is connected.
1.21 ///
1.22 - /// Check whether the given undirected graph is connected.
1.23 - /// \param graph The undirected graph.
1.24 - /// \return %True when there is path between any two nodes in the graph.
1.25 + /// This function checks whether the given undirected graph is connected,
1.26 + /// i.e. there is a path between any two nodes in the graph.
1.27 + ///
1.28 + /// \return \c true if the graph is connected.
1.29 /// \note By definition, the empty graph is connected.
1.30 + ///
1.31 + /// \see countConnectedComponents(), connectedComponents()
1.32 + /// \see stronglyConnected()
1.33 template <typename Graph>
1.34 bool connected(const Graph& graph) {
1.35 checkConcept<concepts::Graph, Graph>();
1.36 @@ -63,16 +67,22 @@
1.37 return true;
1.38 }
1.39
1.40 - /// \ingroup connectivity
1.41 + /// \ingroup graph_properties
1.42 ///
1.43 /// \brief Count the number of connected components of an undirected graph
1.44 ///
1.45 - /// Count the number of connected components of an undirected graph
1.46 + /// This function counts the number of connected components of the given
1.47 + /// undirected graph.
1.48 ///
1.49 - /// \param graph The graph. It must be undirected.
1.50 - /// \return The number of components
1.51 + /// The connected components are the classes of an equivalence relation
1.52 + /// on the nodes of an undirected graph. Two nodes are in the same class
1.53 + /// if they are connected with a path.
1.54 + ///
1.55 + /// \return The number of connected components.
1.56 /// \note By definition, the empty graph consists
1.57 /// of zero connected components.
1.58 + ///
1.59 + /// \see connected(), connectedComponents()
1.60 template <typename Graph>
1.61 int countConnectedComponents(const Graph &graph) {
1.62 checkConcept<concepts::Graph, Graph>();
1.63 @@ -105,19 +115,30 @@
1.64 return compNum;
1.65 }
1.66
1.67 - /// \ingroup connectivity
1.68 + /// \ingroup graph_properties
1.69 ///
1.70 /// \brief Find the connected components of an undirected graph
1.71 ///
1.72 - /// Find the connected components of an undirected graph.
1.73 + /// This function finds the connected components of the given undirected
1.74 + /// graph.
1.75 ///
1.76 - /// \param graph The graph. It must be undirected.
1.77 + /// The connected components are the classes of an equivalence relation
1.78 + /// on the nodes of an undirected graph. Two nodes are in the same class
1.79 + /// if they are connected with a path.
1.80 + ///
1.81 + /// \image html connected_components.png
1.82 + /// \image latex connected_components.eps "Connected components" width=\textwidth
1.83 + ///
1.84 + /// \param graph The undirected graph.
1.85 /// \retval compMap A writable node map. The values will be set from 0 to
1.86 - /// the number of the connected components minus one. Each values of the map
1.87 - /// will be set exactly once, the values of a certain component will be
1.88 + /// the number of the connected components minus one. Each value of the map
1.89 + /// will be set exactly once, and the values of a certain component will be
1.90 /// set continuously.
1.91 - /// \return The number of components
1.92 + /// \return The number of connected components.
1.93 + /// \note By definition, the empty graph consists
1.94 + /// of zero connected components.
1.95 ///
1.96 + /// \see connected(), countConnectedComponents()
1.97 template <class Graph, class NodeMap>
1.98 int connectedComponents(const Graph &graph, NodeMap &compMap) {
1.99 checkConcept<concepts::Graph, Graph>();
1.100 @@ -227,17 +248,19 @@
1.101 }
1.102
1.103
1.104 - /// \ingroup connectivity
1.105 + /// \ingroup graph_properties
1.106 ///
1.107 - /// \brief Check whether the given directed graph is strongly connected.
1.108 + /// \brief Check whether a directed graph is strongly connected.
1.109 ///
1.110 - /// Check whether the given directed graph is strongly connected. The
1.111 - /// graph is strongly connected when any two nodes of the graph are
1.112 + /// This function checks whether the given directed graph is strongly
1.113 + /// connected, i.e. any two nodes of the digraph are
1.114 /// connected with directed paths in both direction.
1.115 - /// \return %False when the graph is not strongly connected.
1.116 - /// \see connected
1.117 ///
1.118 - /// \note By definition, the empty graph is strongly connected.
1.119 + /// \return \c true if the digraph is strongly connected.
1.120 + /// \note By definition, the empty digraph is strongly connected.
1.121 + ///
1.122 + /// \see countStronglyConnectedComponents(), stronglyConnectedComponents()
1.123 + /// \see connected()
1.124 template <typename Digraph>
1.125 bool stronglyConnected(const Digraph& digraph) {
1.126 checkConcept<concepts::Digraph, Digraph>();
1.127 @@ -268,7 +291,7 @@
1.128 typedef typename RDigraph::NodeIt RNodeIt;
1.129 RDigraph rdigraph(digraph);
1.130
1.131 - typedef DfsVisitor<Digraph> RVisitor;
1.132 + typedef DfsVisitor<RDigraph> RVisitor;
1.133 RVisitor rvisitor;
1.134
1.135 DfsVisit<RDigraph, RVisitor> rdfs(rdigraph, rvisitor);
1.136 @@ -285,20 +308,24 @@
1.137 return true;
1.138 }
1.139
1.140 - /// \ingroup connectivity
1.141 + /// \ingroup graph_properties
1.142 ///
1.143 - /// \brief Count the strongly connected components of a directed graph
1.144 + /// \brief Count the number of strongly connected components of a
1.145 + /// directed graph
1.146 ///
1.147 - /// Count the strongly connected components of a directed graph.
1.148 + /// This function counts the number of strongly connected components of
1.149 + /// the given directed graph.
1.150 + ///
1.151 /// The strongly connected components are the classes of an
1.152 - /// equivalence relation on the nodes of the graph. Two nodes are in
1.153 + /// equivalence relation on the nodes of a digraph. Two nodes are in
1.154 /// the same class if they are connected with directed paths in both
1.155 /// direction.
1.156 ///
1.157 - /// \param digraph The graph.
1.158 - /// \return The number of components
1.159 - /// \note By definition, the empty graph has zero
1.160 + /// \return The number of strongly connected components.
1.161 + /// \note By definition, the empty digraph has zero
1.162 /// strongly connected components.
1.163 + ///
1.164 + /// \see stronglyConnected(), stronglyConnectedComponents()
1.165 template <typename Digraph>
1.166 int countStronglyConnectedComponents(const Digraph& digraph) {
1.167 checkConcept<concepts::Digraph, Digraph>();
1.168 @@ -349,25 +376,33 @@
1.169 return compNum;
1.170 }
1.171
1.172 - /// \ingroup connectivity
1.173 + /// \ingroup graph_properties
1.174 ///
1.175 /// \brief Find the strongly connected components of a directed graph
1.176 ///
1.177 - /// Find the strongly connected components of a directed graph. The
1.178 - /// strongly connected components are the classes of an equivalence
1.179 - /// relation on the nodes of the graph. Two nodes are in
1.180 - /// relationship when there are directed paths between them in both
1.181 - /// direction. In addition, the numbering of components will satisfy
1.182 - /// that there is no arc going from a higher numbered component to
1.183 - /// a lower.
1.184 + /// This function finds the strongly connected components of the given
1.185 + /// directed graph. In addition, the numbering of the components will
1.186 + /// satisfy that there is no arc going from a higher numbered component
1.187 + /// to a lower one (i.e. it provides a topological order of the components).
1.188 + ///
1.189 + /// The strongly connected components are the classes of an
1.190 + /// equivalence relation on the nodes of a digraph. Two nodes are in
1.191 + /// the same class if they are connected with directed paths in both
1.192 + /// direction.
1.193 + ///
1.194 + /// \image html strongly_connected_components.png
1.195 + /// \image latex strongly_connected_components.eps "Strongly connected components" width=\textwidth
1.196 ///
1.197 /// \param digraph The digraph.
1.198 /// \retval compMap A writable node map. The values will be set from 0 to
1.199 /// the number of the strongly connected components minus one. Each value
1.200 - /// of the map will be set exactly once, the values of a certain component
1.201 - /// will be set continuously.
1.202 - /// \return The number of components
1.203 + /// of the map will be set exactly once, and the values of a certain
1.204 + /// component will be set continuously.
1.205 + /// \return The number of strongly connected components.
1.206 + /// \note By definition, the empty digraph has zero
1.207 + /// strongly connected components.
1.208 ///
1.209 + /// \see stronglyConnected(), countStronglyConnectedComponents()
1.210 template <typename Digraph, typename NodeMap>
1.211 int stronglyConnectedComponents(const Digraph& digraph, NodeMap& compMap) {
1.212 checkConcept<concepts::Digraph, Digraph>();
1.213 @@ -416,23 +451,28 @@
1.214 return compNum;
1.215 }
1.216
1.217 - /// \ingroup connectivity
1.218 + /// \ingroup graph_properties
1.219 ///
1.220 /// \brief Find the cut arcs of the strongly connected components.
1.221 ///
1.222 - /// Find the cut arcs of the strongly connected components.
1.223 - /// The strongly connected components are the classes of an equivalence
1.224 - /// relation on the nodes of the graph. Two nodes are in relationship
1.225 - /// when there are directed paths between them in both direction.
1.226 + /// This function finds the cut arcs of the strongly connected components
1.227 + /// of the given digraph.
1.228 + ///
1.229 + /// The strongly connected components are the classes of an
1.230 + /// equivalence relation on the nodes of a digraph. Two nodes are in
1.231 + /// the same class if they are connected with directed paths in both
1.232 + /// direction.
1.233 /// The strongly connected components are separated by the cut arcs.
1.234 ///
1.235 - /// \param graph The graph.
1.236 - /// \retval cutMap A writable node map. The values will be set true when the
1.237 - /// arc is a cut arc.
1.238 + /// \param digraph The digraph.
1.239 + /// \retval cutMap A writable arc map. The values will be set to \c true
1.240 + /// for the cut arcs (exactly once for each cut arc), and will not be
1.241 + /// changed for other arcs.
1.242 + /// \return The number of cut arcs.
1.243 ///
1.244 - /// \return The number of cut arcs
1.245 + /// \see stronglyConnected(), stronglyConnectedComponents()
1.246 template <typename Digraph, typename ArcMap>
1.247 - int stronglyConnectedCutArcs(const Digraph& graph, ArcMap& cutMap) {
1.248 + int stronglyConnectedCutArcs(const Digraph& digraph, ArcMap& cutMap) {
1.249 checkConcept<concepts::Digraph, Digraph>();
1.250 typedef typename Digraph::Node Node;
1.251 typedef typename Digraph::Arc Arc;
1.252 @@ -444,13 +484,13 @@
1.253 typedef std::vector<Node> Container;
1.254 typedef typename Container::iterator Iterator;
1.255
1.256 - Container nodes(countNodes(graph));
1.257 + Container nodes(countNodes(digraph));
1.258 typedef LeaveOrderVisitor<Digraph, Iterator> Visitor;
1.259 Visitor visitor(nodes.begin());
1.260
1.261 - DfsVisit<Digraph, Visitor> dfs(graph, visitor);
1.262 + DfsVisit<Digraph, Visitor> dfs(digraph, visitor);
1.263 dfs.init();
1.264 - for (NodeIt it(graph); it != INVALID; ++it) {
1.265 + for (NodeIt it(digraph); it != INVALID; ++it) {
1.266 if (!dfs.reached(it)) {
1.267 dfs.addSource(it);
1.268 dfs.start();
1.269 @@ -460,14 +500,14 @@
1.270 typedef typename Container::reverse_iterator RIterator;
1.271 typedef ReverseDigraph<const Digraph> RDigraph;
1.272
1.273 - RDigraph rgraph(graph);
1.274 + RDigraph rdigraph(digraph);
1.275
1.276 int cutNum = 0;
1.277
1.278 typedef StronglyConnectedCutArcsVisitor<RDigraph, ArcMap> RVisitor;
1.279 - RVisitor rvisitor(rgraph, cutMap, cutNum);
1.280 + RVisitor rvisitor(rdigraph, cutMap, cutNum);
1.281
1.282 - DfsVisit<RDigraph, RVisitor> rdfs(rgraph, rvisitor);
1.283 + DfsVisit<RDigraph, RVisitor> rdfs(rdigraph, rvisitor);
1.284
1.285 rdfs.init();
1.286 for (RIterator it = nodes.rbegin(); it != nodes.rend(); ++it) {
1.287 @@ -700,32 +740,37 @@
1.288 template <typename Graph>
1.289 int countBiNodeConnectedComponents(const Graph& graph);
1.290
1.291 - /// \ingroup connectivity
1.292 + /// \ingroup graph_properties
1.293 ///
1.294 - /// \brief Checks the graph is bi-node-connected.
1.295 + /// \brief Check whether an undirected graph is bi-node-connected.
1.296 ///
1.297 - /// This function checks that the undirected graph is bi-node-connected
1.298 - /// graph. The graph is bi-node-connected if any two undirected edge is
1.299 - /// on same circle.
1.300 + /// This function checks whether the given undirected graph is
1.301 + /// bi-node-connected, i.e. any two edges are on same circle.
1.302 ///
1.303 - /// \param graph The graph.
1.304 - /// \return %True when the graph bi-node-connected.
1.305 + /// \return \c true if the graph bi-node-connected.
1.306 + /// \note By definition, the empty graph is bi-node-connected.
1.307 + ///
1.308 + /// \see countBiNodeConnectedComponents(), biNodeConnectedComponents()
1.309 template <typename Graph>
1.310 bool biNodeConnected(const Graph& graph) {
1.311 return countBiNodeConnectedComponents(graph) <= 1;
1.312 }
1.313
1.314 - /// \ingroup connectivity
1.315 + /// \ingroup graph_properties
1.316 ///
1.317 - /// \brief Count the biconnected components.
1.318 + /// \brief Count the number of bi-node-connected components of an
1.319 + /// undirected graph.
1.320 ///
1.321 - /// This function finds the bi-node-connected components in an undirected
1.322 - /// graph. The biconnected components are the classes of an equivalence
1.323 - /// relation on the undirected edges. Two undirected edge is in relationship
1.324 - /// when they are on same circle.
1.325 + /// This function counts the number of bi-node-connected components of
1.326 + /// the given undirected graph.
1.327 ///
1.328 - /// \param graph The graph.
1.329 - /// \return The number of components.
1.330 + /// The bi-node-connected components are the classes of an equivalence
1.331 + /// relation on the edges of a undirected graph. Two edges are in the
1.332 + /// same class if they are on same circle.
1.333 + ///
1.334 + /// \return The number of bi-node-connected components.
1.335 + ///
1.336 + /// \see biNodeConnected(), biNodeConnectedComponents()
1.337 template <typename Graph>
1.338 int countBiNodeConnectedComponents(const Graph& graph) {
1.339 checkConcept<concepts::Graph, Graph>();
1.340 @@ -750,22 +795,28 @@
1.341 return compNum;
1.342 }
1.343
1.344 - /// \ingroup connectivity
1.345 + /// \ingroup graph_properties
1.346 ///
1.347 - /// \brief Find the bi-node-connected components.
1.348 + /// \brief Find the bi-node-connected components of an undirected graph.
1.349 ///
1.350 - /// This function finds the bi-node-connected components in an undirected
1.351 - /// graph. The bi-node-connected components are the classes of an equivalence
1.352 - /// relation on the undirected edges. Two undirected edge are in relationship
1.353 - /// when they are on same circle.
1.354 + /// This function finds the bi-node-connected components of the given
1.355 + /// undirected graph.
1.356 ///
1.357 - /// \param graph The graph.
1.358 - /// \retval compMap A writable uedge map. The values will be set from 0
1.359 - /// to the number of the biconnected components minus one. Each values
1.360 - /// of the map will be set exactly once, the values of a certain component
1.361 - /// will be set continuously.
1.362 - /// \return The number of components.
1.363 + /// The bi-node-connected components are the classes of an equivalence
1.364 + /// relation on the edges of a undirected graph. Two edges are in the
1.365 + /// same class if they are on same circle.
1.366 ///
1.367 + /// \image html node_biconnected_components.png
1.368 + /// \image latex node_biconnected_components.eps "bi-node-connected components" width=\textwidth
1.369 + ///
1.370 + /// \param graph The undirected graph.
1.371 + /// \retval compMap A writable edge map. The values will be set from 0
1.372 + /// to the number of the bi-node-connected components minus one. Each
1.373 + /// value of the map will be set exactly once, and the values of a
1.374 + /// certain component will be set continuously.
1.375 + /// \return The number of bi-node-connected components.
1.376 + ///
1.377 + /// \see biNodeConnected(), countBiNodeConnectedComponents()
1.378 template <typename Graph, typename EdgeMap>
1.379 int biNodeConnectedComponents(const Graph& graph,
1.380 EdgeMap& compMap) {
1.381 @@ -793,20 +844,27 @@
1.382 return compNum;
1.383 }
1.384
1.385 - /// \ingroup connectivity
1.386 + /// \ingroup graph_properties
1.387 ///
1.388 - /// \brief Find the bi-node-connected cut nodes.
1.389 + /// \brief Find the bi-node-connected cut nodes in an undirected graph.
1.390 ///
1.391 - /// This function finds the bi-node-connected cut nodes in an undirected
1.392 - /// graph. The bi-node-connected components are the classes of an equivalence
1.393 - /// relation on the undirected edges. Two undirected edges are in
1.394 - /// relationship when they are on same circle. The biconnected components
1.395 - /// are separted by nodes which are the cut nodes of the components.
1.396 + /// This function finds the bi-node-connected cut nodes in the given
1.397 + /// undirected graph.
1.398 ///
1.399 - /// \param graph The graph.
1.400 - /// \retval cutMap A writable edge map. The values will be set true when
1.401 - /// the node separate two or more components.
1.402 + /// The bi-node-connected components are the classes of an equivalence
1.403 + /// relation on the edges of a undirected graph. Two edges are in the
1.404 + /// same class if they are on same circle.
1.405 + /// The bi-node-connected components are separted by the cut nodes of
1.406 + /// the components.
1.407 + ///
1.408 + /// \param graph The undirected graph.
1.409 + /// \retval cutMap A writable node map. The values will be set to
1.410 + /// \c true for the nodes that separate two or more components
1.411 + /// (exactly once for each cut node), and will not be changed for
1.412 + /// other nodes.
1.413 /// \return The number of the cut nodes.
1.414 + ///
1.415 + /// \see biNodeConnected(), biNodeConnectedComponents()
1.416 template <typename Graph, typename NodeMap>
1.417 int biNodeConnectedCutNodes(const Graph& graph, NodeMap& cutMap) {
1.418 checkConcept<concepts::Graph, Graph>();
1.419 @@ -1023,32 +1081,39 @@
1.420 template <typename Graph>
1.421 int countBiEdgeConnectedComponents(const Graph& graph);
1.422
1.423 - /// \ingroup connectivity
1.424 + /// \ingroup graph_properties
1.425 ///
1.426 - /// \brief Checks that the graph is bi-edge-connected.
1.427 + /// \brief Check whether an undirected graph is bi-edge-connected.
1.428 ///
1.429 - /// This function checks that the graph is bi-edge-connected. The undirected
1.430 - /// graph is bi-edge-connected when any two nodes are connected with two
1.431 - /// edge-disjoint paths.
1.432 + /// This function checks whether the given undirected graph is
1.433 + /// bi-edge-connected, i.e. any two nodes are connected with at least
1.434 + /// two edge-disjoint paths.
1.435 ///
1.436 - /// \param graph The undirected graph.
1.437 - /// \return The number of components.
1.438 + /// \return \c true if the graph is bi-edge-connected.
1.439 + /// \note By definition, the empty graph is bi-edge-connected.
1.440 + ///
1.441 + /// \see countBiEdgeConnectedComponents(), biEdgeConnectedComponents()
1.442 template <typename Graph>
1.443 bool biEdgeConnected(const Graph& graph) {
1.444 return countBiEdgeConnectedComponents(graph) <= 1;
1.445 }
1.446
1.447 - /// \ingroup connectivity
1.448 + /// \ingroup graph_properties
1.449 ///
1.450 - /// \brief Count the bi-edge-connected components.
1.451 + /// \brief Count the number of bi-edge-connected components of an
1.452 + /// undirected graph.
1.453 ///
1.454 - /// This function count the bi-edge-connected components in an undirected
1.455 - /// graph. The bi-edge-connected components are the classes of an equivalence
1.456 - /// relation on the nodes. Two nodes are in relationship when they are
1.457 - /// connected with at least two edge-disjoint paths.
1.458 + /// This function counts the number of bi-edge-connected components of
1.459 + /// the given undirected graph.
1.460 ///
1.461 - /// \param graph The undirected graph.
1.462 - /// \return The number of components.
1.463 + /// The bi-edge-connected components are the classes of an equivalence
1.464 + /// relation on the nodes of an undirected graph. Two nodes are in the
1.465 + /// same class if they are connected with at least two edge-disjoint
1.466 + /// paths.
1.467 + ///
1.468 + /// \return The number of bi-edge-connected components.
1.469 + ///
1.470 + /// \see biEdgeConnected(), biEdgeConnectedComponents()
1.471 template <typename Graph>
1.472 int countBiEdgeConnectedComponents(const Graph& graph) {
1.473 checkConcept<concepts::Graph, Graph>();
1.474 @@ -1073,22 +1138,29 @@
1.475 return compNum;
1.476 }
1.477
1.478 - /// \ingroup connectivity
1.479 + /// \ingroup graph_properties
1.480 ///
1.481 - /// \brief Find the bi-edge-connected components.
1.482 + /// \brief Find the bi-edge-connected components of an undirected graph.
1.483 ///
1.484 - /// This function finds the bi-edge-connected components in an undirected
1.485 - /// graph. The bi-edge-connected components are the classes of an equivalence
1.486 - /// relation on the nodes. Two nodes are in relationship when they are
1.487 - /// connected at least two edge-disjoint paths.
1.488 + /// This function finds the bi-edge-connected components of the given
1.489 + /// undirected graph.
1.490 ///
1.491 - /// \param graph The graph.
1.492 + /// The bi-edge-connected components are the classes of an equivalence
1.493 + /// relation on the nodes of an undirected graph. Two nodes are in the
1.494 + /// same class if they are connected with at least two edge-disjoint
1.495 + /// paths.
1.496 + ///
1.497 + /// \image html edge_biconnected_components.png
1.498 + /// \image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth
1.499 + ///
1.500 + /// \param graph The undirected graph.
1.501 /// \retval compMap A writable node map. The values will be set from 0 to
1.502 - /// the number of the biconnected components minus one. Each values
1.503 - /// of the map will be set exactly once, the values of a certain component
1.504 - /// will be set continuously.
1.505 - /// \return The number of components.
1.506 + /// the number of the bi-edge-connected components minus one. Each value
1.507 + /// of the map will be set exactly once, and the values of a certain
1.508 + /// component will be set continuously.
1.509 + /// \return The number of bi-edge-connected components.
1.510 ///
1.511 + /// \see biEdgeConnected(), countBiEdgeConnectedComponents()
1.512 template <typename Graph, typename NodeMap>
1.513 int biEdgeConnectedComponents(const Graph& graph, NodeMap& compMap) {
1.514 checkConcept<concepts::Graph, Graph>();
1.515 @@ -1115,21 +1187,27 @@
1.516 return compNum;
1.517 }
1.518
1.519 - /// \ingroup connectivity
1.520 + /// \ingroup graph_properties
1.521 ///
1.522 - /// \brief Find the bi-edge-connected cut edges.
1.523 + /// \brief Find the bi-edge-connected cut edges in an undirected graph.
1.524 ///
1.525 - /// This function finds the bi-edge-connected components in an undirected
1.526 - /// graph. The bi-edge-connected components are the classes of an equivalence
1.527 - /// relation on the nodes. Two nodes are in relationship when they are
1.528 - /// connected with at least two edge-disjoint paths. The bi-edge-connected
1.529 - /// components are separted by edges which are the cut edges of the
1.530 - /// components.
1.531 + /// This function finds the bi-edge-connected cut edges in the given
1.532 + /// undirected graph.
1.533 ///
1.534 - /// \param graph The graph.
1.535 - /// \retval cutMap A writable node map. The values will be set true when the
1.536 - /// edge is a cut edge.
1.537 + /// The bi-edge-connected components are the classes of an equivalence
1.538 + /// relation on the nodes of an undirected graph. Two nodes are in the
1.539 + /// same class if they are connected with at least two edge-disjoint
1.540 + /// paths.
1.541 + /// The bi-edge-connected components are separted by the cut edges of
1.542 + /// the components.
1.543 + ///
1.544 + /// \param graph The undirected graph.
1.545 + /// \retval cutMap A writable edge map. The values will be set to \c true
1.546 + /// for the cut edges (exactly once for each cut edge), and will not be
1.547 + /// changed for other edges.
1.548 /// \return The number of cut edges.
1.549 + ///
1.550 + /// \see biEdgeConnected(), biEdgeConnectedComponents()
1.551 template <typename Graph, typename EdgeMap>
1.552 int biEdgeConnectedCutEdges(const Graph& graph, EdgeMap& cutMap) {
1.553 checkConcept<concepts::Graph, Graph>();
1.554 @@ -1179,21 +1257,64 @@
1.555
1.556 }
1.557
1.558 - /// \ingroup connectivity
1.559 + /// \ingroup graph_properties
1.560 + ///
1.561 + /// \brief Check whether a digraph is DAG.
1.562 + ///
1.563 + /// This function checks whether the given digraph is DAG, i.e.
1.564 + /// \e Directed \e Acyclic \e Graph.
1.565 + /// \return \c true if there is no directed cycle in the digraph.
1.566 + /// \see acyclic()
1.567 + template <typename Digraph>
1.568 + bool dag(const Digraph& digraph) {
1.569 +
1.570 + checkConcept<concepts::Digraph, Digraph>();
1.571 +
1.572 + typedef typename Digraph::Node Node;
1.573 + typedef typename Digraph::NodeIt NodeIt;
1.574 + typedef typename Digraph::Arc Arc;
1.575 +
1.576 + typedef typename Digraph::template NodeMap<bool> ProcessedMap;
1.577 +
1.578 + typename Dfs<Digraph>::template SetProcessedMap<ProcessedMap>::
1.579 + Create dfs(digraph);
1.580 +
1.581 + ProcessedMap processed(digraph);
1.582 + dfs.processedMap(processed);
1.583 +
1.584 + dfs.init();
1.585 + for (NodeIt it(digraph); it != INVALID; ++it) {
1.586 + if (!dfs.reached(it)) {
1.587 + dfs.addSource(it);
1.588 + while (!dfs.emptyQueue()) {
1.589 + Arc arc = dfs.nextArc();
1.590 + Node target = digraph.target(arc);
1.591 + if (dfs.reached(target) && !processed[target]) {
1.592 + return false;
1.593 + }
1.594 + dfs.processNextArc();
1.595 + }
1.596 + }
1.597 + }
1.598 + return true;
1.599 + }
1.600 +
1.601 + /// \ingroup graph_properties
1.602 ///
1.603 /// \brief Sort the nodes of a DAG into topolgical order.
1.604 ///
1.605 - /// Sort the nodes of a DAG into topolgical order.
1.606 + /// This function sorts the nodes of the given acyclic digraph (DAG)
1.607 + /// into topolgical order.
1.608 ///
1.609 - /// \param graph The graph. It must be directed and acyclic.
1.610 + /// \param digraph The digraph, which must be DAG.
1.611 /// \retval order A writable node map. The values will be set from 0 to
1.612 - /// the number of the nodes in the graph minus one. Each values of the map
1.613 - /// will be set exactly once, the values will be set descending order.
1.614 + /// the number of the nodes in the digraph minus one. Each value of the
1.615 + /// map will be set exactly once, and the values will be set descending
1.616 + /// order.
1.617 ///
1.618 - /// \see checkedTopologicalSort
1.619 - /// \see dag
1.620 + /// \see dag(), checkedTopologicalSort()
1.621 template <typename Digraph, typename NodeMap>
1.622 - void topologicalSort(const Digraph& graph, NodeMap& order) {
1.623 + void topologicalSort(const Digraph& digraph, NodeMap& order) {
1.624 using namespace _connectivity_bits;
1.625
1.626 checkConcept<concepts::Digraph, Digraph>();
1.627 @@ -1204,13 +1325,13 @@
1.628 typedef typename Digraph::Arc Arc;
1.629
1.630 TopologicalSortVisitor<Digraph, NodeMap>
1.631 - visitor(order, countNodes(graph));
1.632 + visitor(order, countNodes(digraph));
1.633
1.634 DfsVisit<Digraph, TopologicalSortVisitor<Digraph, NodeMap> >
1.635 - dfs(graph, visitor);
1.636 + dfs(digraph, visitor);
1.637
1.638 dfs.init();
1.639 - for (NodeIt it(graph); it != INVALID; ++it) {
1.640 + for (NodeIt it(digraph); it != INVALID; ++it) {
1.641 if (!dfs.reached(it)) {
1.642 dfs.addSource(it);
1.643 dfs.start();
1.644 @@ -1218,22 +1339,22 @@
1.645 }
1.646 }
1.647
1.648 - /// \ingroup connectivity
1.649 + /// \ingroup graph_properties
1.650 ///
1.651 /// \brief Sort the nodes of a DAG into topolgical order.
1.652 ///
1.653 - /// Sort the nodes of a DAG into topolgical order. It also checks
1.654 - /// that the given graph is DAG.
1.655 + /// This function sorts the nodes of the given acyclic digraph (DAG)
1.656 + /// into topolgical order and also checks whether the given digraph
1.657 + /// is DAG.
1.658 ///
1.659 - /// \param digraph The graph. It must be directed and acyclic.
1.660 - /// \retval order A readable - writable node map. The values will be set
1.661 - /// from 0 to the number of the nodes in the graph minus one. Each values
1.662 - /// of the map will be set exactly once, the values will be set descending
1.663 - /// order.
1.664 - /// \return %False when the graph is not DAG.
1.665 + /// \param digraph The digraph.
1.666 + /// \retval order A readable and writable node map. The values will be
1.667 + /// set from 0 to the number of the nodes in the digraph minus one.
1.668 + /// Each value of the map will be set exactly once, and the values will
1.669 + /// be set descending order.
1.670 + /// \return \c false if the digraph is not DAG.
1.671 ///
1.672 - /// \see topologicalSort
1.673 - /// \see dag
1.674 + /// \see dag(), topologicalSort()
1.675 template <typename Digraph, typename NodeMap>
1.676 bool checkedTopologicalSort(const Digraph& digraph, NodeMap& order) {
1.677 using namespace _connectivity_bits;
1.678 @@ -1273,56 +1394,13 @@
1.679 return true;
1.680 }
1.681
1.682 - /// \ingroup connectivity
1.683 + /// \ingroup graph_properties
1.684 ///
1.685 - /// \brief Check that the given directed graph is a DAG.
1.686 + /// \brief Check whether an undirected graph is acyclic.
1.687 ///
1.688 - /// Check that the given directed graph is a DAG. The DAG is
1.689 - /// an Directed Acyclic Digraph.
1.690 - /// \return %False when the graph is not DAG.
1.691 - /// \see acyclic
1.692 - template <typename Digraph>
1.693 - bool dag(const Digraph& digraph) {
1.694 -
1.695 - checkConcept<concepts::Digraph, Digraph>();
1.696 -
1.697 - typedef typename Digraph::Node Node;
1.698 - typedef typename Digraph::NodeIt NodeIt;
1.699 - typedef typename Digraph::Arc Arc;
1.700 -
1.701 - typedef typename Digraph::template NodeMap<bool> ProcessedMap;
1.702 -
1.703 - typename Dfs<Digraph>::template SetProcessedMap<ProcessedMap>::
1.704 - Create dfs(digraph);
1.705 -
1.706 - ProcessedMap processed(digraph);
1.707 - dfs.processedMap(processed);
1.708 -
1.709 - dfs.init();
1.710 - for (NodeIt it(digraph); it != INVALID; ++it) {
1.711 - if (!dfs.reached(it)) {
1.712 - dfs.addSource(it);
1.713 - while (!dfs.emptyQueue()) {
1.714 - Arc edge = dfs.nextArc();
1.715 - Node target = digraph.target(edge);
1.716 - if (dfs.reached(target) && !processed[target]) {
1.717 - return false;
1.718 - }
1.719 - dfs.processNextArc();
1.720 - }
1.721 - }
1.722 - }
1.723 - return true;
1.724 - }
1.725 -
1.726 - /// \ingroup connectivity
1.727 - ///
1.728 - /// \brief Check that the given undirected graph is acyclic.
1.729 - ///
1.730 - /// Check that the given undirected graph acyclic.
1.731 - /// \param graph The undirected graph.
1.732 - /// \return %True when there is no circle in the graph.
1.733 - /// \see dag
1.734 + /// This function checks whether the given undirected graph is acyclic.
1.735 + /// \return \c true if there is no cycle in the graph.
1.736 + /// \see dag()
1.737 template <typename Graph>
1.738 bool acyclic(const Graph& graph) {
1.739 checkConcept<concepts::Graph, Graph>();
1.740 @@ -1335,11 +1413,11 @@
1.741 if (!dfs.reached(it)) {
1.742 dfs.addSource(it);
1.743 while (!dfs.emptyQueue()) {
1.744 - Arc edge = dfs.nextArc();
1.745 - Node source = graph.source(edge);
1.746 - Node target = graph.target(edge);
1.747 + Arc arc = dfs.nextArc();
1.748 + Node source = graph.source(arc);
1.749 + Node target = graph.target(arc);
1.750 if (dfs.reached(target) &&
1.751 - dfs.predArc(source) != graph.oppositeArc(edge)) {
1.752 + dfs.predArc(source) != graph.oppositeArc(arc)) {
1.753 return false;
1.754 }
1.755 dfs.processNextArc();
1.756 @@ -1349,28 +1427,29 @@
1.757 return true;
1.758 }
1.759
1.760 - /// \ingroup connectivity
1.761 + /// \ingroup graph_properties
1.762 ///
1.763 - /// \brief Check that the given undirected graph is tree.
1.764 + /// \brief Check whether an undirected graph is tree.
1.765 ///
1.766 - /// Check that the given undirected graph is tree.
1.767 - /// \param graph The undirected graph.
1.768 - /// \return %True when the graph is acyclic and connected.
1.769 + /// This function checks whether the given undirected graph is tree.
1.770 + /// \return \c true if the graph is acyclic and connected.
1.771 + /// \see acyclic(), connected()
1.772 template <typename Graph>
1.773 bool tree(const Graph& graph) {
1.774 checkConcept<concepts::Graph, Graph>();
1.775 typedef typename Graph::Node Node;
1.776 typedef typename Graph::NodeIt NodeIt;
1.777 typedef typename Graph::Arc Arc;
1.778 + if (NodeIt(graph) == INVALID) return true;
1.779 Dfs<Graph> dfs(graph);
1.780 dfs.init();
1.781 dfs.addSource(NodeIt(graph));
1.782 while (!dfs.emptyQueue()) {
1.783 - Arc edge = dfs.nextArc();
1.784 - Node source = graph.source(edge);
1.785 - Node target = graph.target(edge);
1.786 + Arc arc = dfs.nextArc();
1.787 + Node source = graph.source(arc);
1.788 + Node target = graph.target(arc);
1.789 if (dfs.reached(target) &&
1.790 - dfs.predArc(source) != graph.oppositeArc(edge)) {
1.791 + dfs.predArc(source) != graph.oppositeArc(arc)) {
1.792 return false;
1.793 }
1.794 dfs.processNextArc();
1.795 @@ -1441,17 +1520,16 @@
1.796 };
1.797 }
1.798
1.799 - /// \ingroup connectivity
1.800 + /// \ingroup graph_properties
1.801 ///
1.802 - /// \brief Check if the given undirected graph is bipartite or not
1.803 + /// \brief Check whether an undirected graph is bipartite.
1.804 ///
1.805 - /// The function checks if the given undirected \c graph graph is bipartite
1.806 - /// or not. The \ref Bfs algorithm is used to calculate the result.
1.807 - /// \param graph The undirected graph.
1.808 - /// \return %True if \c graph is bipartite, %false otherwise.
1.809 - /// \sa bipartitePartitions
1.810 + /// The function checks whether the given undirected graph is bipartite.
1.811 + /// \return \c true if the graph is bipartite.
1.812 + ///
1.813 + /// \see bipartitePartitions()
1.814 template<typename Graph>
1.815 - inline bool bipartite(const Graph &graph){
1.816 + bool bipartite(const Graph &graph){
1.817 using namespace _connectivity_bits;
1.818
1.819 checkConcept<concepts::Graph, Graph>();
1.820 @@ -1478,23 +1556,29 @@
1.821 return true;
1.822 }
1.823
1.824 - /// \ingroup connectivity
1.825 + /// \ingroup graph_properties
1.826 ///
1.827 - /// \brief Check if the given undirected graph is bipartite or not
1.828 + /// \brief Find the bipartite partitions of an undirected graph.
1.829 ///
1.830 - /// The function checks if the given undirected graph is bipartite
1.831 - /// or not. The \ref Bfs algorithm is used to calculate the result.
1.832 - /// During the execution, the \c partMap will be set as the two
1.833 - /// partitions of the graph.
1.834 + /// This function checks whether the given undirected graph is bipartite
1.835 + /// and gives back the bipartite partitions.
1.836 + ///
1.837 + /// \image html bipartite_partitions.png
1.838 + /// \image latex bipartite_partitions.eps "Bipartite partititions" width=\textwidth
1.839 + ///
1.840 /// \param graph The undirected graph.
1.841 - /// \retval partMap A writable bool map of nodes. It will be set as the
1.842 - /// two partitions of the graph.
1.843 - /// \return %True if \c graph is bipartite, %false otherwise.
1.844 + /// \retval partMap A writable node map of \c bool (or convertible) value
1.845 + /// type. The values will be set to \c true for one component and
1.846 + /// \c false for the other one.
1.847 + /// \return \c true if the graph is bipartite, \c false otherwise.
1.848 + ///
1.849 + /// \see bipartite()
1.850 template<typename Graph, typename NodeMap>
1.851 - inline bool bipartitePartitions(const Graph &graph, NodeMap &partMap){
1.852 + bool bipartitePartitions(const Graph &graph, NodeMap &partMap){
1.853 using namespace _connectivity_bits;
1.854
1.855 checkConcept<concepts::Graph, Graph>();
1.856 + checkConcept<concepts::WriteMap<typename Graph::Node, bool>, NodeMap>();
1.857
1.858 typedef typename Graph::Node Node;
1.859 typedef typename Graph::NodeIt NodeIt;
1.860 @@ -1519,53 +1603,59 @@
1.861 return true;
1.862 }
1.863
1.864 - /// \brief Returns true when there are not loop edges in the graph.
1.865 + /// \ingroup graph_properties
1.866 ///
1.867 - /// Returns true when there are not loop edges in the graph.
1.868 - template <typename Digraph>
1.869 - bool loopFree(const Digraph& digraph) {
1.870 - for (typename Digraph::ArcIt it(digraph); it != INVALID; ++it) {
1.871 - if (digraph.source(it) == digraph.target(it)) return false;
1.872 + /// \brief Check whether the given graph contains no loop arcs/edges.
1.873 + ///
1.874 + /// This function returns \c true if there are no loop arcs/edges in
1.875 + /// the given graph. It works for both directed and undirected graphs.
1.876 + template <typename Graph>
1.877 + bool loopFree(const Graph& graph) {
1.878 + for (typename Graph::ArcIt it(graph); it != INVALID; ++it) {
1.879 + if (graph.source(it) == graph.target(it)) return false;
1.880 }
1.881 return true;
1.882 }
1.883
1.884 - /// \brief Returns true when there are not parallel edges in the graph.
1.885 + /// \ingroup graph_properties
1.886 ///
1.887 - /// Returns true when there are not parallel edges in the graph.
1.888 - template <typename Digraph>
1.889 - bool parallelFree(const Digraph& digraph) {
1.890 - typename Digraph::template NodeMap<bool> reached(digraph, false);
1.891 - for (typename Digraph::NodeIt n(digraph); n != INVALID; ++n) {
1.892 - for (typename Digraph::OutArcIt a(digraph, n); a != INVALID; ++a) {
1.893 - if (reached[digraph.target(a)]) return false;
1.894 - reached.set(digraph.target(a), true);
1.895 + /// \brief Check whether the given graph contains no parallel arcs/edges.
1.896 + ///
1.897 + /// This function returns \c true if there are no parallel arcs/edges in
1.898 + /// the given graph. It works for both directed and undirected graphs.
1.899 + template <typename Graph>
1.900 + bool parallelFree(const Graph& graph) {
1.901 + typename Graph::template NodeMap<int> reached(graph, 0);
1.902 + int cnt = 1;
1.903 + for (typename Graph::NodeIt n(graph); n != INVALID; ++n) {
1.904 + for (typename Graph::OutArcIt a(graph, n); a != INVALID; ++a) {
1.905 + if (reached[graph.target(a)] == cnt) return false;
1.906 + reached[graph.target(a)] = cnt;
1.907 }
1.908 - for (typename Digraph::OutArcIt a(digraph, n); a != INVALID; ++a) {
1.909 - reached.set(digraph.target(a), false);
1.910 - }
1.911 + ++cnt;
1.912 }
1.913 return true;
1.914 }
1.915
1.916 - /// \brief Returns true when there are not loop edges and parallel
1.917 - /// edges in the graph.
1.918 + /// \ingroup graph_properties
1.919 ///
1.920 - /// Returns true when there are not loop edges and parallel edges in
1.921 - /// the graph.
1.922 - template <typename Digraph>
1.923 - bool simpleDigraph(const Digraph& digraph) {
1.924 - typename Digraph::template NodeMap<bool> reached(digraph, false);
1.925 - for (typename Digraph::NodeIt n(digraph); n != INVALID; ++n) {
1.926 - reached.set(n, true);
1.927 - for (typename Digraph::OutArcIt a(digraph, n); a != INVALID; ++a) {
1.928 - if (reached[digraph.target(a)]) return false;
1.929 - reached.set(digraph.target(a), true);
1.930 + /// \brief Check whether the given graph is simple.
1.931 + ///
1.932 + /// This function returns \c true if the given graph is simple, i.e.
1.933 + /// it contains no loop arcs/edges and no parallel arcs/edges.
1.934 + /// The function works for both directed and undirected graphs.
1.935 + /// \see loopFree(), parallelFree()
1.936 + template <typename Graph>
1.937 + bool simpleGraph(const Graph& graph) {
1.938 + typename Graph::template NodeMap<int> reached(graph, 0);
1.939 + int cnt = 1;
1.940 + for (typename Graph::NodeIt n(graph); n != INVALID; ++n) {
1.941 + reached[n] = cnt;
1.942 + for (typename Graph::OutArcIt a(graph, n); a != INVALID; ++a) {
1.943 + if (reached[graph.target(a)] == cnt) return false;
1.944 + reached[graph.target(a)] = cnt;
1.945 }
1.946 - for (typename Digraph::OutArcIt a(digraph, n); a != INVALID; ++a) {
1.947 - reached.set(digraph.target(a), false);
1.948 - }
1.949 - reached.set(n, false);
1.950 + ++cnt;
1.951 }
1.952 return true;
1.953 }