1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/lemon/connectivity.h Thu Nov 05 15:50:01 2009 +0100
1.3 @@ -0,0 +1,1665 @@
1.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
1.5 + *
1.6 + * This file is a part of LEMON, a generic C++ optimization library.
1.7 + *
1.8 + * Copyright (C) 2003-2009
1.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.11 + *
1.12 + * Permission to use, modify and distribute this software is granted
1.13 + * provided that this copyright notice appears in all copies. For
1.14 + * precise terms see the accompanying LICENSE file.
1.15 + *
1.16 + * This software is provided "AS IS" with no warranty of any kind,
1.17 + * express or implied, and with no claim as to its suitability for any
1.18 + * purpose.
1.19 + *
1.20 + */
1.21 +
1.22 +#ifndef LEMON_CONNECTIVITY_H
1.23 +#define LEMON_CONNECTIVITY_H
1.24 +
1.25 +#include <lemon/dfs.h>
1.26 +#include <lemon/bfs.h>
1.27 +#include <lemon/core.h>
1.28 +#include <lemon/maps.h>
1.29 +#include <lemon/adaptors.h>
1.30 +
1.31 +#include <lemon/concepts/digraph.h>
1.32 +#include <lemon/concepts/graph.h>
1.33 +#include <lemon/concept_check.h>
1.34 +
1.35 +#include <stack>
1.36 +#include <functional>
1.37 +
1.38 +/// \ingroup graph_properties
1.39 +/// \file
1.40 +/// \brief Connectivity algorithms
1.41 +///
1.42 +/// Connectivity algorithms
1.43 +
1.44 +namespace lemon {
1.45 +
1.46 + /// \ingroup graph_properties
1.47 + ///
1.48 + /// \brief Check whether an undirected graph is connected.
1.49 + ///
1.50 + /// This function checks whether the given undirected graph is connected,
1.51 + /// i.e. there is a path between any two nodes in the graph.
1.52 + ///
1.53 + /// \return \c true if the graph is connected.
1.54 + /// \note By definition, the empty graph is connected.
1.55 + ///
1.56 + /// \see countConnectedComponents(), connectedComponents()
1.57 + /// \see stronglyConnected()
1.58 + template <typename Graph>
1.59 + bool connected(const Graph& graph) {
1.60 + checkConcept<concepts::Graph, Graph>();
1.61 + typedef typename Graph::NodeIt NodeIt;
1.62 + if (NodeIt(graph) == INVALID) return true;
1.63 + Dfs<Graph> dfs(graph);
1.64 + dfs.run(NodeIt(graph));
1.65 + for (NodeIt it(graph); it != INVALID; ++it) {
1.66 + if (!dfs.reached(it)) {
1.67 + return false;
1.68 + }
1.69 + }
1.70 + return true;
1.71 + }
1.72 +
1.73 + /// \ingroup graph_properties
1.74 + ///
1.75 + /// \brief Count the number of connected components of an undirected graph
1.76 + ///
1.77 + /// This function counts the number of connected components of the given
1.78 + /// undirected graph.
1.79 + ///
1.80 + /// The connected components are the classes of an equivalence relation
1.81 + /// on the nodes of an undirected graph. Two nodes are in the same class
1.82 + /// if they are connected with a path.
1.83 + ///
1.84 + /// \return The number of connected components.
1.85 + /// \note By definition, the empty graph consists
1.86 + /// of zero connected components.
1.87 + ///
1.88 + /// \see connected(), connectedComponents()
1.89 + template <typename Graph>
1.90 + int countConnectedComponents(const Graph &graph) {
1.91 + checkConcept<concepts::Graph, Graph>();
1.92 + typedef typename Graph::Node Node;
1.93 + typedef typename Graph::Arc Arc;
1.94 +
1.95 + typedef NullMap<Node, Arc> PredMap;
1.96 + typedef NullMap<Node, int> DistMap;
1.97 +
1.98 + int compNum = 0;
1.99 + typename Bfs<Graph>::
1.100 + template SetPredMap<PredMap>::
1.101 + template SetDistMap<DistMap>::
1.102 + Create bfs(graph);
1.103 +
1.104 + PredMap predMap;
1.105 + bfs.predMap(predMap);
1.106 +
1.107 + DistMap distMap;
1.108 + bfs.distMap(distMap);
1.109 +
1.110 + bfs.init();
1.111 + for(typename Graph::NodeIt n(graph); n != INVALID; ++n) {
1.112 + if (!bfs.reached(n)) {
1.113 + bfs.addSource(n);
1.114 + bfs.start();
1.115 + ++compNum;
1.116 + }
1.117 + }
1.118 + return compNum;
1.119 + }
1.120 +
1.121 + /// \ingroup graph_properties
1.122 + ///
1.123 + /// \brief Find the connected components of an undirected graph
1.124 + ///
1.125 + /// This function finds the connected components of the given undirected
1.126 + /// graph.
1.127 + ///
1.128 + /// The connected components are the classes of an equivalence relation
1.129 + /// on the nodes of an undirected graph. Two nodes are in the same class
1.130 + /// if they are connected with a path.
1.131 + ///
1.132 + /// \image html connected_components.png
1.133 + /// \image latex connected_components.eps "Connected components" width=\textwidth
1.134 + ///
1.135 + /// \param graph The undirected graph.
1.136 + /// \retval compMap A writable node map. The values will be set from 0 to
1.137 + /// the number of the connected components minus one. Each value of the map
1.138 + /// will be set exactly once, and the values of a certain component will be
1.139 + /// set continuously.
1.140 + /// \return The number of connected components.
1.141 + /// \note By definition, the empty graph consists
1.142 + /// of zero connected components.
1.143 + ///
1.144 + /// \see connected(), countConnectedComponents()
1.145 + template <class Graph, class NodeMap>
1.146 + int connectedComponents(const Graph &graph, NodeMap &compMap) {
1.147 + checkConcept<concepts::Graph, Graph>();
1.148 + typedef typename Graph::Node Node;
1.149 + typedef typename Graph::Arc Arc;
1.150 + checkConcept<concepts::WriteMap<Node, int>, NodeMap>();
1.151 +
1.152 + typedef NullMap<Node, Arc> PredMap;
1.153 + typedef NullMap<Node, int> DistMap;
1.154 +
1.155 + int compNum = 0;
1.156 + typename Bfs<Graph>::
1.157 + template SetPredMap<PredMap>::
1.158 + template SetDistMap<DistMap>::
1.159 + Create bfs(graph);
1.160 +
1.161 + PredMap predMap;
1.162 + bfs.predMap(predMap);
1.163 +
1.164 + DistMap distMap;
1.165 + bfs.distMap(distMap);
1.166 +
1.167 + bfs.init();
1.168 + for(typename Graph::NodeIt n(graph); n != INVALID; ++n) {
1.169 + if(!bfs.reached(n)) {
1.170 + bfs.addSource(n);
1.171 + while (!bfs.emptyQueue()) {
1.172 + compMap.set(bfs.nextNode(), compNum);
1.173 + bfs.processNextNode();
1.174 + }
1.175 + ++compNum;
1.176 + }
1.177 + }
1.178 + return compNum;
1.179 + }
1.180 +
1.181 + namespace _connectivity_bits {
1.182 +
1.183 + template <typename Digraph, typename Iterator >
1.184 + struct LeaveOrderVisitor : public DfsVisitor<Digraph> {
1.185 + public:
1.186 + typedef typename Digraph::Node Node;
1.187 + LeaveOrderVisitor(Iterator it) : _it(it) {}
1.188 +
1.189 + void leave(const Node& node) {
1.190 + *(_it++) = node;
1.191 + }
1.192 +
1.193 + private:
1.194 + Iterator _it;
1.195 + };
1.196 +
1.197 + template <typename Digraph, typename Map>
1.198 + struct FillMapVisitor : public DfsVisitor<Digraph> {
1.199 + public:
1.200 + typedef typename Digraph::Node Node;
1.201 + typedef typename Map::Value Value;
1.202 +
1.203 + FillMapVisitor(Map& map, Value& value)
1.204 + : _map(map), _value(value) {}
1.205 +
1.206 + void reach(const Node& node) {
1.207 + _map.set(node, _value);
1.208 + }
1.209 + private:
1.210 + Map& _map;
1.211 + Value& _value;
1.212 + };
1.213 +
1.214 + template <typename Digraph, typename ArcMap>
1.215 + struct StronglyConnectedCutArcsVisitor : public DfsVisitor<Digraph> {
1.216 + public:
1.217 + typedef typename Digraph::Node Node;
1.218 + typedef typename Digraph::Arc Arc;
1.219 +
1.220 + StronglyConnectedCutArcsVisitor(const Digraph& digraph,
1.221 + ArcMap& cutMap,
1.222 + int& cutNum)
1.223 + : _digraph(digraph), _cutMap(cutMap), _cutNum(cutNum),
1.224 + _compMap(digraph, -1), _num(-1) {
1.225 + }
1.226 +
1.227 + void start(const Node&) {
1.228 + ++_num;
1.229 + }
1.230 +
1.231 + void reach(const Node& node) {
1.232 + _compMap.set(node, _num);
1.233 + }
1.234 +
1.235 + void examine(const Arc& arc) {
1.236 + if (_compMap[_digraph.source(arc)] !=
1.237 + _compMap[_digraph.target(arc)]) {
1.238 + _cutMap.set(arc, true);
1.239 + ++_cutNum;
1.240 + }
1.241 + }
1.242 + private:
1.243 + const Digraph& _digraph;
1.244 + ArcMap& _cutMap;
1.245 + int& _cutNum;
1.246 +
1.247 + typename Digraph::template NodeMap<int> _compMap;
1.248 + int _num;
1.249 + };
1.250 +
1.251 + }
1.252 +
1.253 +
1.254 + /// \ingroup graph_properties
1.255 + ///
1.256 + /// \brief Check whether a directed graph is strongly connected.
1.257 + ///
1.258 + /// This function checks whether the given directed graph is strongly
1.259 + /// connected, i.e. any two nodes of the digraph are
1.260 + /// connected with directed paths in both direction.
1.261 + ///
1.262 + /// \return \c true if the digraph is strongly connected.
1.263 + /// \note By definition, the empty digraph is strongly connected.
1.264 + ///
1.265 + /// \see countStronglyConnectedComponents(), stronglyConnectedComponents()
1.266 + /// \see connected()
1.267 + template <typename Digraph>
1.268 + bool stronglyConnected(const Digraph& digraph) {
1.269 + checkConcept<concepts::Digraph, Digraph>();
1.270 +
1.271 + typedef typename Digraph::Node Node;
1.272 + typedef typename Digraph::NodeIt NodeIt;
1.273 +
1.274 + typename Digraph::Node source = NodeIt(digraph);
1.275 + if (source == INVALID) return true;
1.276 +
1.277 + using namespace _connectivity_bits;
1.278 +
1.279 + typedef DfsVisitor<Digraph> Visitor;
1.280 + Visitor visitor;
1.281 +
1.282 + DfsVisit<Digraph, Visitor> dfs(digraph, visitor);
1.283 + dfs.init();
1.284 + dfs.addSource(source);
1.285 + dfs.start();
1.286 +
1.287 + for (NodeIt it(digraph); it != INVALID; ++it) {
1.288 + if (!dfs.reached(it)) {
1.289 + return false;
1.290 + }
1.291 + }
1.292 +
1.293 + typedef ReverseDigraph<const Digraph> RDigraph;
1.294 + typedef typename RDigraph::NodeIt RNodeIt;
1.295 + RDigraph rdigraph(digraph);
1.296 +
1.297 + typedef DfsVisitor<RDigraph> RVisitor;
1.298 + RVisitor rvisitor;
1.299 +
1.300 + DfsVisit<RDigraph, RVisitor> rdfs(rdigraph, rvisitor);
1.301 + rdfs.init();
1.302 + rdfs.addSource(source);
1.303 + rdfs.start();
1.304 +
1.305 + for (RNodeIt it(rdigraph); it != INVALID; ++it) {
1.306 + if (!rdfs.reached(it)) {
1.307 + return false;
1.308 + }
1.309 + }
1.310 +
1.311 + return true;
1.312 + }
1.313 +
1.314 + /// \ingroup graph_properties
1.315 + ///
1.316 + /// \brief Count the number of strongly connected components of a
1.317 + /// directed graph
1.318 + ///
1.319 + /// This function counts the number of strongly connected components of
1.320 + /// the given directed graph.
1.321 + ///
1.322 + /// The strongly connected components are the classes of an
1.323 + /// equivalence relation on the nodes of a digraph. Two nodes are in
1.324 + /// the same class if they are connected with directed paths in both
1.325 + /// direction.
1.326 + ///
1.327 + /// \return The number of strongly connected components.
1.328 + /// \note By definition, the empty digraph has zero
1.329 + /// strongly connected components.
1.330 + ///
1.331 + /// \see stronglyConnected(), stronglyConnectedComponents()
1.332 + template <typename Digraph>
1.333 + int countStronglyConnectedComponents(const Digraph& digraph) {
1.334 + checkConcept<concepts::Digraph, Digraph>();
1.335 +
1.336 + using namespace _connectivity_bits;
1.337 +
1.338 + typedef typename Digraph::Node Node;
1.339 + typedef typename Digraph::Arc Arc;
1.340 + typedef typename Digraph::NodeIt NodeIt;
1.341 + typedef typename Digraph::ArcIt ArcIt;
1.342 +
1.343 + typedef std::vector<Node> Container;
1.344 + typedef typename Container::iterator Iterator;
1.345 +
1.346 + Container nodes(countNodes(digraph));
1.347 + typedef LeaveOrderVisitor<Digraph, Iterator> Visitor;
1.348 + Visitor visitor(nodes.begin());
1.349 +
1.350 + DfsVisit<Digraph, Visitor> dfs(digraph, visitor);
1.351 + dfs.init();
1.352 + for (NodeIt it(digraph); it != INVALID; ++it) {
1.353 + if (!dfs.reached(it)) {
1.354 + dfs.addSource(it);
1.355 + dfs.start();
1.356 + }
1.357 + }
1.358 +
1.359 + typedef typename Container::reverse_iterator RIterator;
1.360 + typedef ReverseDigraph<const Digraph> RDigraph;
1.361 +
1.362 + RDigraph rdigraph(digraph);
1.363 +
1.364 + typedef DfsVisitor<Digraph> RVisitor;
1.365 + RVisitor rvisitor;
1.366 +
1.367 + DfsVisit<RDigraph, RVisitor> rdfs(rdigraph, rvisitor);
1.368 +
1.369 + int compNum = 0;
1.370 +
1.371 + rdfs.init();
1.372 + for (RIterator it = nodes.rbegin(); it != nodes.rend(); ++it) {
1.373 + if (!rdfs.reached(*it)) {
1.374 + rdfs.addSource(*it);
1.375 + rdfs.start();
1.376 + ++compNum;
1.377 + }
1.378 + }
1.379 + return compNum;
1.380 + }
1.381 +
1.382 + /// \ingroup graph_properties
1.383 + ///
1.384 + /// \brief Find the strongly connected components of a directed graph
1.385 + ///
1.386 + /// This function finds the strongly connected components of the given
1.387 + /// directed graph. In addition, the numbering of the components will
1.388 + /// satisfy that there is no arc going from a higher numbered component
1.389 + /// to a lower one (i.e. it provides a topological order of the components).
1.390 + ///
1.391 + /// The strongly connected components are the classes of an
1.392 + /// equivalence relation on the nodes of a digraph. Two nodes are in
1.393 + /// the same class if they are connected with directed paths in both
1.394 + /// direction.
1.395 + ///
1.396 + /// \image html strongly_connected_components.png
1.397 + /// \image latex strongly_connected_components.eps "Strongly connected components" width=\textwidth
1.398 + ///
1.399 + /// \param digraph The digraph.
1.400 + /// \retval compMap A writable node map. The values will be set from 0 to
1.401 + /// the number of the strongly connected components minus one. Each value
1.402 + /// of the map will be set exactly once, and the values of a certain
1.403 + /// component will be set continuously.
1.404 + /// \return The number of strongly connected components.
1.405 + /// \note By definition, the empty digraph has zero
1.406 + /// strongly connected components.
1.407 + ///
1.408 + /// \see stronglyConnected(), countStronglyConnectedComponents()
1.409 + template <typename Digraph, typename NodeMap>
1.410 + int stronglyConnectedComponents(const Digraph& digraph, NodeMap& compMap) {
1.411 + checkConcept<concepts::Digraph, Digraph>();
1.412 + typedef typename Digraph::Node Node;
1.413 + typedef typename Digraph::NodeIt NodeIt;
1.414 + checkConcept<concepts::WriteMap<Node, int>, NodeMap>();
1.415 +
1.416 + using namespace _connectivity_bits;
1.417 +
1.418 + typedef std::vector<Node> Container;
1.419 + typedef typename Container::iterator Iterator;
1.420 +
1.421 + Container nodes(countNodes(digraph));
1.422 + typedef LeaveOrderVisitor<Digraph, Iterator> Visitor;
1.423 + Visitor visitor(nodes.begin());
1.424 +
1.425 + DfsVisit<Digraph, Visitor> dfs(digraph, visitor);
1.426 + dfs.init();
1.427 + for (NodeIt it(digraph); it != INVALID; ++it) {
1.428 + if (!dfs.reached(it)) {
1.429 + dfs.addSource(it);
1.430 + dfs.start();
1.431 + }
1.432 + }
1.433 +
1.434 + typedef typename Container::reverse_iterator RIterator;
1.435 + typedef ReverseDigraph<const Digraph> RDigraph;
1.436 +
1.437 + RDigraph rdigraph(digraph);
1.438 +
1.439 + int compNum = 0;
1.440 +
1.441 + typedef FillMapVisitor<RDigraph, NodeMap> RVisitor;
1.442 + RVisitor rvisitor(compMap, compNum);
1.443 +
1.444 + DfsVisit<RDigraph, RVisitor> rdfs(rdigraph, rvisitor);
1.445 +
1.446 + rdfs.init();
1.447 + for (RIterator it = nodes.rbegin(); it != nodes.rend(); ++it) {
1.448 + if (!rdfs.reached(*it)) {
1.449 + rdfs.addSource(*it);
1.450 + rdfs.start();
1.451 + ++compNum;
1.452 + }
1.453 + }
1.454 + return compNum;
1.455 + }
1.456 +
1.457 + /// \ingroup graph_properties
1.458 + ///
1.459 + /// \brief Find the cut arcs of the strongly connected components.
1.460 + ///
1.461 + /// This function finds the cut arcs of the strongly connected components
1.462 + /// of the given digraph.
1.463 + ///
1.464 + /// The strongly connected components are the classes of an
1.465 + /// equivalence relation on the nodes of a digraph. Two nodes are in
1.466 + /// the same class if they are connected with directed paths in both
1.467 + /// direction.
1.468 + /// The strongly connected components are separated by the cut arcs.
1.469 + ///
1.470 + /// \param digraph The digraph.
1.471 + /// \retval cutMap A writable arc map. The values will be set to \c true
1.472 + /// for the cut arcs (exactly once for each cut arc), and will not be
1.473 + /// changed for other arcs.
1.474 + /// \return The number of cut arcs.
1.475 + ///
1.476 + /// \see stronglyConnected(), stronglyConnectedComponents()
1.477 + template <typename Digraph, typename ArcMap>
1.478 + int stronglyConnectedCutArcs(const Digraph& digraph, ArcMap& cutMap) {
1.479 + checkConcept<concepts::Digraph, Digraph>();
1.480 + typedef typename Digraph::Node Node;
1.481 + typedef typename Digraph::Arc Arc;
1.482 + typedef typename Digraph::NodeIt NodeIt;
1.483 + checkConcept<concepts::WriteMap<Arc, bool>, ArcMap>();
1.484 +
1.485 + using namespace _connectivity_bits;
1.486 +
1.487 + typedef std::vector<Node> Container;
1.488 + typedef typename Container::iterator Iterator;
1.489 +
1.490 + Container nodes(countNodes(digraph));
1.491 + typedef LeaveOrderVisitor<Digraph, Iterator> Visitor;
1.492 + Visitor visitor(nodes.begin());
1.493 +
1.494 + DfsVisit<Digraph, Visitor> dfs(digraph, visitor);
1.495 + dfs.init();
1.496 + for (NodeIt it(digraph); it != INVALID; ++it) {
1.497 + if (!dfs.reached(it)) {
1.498 + dfs.addSource(it);
1.499 + dfs.start();
1.500 + }
1.501 + }
1.502 +
1.503 + typedef typename Container::reverse_iterator RIterator;
1.504 + typedef ReverseDigraph<const Digraph> RDigraph;
1.505 +
1.506 + RDigraph rdigraph(digraph);
1.507 +
1.508 + int cutNum = 0;
1.509 +
1.510 + typedef StronglyConnectedCutArcsVisitor<RDigraph, ArcMap> RVisitor;
1.511 + RVisitor rvisitor(rdigraph, cutMap, cutNum);
1.512 +
1.513 + DfsVisit<RDigraph, RVisitor> rdfs(rdigraph, rvisitor);
1.514 +
1.515 + rdfs.init();
1.516 + for (RIterator it = nodes.rbegin(); it != nodes.rend(); ++it) {
1.517 + if (!rdfs.reached(*it)) {
1.518 + rdfs.addSource(*it);
1.519 + rdfs.start();
1.520 + }
1.521 + }
1.522 + return cutNum;
1.523 + }
1.524 +
1.525 + namespace _connectivity_bits {
1.526 +
1.527 + template <typename Digraph>
1.528 + class CountBiNodeConnectedComponentsVisitor : public DfsVisitor<Digraph> {
1.529 + public:
1.530 + typedef typename Digraph::Node Node;
1.531 + typedef typename Digraph::Arc Arc;
1.532 + typedef typename Digraph::Edge Edge;
1.533 +
1.534 + CountBiNodeConnectedComponentsVisitor(const Digraph& graph, int &compNum)
1.535 + : _graph(graph), _compNum(compNum),
1.536 + _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
1.537 +
1.538 + void start(const Node& node) {
1.539 + _predMap.set(node, INVALID);
1.540 + }
1.541 +
1.542 + void reach(const Node& node) {
1.543 + _numMap.set(node, _num);
1.544 + _retMap.set(node, _num);
1.545 + ++_num;
1.546 + }
1.547 +
1.548 + void discover(const Arc& edge) {
1.549 + _predMap.set(_graph.target(edge), _graph.source(edge));
1.550 + }
1.551 +
1.552 + void examine(const Arc& edge) {
1.553 + if (_graph.source(edge) == _graph.target(edge) &&
1.554 + _graph.direction(edge)) {
1.555 + ++_compNum;
1.556 + return;
1.557 + }
1.558 + if (_predMap[_graph.source(edge)] == _graph.target(edge)) {
1.559 + return;
1.560 + }
1.561 + if (_retMap[_graph.source(edge)] > _numMap[_graph.target(edge)]) {
1.562 + _retMap.set(_graph.source(edge), _numMap[_graph.target(edge)]);
1.563 + }
1.564 + }
1.565 +
1.566 + void backtrack(const Arc& edge) {
1.567 + if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
1.568 + _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
1.569 + }
1.570 + if (_numMap[_graph.source(edge)] <= _retMap[_graph.target(edge)]) {
1.571 + ++_compNum;
1.572 + }
1.573 + }
1.574 +
1.575 + private:
1.576 + const Digraph& _graph;
1.577 + int& _compNum;
1.578 +
1.579 + typename Digraph::template NodeMap<int> _numMap;
1.580 + typename Digraph::template NodeMap<int> _retMap;
1.581 + typename Digraph::template NodeMap<Node> _predMap;
1.582 + int _num;
1.583 + };
1.584 +
1.585 + template <typename Digraph, typename ArcMap>
1.586 + class BiNodeConnectedComponentsVisitor : public DfsVisitor<Digraph> {
1.587 + public:
1.588 + typedef typename Digraph::Node Node;
1.589 + typedef typename Digraph::Arc Arc;
1.590 + typedef typename Digraph::Edge Edge;
1.591 +
1.592 + BiNodeConnectedComponentsVisitor(const Digraph& graph,
1.593 + ArcMap& compMap, int &compNum)
1.594 + : _graph(graph), _compMap(compMap), _compNum(compNum),
1.595 + _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
1.596 +
1.597 + void start(const Node& node) {
1.598 + _predMap.set(node, INVALID);
1.599 + }
1.600 +
1.601 + void reach(const Node& node) {
1.602 + _numMap.set(node, _num);
1.603 + _retMap.set(node, _num);
1.604 + ++_num;
1.605 + }
1.606 +
1.607 + void discover(const Arc& edge) {
1.608 + Node target = _graph.target(edge);
1.609 + _predMap.set(target, edge);
1.610 + _edgeStack.push(edge);
1.611 + }
1.612 +
1.613 + void examine(const Arc& edge) {
1.614 + Node source = _graph.source(edge);
1.615 + Node target = _graph.target(edge);
1.616 + if (source == target && _graph.direction(edge)) {
1.617 + _compMap.set(edge, _compNum);
1.618 + ++_compNum;
1.619 + return;
1.620 + }
1.621 + if (_numMap[target] < _numMap[source]) {
1.622 + if (_predMap[source] != _graph.oppositeArc(edge)) {
1.623 + _edgeStack.push(edge);
1.624 + }
1.625 + }
1.626 + if (_predMap[source] != INVALID &&
1.627 + target == _graph.source(_predMap[source])) {
1.628 + return;
1.629 + }
1.630 + if (_retMap[source] > _numMap[target]) {
1.631 + _retMap.set(source, _numMap[target]);
1.632 + }
1.633 + }
1.634 +
1.635 + void backtrack(const Arc& edge) {
1.636 + Node source = _graph.source(edge);
1.637 + Node target = _graph.target(edge);
1.638 + if (_retMap[source] > _retMap[target]) {
1.639 + _retMap.set(source, _retMap[target]);
1.640 + }
1.641 + if (_numMap[source] <= _retMap[target]) {
1.642 + while (_edgeStack.top() != edge) {
1.643 + _compMap.set(_edgeStack.top(), _compNum);
1.644 + _edgeStack.pop();
1.645 + }
1.646 + _compMap.set(edge, _compNum);
1.647 + _edgeStack.pop();
1.648 + ++_compNum;
1.649 + }
1.650 + }
1.651 +
1.652 + private:
1.653 + const Digraph& _graph;
1.654 + ArcMap& _compMap;
1.655 + int& _compNum;
1.656 +
1.657 + typename Digraph::template NodeMap<int> _numMap;
1.658 + typename Digraph::template NodeMap<int> _retMap;
1.659 + typename Digraph::template NodeMap<Arc> _predMap;
1.660 + std::stack<Edge> _edgeStack;
1.661 + int _num;
1.662 + };
1.663 +
1.664 +
1.665 + template <typename Digraph, typename NodeMap>
1.666 + class BiNodeConnectedCutNodesVisitor : public DfsVisitor<Digraph> {
1.667 + public:
1.668 + typedef typename Digraph::Node Node;
1.669 + typedef typename Digraph::Arc Arc;
1.670 + typedef typename Digraph::Edge Edge;
1.671 +
1.672 + BiNodeConnectedCutNodesVisitor(const Digraph& graph, NodeMap& cutMap,
1.673 + int& cutNum)
1.674 + : _graph(graph), _cutMap(cutMap), _cutNum(cutNum),
1.675 + _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
1.676 +
1.677 + void start(const Node& node) {
1.678 + _predMap.set(node, INVALID);
1.679 + rootCut = false;
1.680 + }
1.681 +
1.682 + void reach(const Node& node) {
1.683 + _numMap.set(node, _num);
1.684 + _retMap.set(node, _num);
1.685 + ++_num;
1.686 + }
1.687 +
1.688 + void discover(const Arc& edge) {
1.689 + _predMap.set(_graph.target(edge), _graph.source(edge));
1.690 + }
1.691 +
1.692 + void examine(const Arc& edge) {
1.693 + if (_graph.source(edge) == _graph.target(edge) &&
1.694 + _graph.direction(edge)) {
1.695 + if (!_cutMap[_graph.source(edge)]) {
1.696 + _cutMap.set(_graph.source(edge), true);
1.697 + ++_cutNum;
1.698 + }
1.699 + return;
1.700 + }
1.701 + if (_predMap[_graph.source(edge)] == _graph.target(edge)) return;
1.702 + if (_retMap[_graph.source(edge)] > _numMap[_graph.target(edge)]) {
1.703 + _retMap.set(_graph.source(edge), _numMap[_graph.target(edge)]);
1.704 + }
1.705 + }
1.706 +
1.707 + void backtrack(const Arc& edge) {
1.708 + if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
1.709 + _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
1.710 + }
1.711 + if (_numMap[_graph.source(edge)] <= _retMap[_graph.target(edge)]) {
1.712 + if (_predMap[_graph.source(edge)] != INVALID) {
1.713 + if (!_cutMap[_graph.source(edge)]) {
1.714 + _cutMap.set(_graph.source(edge), true);
1.715 + ++_cutNum;
1.716 + }
1.717 + } else if (rootCut) {
1.718 + if (!_cutMap[_graph.source(edge)]) {
1.719 + _cutMap.set(_graph.source(edge), true);
1.720 + ++_cutNum;
1.721 + }
1.722 + } else {
1.723 + rootCut = true;
1.724 + }
1.725 + }
1.726 + }
1.727 +
1.728 + private:
1.729 + const Digraph& _graph;
1.730 + NodeMap& _cutMap;
1.731 + int& _cutNum;
1.732 +
1.733 + typename Digraph::template NodeMap<int> _numMap;
1.734 + typename Digraph::template NodeMap<int> _retMap;
1.735 + typename Digraph::template NodeMap<Node> _predMap;
1.736 + std::stack<Edge> _edgeStack;
1.737 + int _num;
1.738 + bool rootCut;
1.739 + };
1.740 +
1.741 + }
1.742 +
1.743 + template <typename Graph>
1.744 + int countBiNodeConnectedComponents(const Graph& graph);
1.745 +
1.746 + /// \ingroup graph_properties
1.747 + ///
1.748 + /// \brief Check whether an undirected graph is bi-node-connected.
1.749 + ///
1.750 + /// This function checks whether the given undirected graph is
1.751 + /// bi-node-connected, i.e. any two edges are on same circle.
1.752 + ///
1.753 + /// \return \c true if the graph bi-node-connected.
1.754 + /// \note By definition, the empty graph is bi-node-connected.
1.755 + ///
1.756 + /// \see countBiNodeConnectedComponents(), biNodeConnectedComponents()
1.757 + template <typename Graph>
1.758 + bool biNodeConnected(const Graph& graph) {
1.759 + return countBiNodeConnectedComponents(graph) <= 1;
1.760 + }
1.761 +
1.762 + /// \ingroup graph_properties
1.763 + ///
1.764 + /// \brief Count the number of bi-node-connected components of an
1.765 + /// undirected graph.
1.766 + ///
1.767 + /// This function counts the number of bi-node-connected components of
1.768 + /// the given undirected graph.
1.769 + ///
1.770 + /// The bi-node-connected components are the classes of an equivalence
1.771 + /// relation on the edges of a undirected graph. Two edges are in the
1.772 + /// same class if they are on same circle.
1.773 + ///
1.774 + /// \return The number of bi-node-connected components.
1.775 + ///
1.776 + /// \see biNodeConnected(), biNodeConnectedComponents()
1.777 + template <typename Graph>
1.778 + int countBiNodeConnectedComponents(const Graph& graph) {
1.779 + checkConcept<concepts::Graph, Graph>();
1.780 + typedef typename Graph::NodeIt NodeIt;
1.781 +
1.782 + using namespace _connectivity_bits;
1.783 +
1.784 + typedef CountBiNodeConnectedComponentsVisitor<Graph> Visitor;
1.785 +
1.786 + int compNum = 0;
1.787 + Visitor visitor(graph, compNum);
1.788 +
1.789 + DfsVisit<Graph, Visitor> dfs(graph, visitor);
1.790 + dfs.init();
1.791 +
1.792 + for (NodeIt it(graph); it != INVALID; ++it) {
1.793 + if (!dfs.reached(it)) {
1.794 + dfs.addSource(it);
1.795 + dfs.start();
1.796 + }
1.797 + }
1.798 + return compNum;
1.799 + }
1.800 +
1.801 + /// \ingroup graph_properties
1.802 + ///
1.803 + /// \brief Find the bi-node-connected components of an undirected graph.
1.804 + ///
1.805 + /// This function finds the bi-node-connected components of the given
1.806 + /// undirected graph.
1.807 + ///
1.808 + /// The bi-node-connected components are the classes of an equivalence
1.809 + /// relation on the edges of a undirected graph. Two edges are in the
1.810 + /// same class if they are on same circle.
1.811 + ///
1.812 + /// \image html node_biconnected_components.png
1.813 + /// \image latex node_biconnected_components.eps "bi-node-connected components" width=\textwidth
1.814 + ///
1.815 + /// \param graph The undirected graph.
1.816 + /// \retval compMap A writable edge map. The values will be set from 0
1.817 + /// to the number of the bi-node-connected components minus one. Each
1.818 + /// value of the map will be set exactly once, and the values of a
1.819 + /// certain component will be set continuously.
1.820 + /// \return The number of bi-node-connected components.
1.821 + ///
1.822 + /// \see biNodeConnected(), countBiNodeConnectedComponents()
1.823 + template <typename Graph, typename EdgeMap>
1.824 + int biNodeConnectedComponents(const Graph& graph,
1.825 + EdgeMap& compMap) {
1.826 + checkConcept<concepts::Graph, Graph>();
1.827 + typedef typename Graph::NodeIt NodeIt;
1.828 + typedef typename Graph::Edge Edge;
1.829 + checkConcept<concepts::WriteMap<Edge, int>, EdgeMap>();
1.830 +
1.831 + using namespace _connectivity_bits;
1.832 +
1.833 + typedef BiNodeConnectedComponentsVisitor<Graph, EdgeMap> Visitor;
1.834 +
1.835 + int compNum = 0;
1.836 + Visitor visitor(graph, compMap, compNum);
1.837 +
1.838 + DfsVisit<Graph, Visitor> dfs(graph, visitor);
1.839 + dfs.init();
1.840 +
1.841 + for (NodeIt it(graph); it != INVALID; ++it) {
1.842 + if (!dfs.reached(it)) {
1.843 + dfs.addSource(it);
1.844 + dfs.start();
1.845 + }
1.846 + }
1.847 + return compNum;
1.848 + }
1.849 +
1.850 + /// \ingroup graph_properties
1.851 + ///
1.852 + /// \brief Find the bi-node-connected cut nodes in an undirected graph.
1.853 + ///
1.854 + /// This function finds the bi-node-connected cut nodes in the given
1.855 + /// undirected graph.
1.856 + ///
1.857 + /// The bi-node-connected components are the classes of an equivalence
1.858 + /// relation on the edges of a undirected graph. Two edges are in the
1.859 + /// same class if they are on same circle.
1.860 + /// The bi-node-connected components are separted by the cut nodes of
1.861 + /// the components.
1.862 + ///
1.863 + /// \param graph The undirected graph.
1.864 + /// \retval cutMap A writable node map. The values will be set to
1.865 + /// \c true for the nodes that separate two or more components
1.866 + /// (exactly once for each cut node), and will not be changed for
1.867 + /// other nodes.
1.868 + /// \return The number of the cut nodes.
1.869 + ///
1.870 + /// \see biNodeConnected(), biNodeConnectedComponents()
1.871 + template <typename Graph, typename NodeMap>
1.872 + int biNodeConnectedCutNodes(const Graph& graph, NodeMap& cutMap) {
1.873 + checkConcept<concepts::Graph, Graph>();
1.874 + typedef typename Graph::Node Node;
1.875 + typedef typename Graph::NodeIt NodeIt;
1.876 + checkConcept<concepts::WriteMap<Node, bool>, NodeMap>();
1.877 +
1.878 + using namespace _connectivity_bits;
1.879 +
1.880 + typedef BiNodeConnectedCutNodesVisitor<Graph, NodeMap> Visitor;
1.881 +
1.882 + int cutNum = 0;
1.883 + Visitor visitor(graph, cutMap, cutNum);
1.884 +
1.885 + DfsVisit<Graph, Visitor> dfs(graph, visitor);
1.886 + dfs.init();
1.887 +
1.888 + for (NodeIt it(graph); it != INVALID; ++it) {
1.889 + if (!dfs.reached(it)) {
1.890 + dfs.addSource(it);
1.891 + dfs.start();
1.892 + }
1.893 + }
1.894 + return cutNum;
1.895 + }
1.896 +
1.897 + namespace _connectivity_bits {
1.898 +
1.899 + template <typename Digraph>
1.900 + class CountBiEdgeConnectedComponentsVisitor : public DfsVisitor<Digraph> {
1.901 + public:
1.902 + typedef typename Digraph::Node Node;
1.903 + typedef typename Digraph::Arc Arc;
1.904 + typedef typename Digraph::Edge Edge;
1.905 +
1.906 + CountBiEdgeConnectedComponentsVisitor(const Digraph& graph, int &compNum)
1.907 + : _graph(graph), _compNum(compNum),
1.908 + _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
1.909 +
1.910 + void start(const Node& node) {
1.911 + _predMap.set(node, INVALID);
1.912 + }
1.913 +
1.914 + void reach(const Node& node) {
1.915 + _numMap.set(node, _num);
1.916 + _retMap.set(node, _num);
1.917 + ++_num;
1.918 + }
1.919 +
1.920 + void leave(const Node& node) {
1.921 + if (_numMap[node] <= _retMap[node]) {
1.922 + ++_compNum;
1.923 + }
1.924 + }
1.925 +
1.926 + void discover(const Arc& edge) {
1.927 + _predMap.set(_graph.target(edge), edge);
1.928 + }
1.929 +
1.930 + void examine(const Arc& edge) {
1.931 + if (_predMap[_graph.source(edge)] == _graph.oppositeArc(edge)) {
1.932 + return;
1.933 + }
1.934 + if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
1.935 + _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
1.936 + }
1.937 + }
1.938 +
1.939 + void backtrack(const Arc& edge) {
1.940 + if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
1.941 + _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
1.942 + }
1.943 + }
1.944 +
1.945 + private:
1.946 + const Digraph& _graph;
1.947 + int& _compNum;
1.948 +
1.949 + typename Digraph::template NodeMap<int> _numMap;
1.950 + typename Digraph::template NodeMap<int> _retMap;
1.951 + typename Digraph::template NodeMap<Arc> _predMap;
1.952 + int _num;
1.953 + };
1.954 +
1.955 + template <typename Digraph, typename NodeMap>
1.956 + class BiEdgeConnectedComponentsVisitor : public DfsVisitor<Digraph> {
1.957 + public:
1.958 + typedef typename Digraph::Node Node;
1.959 + typedef typename Digraph::Arc Arc;
1.960 + typedef typename Digraph::Edge Edge;
1.961 +
1.962 + BiEdgeConnectedComponentsVisitor(const Digraph& graph,
1.963 + NodeMap& compMap, int &compNum)
1.964 + : _graph(graph), _compMap(compMap), _compNum(compNum),
1.965 + _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
1.966 +
1.967 + void start(const Node& node) {
1.968 + _predMap.set(node, INVALID);
1.969 + }
1.970 +
1.971 + void reach(const Node& node) {
1.972 + _numMap.set(node, _num);
1.973 + _retMap.set(node, _num);
1.974 + _nodeStack.push(node);
1.975 + ++_num;
1.976 + }
1.977 +
1.978 + void leave(const Node& node) {
1.979 + if (_numMap[node] <= _retMap[node]) {
1.980 + while (_nodeStack.top() != node) {
1.981 + _compMap.set(_nodeStack.top(), _compNum);
1.982 + _nodeStack.pop();
1.983 + }
1.984 + _compMap.set(node, _compNum);
1.985 + _nodeStack.pop();
1.986 + ++_compNum;
1.987 + }
1.988 + }
1.989 +
1.990 + void discover(const Arc& edge) {
1.991 + _predMap.set(_graph.target(edge), edge);
1.992 + }
1.993 +
1.994 + void examine(const Arc& edge) {
1.995 + if (_predMap[_graph.source(edge)] == _graph.oppositeArc(edge)) {
1.996 + return;
1.997 + }
1.998 + if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
1.999 + _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
1.1000 + }
1.1001 + }
1.1002 +
1.1003 + void backtrack(const Arc& edge) {
1.1004 + if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
1.1005 + _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
1.1006 + }
1.1007 + }
1.1008 +
1.1009 + private:
1.1010 + const Digraph& _graph;
1.1011 + NodeMap& _compMap;
1.1012 + int& _compNum;
1.1013 +
1.1014 + typename Digraph::template NodeMap<int> _numMap;
1.1015 + typename Digraph::template NodeMap<int> _retMap;
1.1016 + typename Digraph::template NodeMap<Arc> _predMap;
1.1017 + std::stack<Node> _nodeStack;
1.1018 + int _num;
1.1019 + };
1.1020 +
1.1021 +
1.1022 + template <typename Digraph, typename ArcMap>
1.1023 + class BiEdgeConnectedCutEdgesVisitor : public DfsVisitor<Digraph> {
1.1024 + public:
1.1025 + typedef typename Digraph::Node Node;
1.1026 + typedef typename Digraph::Arc Arc;
1.1027 + typedef typename Digraph::Edge Edge;
1.1028 +
1.1029 + BiEdgeConnectedCutEdgesVisitor(const Digraph& graph,
1.1030 + ArcMap& cutMap, int &cutNum)
1.1031 + : _graph(graph), _cutMap(cutMap), _cutNum(cutNum),
1.1032 + _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
1.1033 +
1.1034 + void start(const Node& node) {
1.1035 + _predMap[node] = INVALID;
1.1036 + }
1.1037 +
1.1038 + void reach(const Node& node) {
1.1039 + _numMap.set(node, _num);
1.1040 + _retMap.set(node, _num);
1.1041 + ++_num;
1.1042 + }
1.1043 +
1.1044 + void leave(const Node& node) {
1.1045 + if (_numMap[node] <= _retMap[node]) {
1.1046 + if (_predMap[node] != INVALID) {
1.1047 + _cutMap.set(_predMap[node], true);
1.1048 + ++_cutNum;
1.1049 + }
1.1050 + }
1.1051 + }
1.1052 +
1.1053 + void discover(const Arc& edge) {
1.1054 + _predMap.set(_graph.target(edge), edge);
1.1055 + }
1.1056 +
1.1057 + void examine(const Arc& edge) {
1.1058 + if (_predMap[_graph.source(edge)] == _graph.oppositeArc(edge)) {
1.1059 + return;
1.1060 + }
1.1061 + if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
1.1062 + _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
1.1063 + }
1.1064 + }
1.1065 +
1.1066 + void backtrack(const Arc& edge) {
1.1067 + if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
1.1068 + _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
1.1069 + }
1.1070 + }
1.1071 +
1.1072 + private:
1.1073 + const Digraph& _graph;
1.1074 + ArcMap& _cutMap;
1.1075 + int& _cutNum;
1.1076 +
1.1077 + typename Digraph::template NodeMap<int> _numMap;
1.1078 + typename Digraph::template NodeMap<int> _retMap;
1.1079 + typename Digraph::template NodeMap<Arc> _predMap;
1.1080 + int _num;
1.1081 + };
1.1082 + }
1.1083 +
1.1084 + template <typename Graph>
1.1085 + int countBiEdgeConnectedComponents(const Graph& graph);
1.1086 +
1.1087 + /// \ingroup graph_properties
1.1088 + ///
1.1089 + /// \brief Check whether an undirected graph is bi-edge-connected.
1.1090 + ///
1.1091 + /// This function checks whether the given undirected graph is
1.1092 + /// bi-edge-connected, i.e. any two nodes are connected with at least
1.1093 + /// two edge-disjoint paths.
1.1094 + ///
1.1095 + /// \return \c true if the graph is bi-edge-connected.
1.1096 + /// \note By definition, the empty graph is bi-edge-connected.
1.1097 + ///
1.1098 + /// \see countBiEdgeConnectedComponents(), biEdgeConnectedComponents()
1.1099 + template <typename Graph>
1.1100 + bool biEdgeConnected(const Graph& graph) {
1.1101 + return countBiEdgeConnectedComponents(graph) <= 1;
1.1102 + }
1.1103 +
1.1104 + /// \ingroup graph_properties
1.1105 + ///
1.1106 + /// \brief Count the number of bi-edge-connected components of an
1.1107 + /// undirected graph.
1.1108 + ///
1.1109 + /// This function counts the number of bi-edge-connected components of
1.1110 + /// the given undirected graph.
1.1111 + ///
1.1112 + /// The bi-edge-connected components are the classes of an equivalence
1.1113 + /// relation on the nodes of an undirected graph. Two nodes are in the
1.1114 + /// same class if they are connected with at least two edge-disjoint
1.1115 + /// paths.
1.1116 + ///
1.1117 + /// \return The number of bi-edge-connected components.
1.1118 + ///
1.1119 + /// \see biEdgeConnected(), biEdgeConnectedComponents()
1.1120 + template <typename Graph>
1.1121 + int countBiEdgeConnectedComponents(const Graph& graph) {
1.1122 + checkConcept<concepts::Graph, Graph>();
1.1123 + typedef typename Graph::NodeIt NodeIt;
1.1124 +
1.1125 + using namespace _connectivity_bits;
1.1126 +
1.1127 + typedef CountBiEdgeConnectedComponentsVisitor<Graph> Visitor;
1.1128 +
1.1129 + int compNum = 0;
1.1130 + Visitor visitor(graph, compNum);
1.1131 +
1.1132 + DfsVisit<Graph, Visitor> dfs(graph, visitor);
1.1133 + dfs.init();
1.1134 +
1.1135 + for (NodeIt it(graph); it != INVALID; ++it) {
1.1136 + if (!dfs.reached(it)) {
1.1137 + dfs.addSource(it);
1.1138 + dfs.start();
1.1139 + }
1.1140 + }
1.1141 + return compNum;
1.1142 + }
1.1143 +
1.1144 + /// \ingroup graph_properties
1.1145 + ///
1.1146 + /// \brief Find the bi-edge-connected components of an undirected graph.
1.1147 + ///
1.1148 + /// This function finds the bi-edge-connected components of the given
1.1149 + /// undirected graph.
1.1150 + ///
1.1151 + /// The bi-edge-connected components are the classes of an equivalence
1.1152 + /// relation on the nodes of an undirected graph. Two nodes are in the
1.1153 + /// same class if they are connected with at least two edge-disjoint
1.1154 + /// paths.
1.1155 + ///
1.1156 + /// \image html edge_biconnected_components.png
1.1157 + /// \image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth
1.1158 + ///
1.1159 + /// \param graph The undirected graph.
1.1160 + /// \retval compMap A writable node map. The values will be set from 0 to
1.1161 + /// the number of the bi-edge-connected components minus one. Each value
1.1162 + /// of the map will be set exactly once, and the values of a certain
1.1163 + /// component will be set continuously.
1.1164 + /// \return The number of bi-edge-connected components.
1.1165 + ///
1.1166 + /// \see biEdgeConnected(), countBiEdgeConnectedComponents()
1.1167 + template <typename Graph, typename NodeMap>
1.1168 + int biEdgeConnectedComponents(const Graph& graph, NodeMap& compMap) {
1.1169 + checkConcept<concepts::Graph, Graph>();
1.1170 + typedef typename Graph::NodeIt NodeIt;
1.1171 + typedef typename Graph::Node Node;
1.1172 + checkConcept<concepts::WriteMap<Node, int>, NodeMap>();
1.1173 +
1.1174 + using namespace _connectivity_bits;
1.1175 +
1.1176 + typedef BiEdgeConnectedComponentsVisitor<Graph, NodeMap> Visitor;
1.1177 +
1.1178 + int compNum = 0;
1.1179 + Visitor visitor(graph, compMap, compNum);
1.1180 +
1.1181 + DfsVisit<Graph, Visitor> dfs(graph, visitor);
1.1182 + dfs.init();
1.1183 +
1.1184 + for (NodeIt it(graph); it != INVALID; ++it) {
1.1185 + if (!dfs.reached(it)) {
1.1186 + dfs.addSource(it);
1.1187 + dfs.start();
1.1188 + }
1.1189 + }
1.1190 + return compNum;
1.1191 + }
1.1192 +
1.1193 + /// \ingroup graph_properties
1.1194 + ///
1.1195 + /// \brief Find the bi-edge-connected cut edges in an undirected graph.
1.1196 + ///
1.1197 + /// This function finds the bi-edge-connected cut edges in the given
1.1198 + /// undirected graph.
1.1199 + ///
1.1200 + /// The bi-edge-connected components are the classes of an equivalence
1.1201 + /// relation on the nodes of an undirected graph. Two nodes are in the
1.1202 + /// same class if they are connected with at least two edge-disjoint
1.1203 + /// paths.
1.1204 + /// The bi-edge-connected components are separted by the cut edges of
1.1205 + /// the components.
1.1206 + ///
1.1207 + /// \param graph The undirected graph.
1.1208 + /// \retval cutMap A writable edge map. The values will be set to \c true
1.1209 + /// for the cut edges (exactly once for each cut edge), and will not be
1.1210 + /// changed for other edges.
1.1211 + /// \return The number of cut edges.
1.1212 + ///
1.1213 + /// \see biEdgeConnected(), biEdgeConnectedComponents()
1.1214 + template <typename Graph, typename EdgeMap>
1.1215 + int biEdgeConnectedCutEdges(const Graph& graph, EdgeMap& cutMap) {
1.1216 + checkConcept<concepts::Graph, Graph>();
1.1217 + typedef typename Graph::NodeIt NodeIt;
1.1218 + typedef typename Graph::Edge Edge;
1.1219 + checkConcept<concepts::WriteMap<Edge, bool>, EdgeMap>();
1.1220 +
1.1221 + using namespace _connectivity_bits;
1.1222 +
1.1223 + typedef BiEdgeConnectedCutEdgesVisitor<Graph, EdgeMap> Visitor;
1.1224 +
1.1225 + int cutNum = 0;
1.1226 + Visitor visitor(graph, cutMap, cutNum);
1.1227 +
1.1228 + DfsVisit<Graph, Visitor> dfs(graph, visitor);
1.1229 + dfs.init();
1.1230 +
1.1231 + for (NodeIt it(graph); it != INVALID; ++it) {
1.1232 + if (!dfs.reached(it)) {
1.1233 + dfs.addSource(it);
1.1234 + dfs.start();
1.1235 + }
1.1236 + }
1.1237 + return cutNum;
1.1238 + }
1.1239 +
1.1240 +
1.1241 + namespace _connectivity_bits {
1.1242 +
1.1243 + template <typename Digraph, typename IntNodeMap>
1.1244 + class TopologicalSortVisitor : public DfsVisitor<Digraph> {
1.1245 + public:
1.1246 + typedef typename Digraph::Node Node;
1.1247 + typedef typename Digraph::Arc edge;
1.1248 +
1.1249 + TopologicalSortVisitor(IntNodeMap& order, int num)
1.1250 + : _order(order), _num(num) {}
1.1251 +
1.1252 + void leave(const Node& node) {
1.1253 + _order.set(node, --_num);
1.1254 + }
1.1255 +
1.1256 + private:
1.1257 + IntNodeMap& _order;
1.1258 + int _num;
1.1259 + };
1.1260 +
1.1261 + }
1.1262 +
1.1263 + /// \ingroup graph_properties
1.1264 + ///
1.1265 + /// \brief Check whether a digraph is DAG.
1.1266 + ///
1.1267 + /// This function checks whether the given digraph is DAG, i.e.
1.1268 + /// \e Directed \e Acyclic \e Graph.
1.1269 + /// \return \c true if there is no directed cycle in the digraph.
1.1270 + /// \see acyclic()
1.1271 + template <typename Digraph>
1.1272 + bool dag(const Digraph& digraph) {
1.1273 +
1.1274 + checkConcept<concepts::Digraph, Digraph>();
1.1275 +
1.1276 + typedef typename Digraph::Node Node;
1.1277 + typedef typename Digraph::NodeIt NodeIt;
1.1278 + typedef typename Digraph::Arc Arc;
1.1279 +
1.1280 + typedef typename Digraph::template NodeMap<bool> ProcessedMap;
1.1281 +
1.1282 + typename Dfs<Digraph>::template SetProcessedMap<ProcessedMap>::
1.1283 + Create dfs(digraph);
1.1284 +
1.1285 + ProcessedMap processed(digraph);
1.1286 + dfs.processedMap(processed);
1.1287 +
1.1288 + dfs.init();
1.1289 + for (NodeIt it(digraph); it != INVALID; ++it) {
1.1290 + if (!dfs.reached(it)) {
1.1291 + dfs.addSource(it);
1.1292 + while (!dfs.emptyQueue()) {
1.1293 + Arc arc = dfs.nextArc();
1.1294 + Node target = digraph.target(arc);
1.1295 + if (dfs.reached(target) && !processed[target]) {
1.1296 + return false;
1.1297 + }
1.1298 + dfs.processNextArc();
1.1299 + }
1.1300 + }
1.1301 + }
1.1302 + return true;
1.1303 + }
1.1304 +
1.1305 + /// \ingroup graph_properties
1.1306 + ///
1.1307 + /// \brief Sort the nodes of a DAG into topolgical order.
1.1308 + ///
1.1309 + /// This function sorts the nodes of the given acyclic digraph (DAG)
1.1310 + /// into topolgical order.
1.1311 + ///
1.1312 + /// \param digraph The digraph, which must be DAG.
1.1313 + /// \retval order A writable node map. The values will be set from 0 to
1.1314 + /// the number of the nodes in the digraph minus one. Each value of the
1.1315 + /// map will be set exactly once, and the values will be set descending
1.1316 + /// order.
1.1317 + ///
1.1318 + /// \see dag(), checkedTopologicalSort()
1.1319 + template <typename Digraph, typename NodeMap>
1.1320 + void topologicalSort(const Digraph& digraph, NodeMap& order) {
1.1321 + using namespace _connectivity_bits;
1.1322 +
1.1323 + checkConcept<concepts::Digraph, Digraph>();
1.1324 + checkConcept<concepts::WriteMap<typename Digraph::Node, int>, NodeMap>();
1.1325 +
1.1326 + typedef typename Digraph::Node Node;
1.1327 + typedef typename Digraph::NodeIt NodeIt;
1.1328 + typedef typename Digraph::Arc Arc;
1.1329 +
1.1330 + TopologicalSortVisitor<Digraph, NodeMap>
1.1331 + visitor(order, countNodes(digraph));
1.1332 +
1.1333 + DfsVisit<Digraph, TopologicalSortVisitor<Digraph, NodeMap> >
1.1334 + dfs(digraph, visitor);
1.1335 +
1.1336 + dfs.init();
1.1337 + for (NodeIt it(digraph); it != INVALID; ++it) {
1.1338 + if (!dfs.reached(it)) {
1.1339 + dfs.addSource(it);
1.1340 + dfs.start();
1.1341 + }
1.1342 + }
1.1343 + }
1.1344 +
1.1345 + /// \ingroup graph_properties
1.1346 + ///
1.1347 + /// \brief Sort the nodes of a DAG into topolgical order.
1.1348 + ///
1.1349 + /// This function sorts the nodes of the given acyclic digraph (DAG)
1.1350 + /// into topolgical order and also checks whether the given digraph
1.1351 + /// is DAG.
1.1352 + ///
1.1353 + /// \param digraph The digraph.
1.1354 + /// \retval order A readable and writable node map. The values will be
1.1355 + /// set from 0 to the number of the nodes in the digraph minus one.
1.1356 + /// Each value of the map will be set exactly once, and the values will
1.1357 + /// be set descending order.
1.1358 + /// \return \c false if the digraph is not DAG.
1.1359 + ///
1.1360 + /// \see dag(), topologicalSort()
1.1361 + template <typename Digraph, typename NodeMap>
1.1362 + bool checkedTopologicalSort(const Digraph& digraph, NodeMap& order) {
1.1363 + using namespace _connectivity_bits;
1.1364 +
1.1365 + checkConcept<concepts::Digraph, Digraph>();
1.1366 + checkConcept<concepts::ReadWriteMap<typename Digraph::Node, int>,
1.1367 + NodeMap>();
1.1368 +
1.1369 + typedef typename Digraph::Node Node;
1.1370 + typedef typename Digraph::NodeIt NodeIt;
1.1371 + typedef typename Digraph::Arc Arc;
1.1372 +
1.1373 + for (NodeIt it(digraph); it != INVALID; ++it) {
1.1374 + order.set(it, -1);
1.1375 + }
1.1376 +
1.1377 + TopologicalSortVisitor<Digraph, NodeMap>
1.1378 + visitor(order, countNodes(digraph));
1.1379 +
1.1380 + DfsVisit<Digraph, TopologicalSortVisitor<Digraph, NodeMap> >
1.1381 + dfs(digraph, visitor);
1.1382 +
1.1383 + dfs.init();
1.1384 + for (NodeIt it(digraph); it != INVALID; ++it) {
1.1385 + if (!dfs.reached(it)) {
1.1386 + dfs.addSource(it);
1.1387 + while (!dfs.emptyQueue()) {
1.1388 + Arc arc = dfs.nextArc();
1.1389 + Node target = digraph.target(arc);
1.1390 + if (dfs.reached(target) && order[target] == -1) {
1.1391 + return false;
1.1392 + }
1.1393 + dfs.processNextArc();
1.1394 + }
1.1395 + }
1.1396 + }
1.1397 + return true;
1.1398 + }
1.1399 +
1.1400 + /// \ingroup graph_properties
1.1401 + ///
1.1402 + /// \brief Check whether an undirected graph is acyclic.
1.1403 + ///
1.1404 + /// This function checks whether the given undirected graph is acyclic.
1.1405 + /// \return \c true if there is no cycle in the graph.
1.1406 + /// \see dag()
1.1407 + template <typename Graph>
1.1408 + bool acyclic(const Graph& graph) {
1.1409 + checkConcept<concepts::Graph, Graph>();
1.1410 + typedef typename Graph::Node Node;
1.1411 + typedef typename Graph::NodeIt NodeIt;
1.1412 + typedef typename Graph::Arc Arc;
1.1413 + Dfs<Graph> dfs(graph);
1.1414 + dfs.init();
1.1415 + for (NodeIt it(graph); it != INVALID; ++it) {
1.1416 + if (!dfs.reached(it)) {
1.1417 + dfs.addSource(it);
1.1418 + while (!dfs.emptyQueue()) {
1.1419 + Arc arc = dfs.nextArc();
1.1420 + Node source = graph.source(arc);
1.1421 + Node target = graph.target(arc);
1.1422 + if (dfs.reached(target) &&
1.1423 + dfs.predArc(source) != graph.oppositeArc(arc)) {
1.1424 + return false;
1.1425 + }
1.1426 + dfs.processNextArc();
1.1427 + }
1.1428 + }
1.1429 + }
1.1430 + return true;
1.1431 + }
1.1432 +
1.1433 + /// \ingroup graph_properties
1.1434 + ///
1.1435 + /// \brief Check whether an undirected graph is tree.
1.1436 + ///
1.1437 + /// This function checks whether the given undirected graph is tree.
1.1438 + /// \return \c true if the graph is acyclic and connected.
1.1439 + /// \see acyclic(), connected()
1.1440 + template <typename Graph>
1.1441 + bool tree(const Graph& graph) {
1.1442 + checkConcept<concepts::Graph, Graph>();
1.1443 + typedef typename Graph::Node Node;
1.1444 + typedef typename Graph::NodeIt NodeIt;
1.1445 + typedef typename Graph::Arc Arc;
1.1446 + if (NodeIt(graph) == INVALID) return true;
1.1447 + Dfs<Graph> dfs(graph);
1.1448 + dfs.init();
1.1449 + dfs.addSource(NodeIt(graph));
1.1450 + while (!dfs.emptyQueue()) {
1.1451 + Arc arc = dfs.nextArc();
1.1452 + Node source = graph.source(arc);
1.1453 + Node target = graph.target(arc);
1.1454 + if (dfs.reached(target) &&
1.1455 + dfs.predArc(source) != graph.oppositeArc(arc)) {
1.1456 + return false;
1.1457 + }
1.1458 + dfs.processNextArc();
1.1459 + }
1.1460 + for (NodeIt it(graph); it != INVALID; ++it) {
1.1461 + if (!dfs.reached(it)) {
1.1462 + return false;
1.1463 + }
1.1464 + }
1.1465 + return true;
1.1466 + }
1.1467 +
1.1468 + namespace _connectivity_bits {
1.1469 +
1.1470 + template <typename Digraph>
1.1471 + class BipartiteVisitor : public BfsVisitor<Digraph> {
1.1472 + public:
1.1473 + typedef typename Digraph::Arc Arc;
1.1474 + typedef typename Digraph::Node Node;
1.1475 +
1.1476 + BipartiteVisitor(const Digraph& graph, bool& bipartite)
1.1477 + : _graph(graph), _part(graph), _bipartite(bipartite) {}
1.1478 +
1.1479 + void start(const Node& node) {
1.1480 + _part[node] = true;
1.1481 + }
1.1482 + void discover(const Arc& edge) {
1.1483 + _part.set(_graph.target(edge), !_part[_graph.source(edge)]);
1.1484 + }
1.1485 + void examine(const Arc& edge) {
1.1486 + _bipartite = _bipartite &&
1.1487 + _part[_graph.target(edge)] != _part[_graph.source(edge)];
1.1488 + }
1.1489 +
1.1490 + private:
1.1491 +
1.1492 + const Digraph& _graph;
1.1493 + typename Digraph::template NodeMap<bool> _part;
1.1494 + bool& _bipartite;
1.1495 + };
1.1496 +
1.1497 + template <typename Digraph, typename PartMap>
1.1498 + class BipartitePartitionsVisitor : public BfsVisitor<Digraph> {
1.1499 + public:
1.1500 + typedef typename Digraph::Arc Arc;
1.1501 + typedef typename Digraph::Node Node;
1.1502 +
1.1503 + BipartitePartitionsVisitor(const Digraph& graph,
1.1504 + PartMap& part, bool& bipartite)
1.1505 + : _graph(graph), _part(part), _bipartite(bipartite) {}
1.1506 +
1.1507 + void start(const Node& node) {
1.1508 + _part.set(node, true);
1.1509 + }
1.1510 + void discover(const Arc& edge) {
1.1511 + _part.set(_graph.target(edge), !_part[_graph.source(edge)]);
1.1512 + }
1.1513 + void examine(const Arc& edge) {
1.1514 + _bipartite = _bipartite &&
1.1515 + _part[_graph.target(edge)] != _part[_graph.source(edge)];
1.1516 + }
1.1517 +
1.1518 + private:
1.1519 +
1.1520 + const Digraph& _graph;
1.1521 + PartMap& _part;
1.1522 + bool& _bipartite;
1.1523 + };
1.1524 + }
1.1525 +
1.1526 + /// \ingroup graph_properties
1.1527 + ///
1.1528 + /// \brief Check whether an undirected graph is bipartite.
1.1529 + ///
1.1530 + /// The function checks whether the given undirected graph is bipartite.
1.1531 + /// \return \c true if the graph is bipartite.
1.1532 + ///
1.1533 + /// \see bipartitePartitions()
1.1534 + template<typename Graph>
1.1535 + bool bipartite(const Graph &graph){
1.1536 + using namespace _connectivity_bits;
1.1537 +
1.1538 + checkConcept<concepts::Graph, Graph>();
1.1539 +
1.1540 + typedef typename Graph::NodeIt NodeIt;
1.1541 + typedef typename Graph::ArcIt ArcIt;
1.1542 +
1.1543 + bool bipartite = true;
1.1544 +
1.1545 + BipartiteVisitor<Graph>
1.1546 + visitor(graph, bipartite);
1.1547 + BfsVisit<Graph, BipartiteVisitor<Graph> >
1.1548 + bfs(graph, visitor);
1.1549 + bfs.init();
1.1550 + for(NodeIt it(graph); it != INVALID; ++it) {
1.1551 + if(!bfs.reached(it)){
1.1552 + bfs.addSource(it);
1.1553 + while (!bfs.emptyQueue()) {
1.1554 + bfs.processNextNode();
1.1555 + if (!bipartite) return false;
1.1556 + }
1.1557 + }
1.1558 + }
1.1559 + return true;
1.1560 + }
1.1561 +
1.1562 + /// \ingroup graph_properties
1.1563 + ///
1.1564 + /// \brief Find the bipartite partitions of an undirected graph.
1.1565 + ///
1.1566 + /// This function checks whether the given undirected graph is bipartite
1.1567 + /// and gives back the bipartite partitions.
1.1568 + ///
1.1569 + /// \image html bipartite_partitions.png
1.1570 + /// \image latex bipartite_partitions.eps "Bipartite partititions" width=\textwidth
1.1571 + ///
1.1572 + /// \param graph The undirected graph.
1.1573 + /// \retval partMap A writable node map of \c bool (or convertible) value
1.1574 + /// type. The values will be set to \c true for one component and
1.1575 + /// \c false for the other one.
1.1576 + /// \return \c true if the graph is bipartite, \c false otherwise.
1.1577 + ///
1.1578 + /// \see bipartite()
1.1579 + template<typename Graph, typename NodeMap>
1.1580 + bool bipartitePartitions(const Graph &graph, NodeMap &partMap){
1.1581 + using namespace _connectivity_bits;
1.1582 +
1.1583 + checkConcept<concepts::Graph, Graph>();
1.1584 + checkConcept<concepts::WriteMap<typename Graph::Node, bool>, NodeMap>();
1.1585 +
1.1586 + typedef typename Graph::Node Node;
1.1587 + typedef typename Graph::NodeIt NodeIt;
1.1588 + typedef typename Graph::ArcIt ArcIt;
1.1589 +
1.1590 + bool bipartite = true;
1.1591 +
1.1592 + BipartitePartitionsVisitor<Graph, NodeMap>
1.1593 + visitor(graph, partMap, bipartite);
1.1594 + BfsVisit<Graph, BipartitePartitionsVisitor<Graph, NodeMap> >
1.1595 + bfs(graph, visitor);
1.1596 + bfs.init();
1.1597 + for(NodeIt it(graph); it != INVALID; ++it) {
1.1598 + if(!bfs.reached(it)){
1.1599 + bfs.addSource(it);
1.1600 + while (!bfs.emptyQueue()) {
1.1601 + bfs.processNextNode();
1.1602 + if (!bipartite) return false;
1.1603 + }
1.1604 + }
1.1605 + }
1.1606 + return true;
1.1607 + }
1.1608 +
1.1609 + /// \ingroup graph_properties
1.1610 + ///
1.1611 + /// \brief Check whether the given graph contains no loop arcs/edges.
1.1612 + ///
1.1613 + /// This function returns \c true if there are no loop arcs/edges in
1.1614 + /// the given graph. It works for both directed and undirected graphs.
1.1615 + template <typename Graph>
1.1616 + bool loopFree(const Graph& graph) {
1.1617 + for (typename Graph::ArcIt it(graph); it != INVALID; ++it) {
1.1618 + if (graph.source(it) == graph.target(it)) return false;
1.1619 + }
1.1620 + return true;
1.1621 + }
1.1622 +
1.1623 + /// \ingroup graph_properties
1.1624 + ///
1.1625 + /// \brief Check whether the given graph contains no parallel arcs/edges.
1.1626 + ///
1.1627 + /// This function returns \c true if there are no parallel arcs/edges in
1.1628 + /// the given graph. It works for both directed and undirected graphs.
1.1629 + template <typename Graph>
1.1630 + bool parallelFree(const Graph& graph) {
1.1631 + typename Graph::template NodeMap<int> reached(graph, 0);
1.1632 + int cnt = 1;
1.1633 + for (typename Graph::NodeIt n(graph); n != INVALID; ++n) {
1.1634 + for (typename Graph::OutArcIt a(graph, n); a != INVALID; ++a) {
1.1635 + if (reached[graph.target(a)] == cnt) return false;
1.1636 + reached[graph.target(a)] = cnt;
1.1637 + }
1.1638 + ++cnt;
1.1639 + }
1.1640 + return true;
1.1641 + }
1.1642 +
1.1643 + /// \ingroup graph_properties
1.1644 + ///
1.1645 + /// \brief Check whether the given graph is simple.
1.1646 + ///
1.1647 + /// This function returns \c true if the given graph is simple, i.e.
1.1648 + /// it contains no loop arcs/edges and no parallel arcs/edges.
1.1649 + /// The function works for both directed and undirected graphs.
1.1650 + /// \see loopFree(), parallelFree()
1.1651 + template <typename Graph>
1.1652 + bool simpleGraph(const Graph& graph) {
1.1653 + typename Graph::template NodeMap<int> reached(graph, 0);
1.1654 + int cnt = 1;
1.1655 + for (typename Graph::NodeIt n(graph); n != INVALID; ++n) {
1.1656 + reached[n] = cnt;
1.1657 + for (typename Graph::OutArcIt a(graph, n); a != INVALID; ++a) {
1.1658 + if (reached[graph.target(a)] == cnt) return false;
1.1659 + reached[graph.target(a)] = cnt;
1.1660 + }
1.1661 + ++cnt;
1.1662 + }
1.1663 + return true;
1.1664 + }
1.1665 +
1.1666 +} //namespace lemon
1.1667 +
1.1668 +#endif //LEMON_CONNECTIVITY_H