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