Connected components, etc...
Based on the dfs visitor interface
1.1 --- a/doc/groups.dox Wed Nov 02 15:22:28 2005 +0000
1.2 +++ b/doc/groups.dox Wed Nov 02 15:23:46 2005 +0000
1.3 @@ -125,6 +125,13 @@
1.4 */
1.5
1.6 /**
1.7 +@defgroup topology Topology related algorithms
1.8 +@ingroup galgs
1.9 +\brief This group describes the algorithms
1.10 +for discover the topology of the graphs.
1.11 +*/
1.12 +
1.13 +/**
1.14 @defgroup exceptions Exceptions
1.15 This group contains the exceptions thrown by LEMON library
1.16 */
2.1 --- a/lemon/topology.h Wed Nov 02 15:22:28 2005 +0000
2.2 +++ b/lemon/topology.h Wed Nov 02 15:23:46 2005 +0000
2.3 @@ -20,49 +20,1208 @@
2.4 #include <lemon/dfs.h>
2.5 #include <lemon/bfs.h>
2.6 #include <lemon/graph_utils.h>
2.7 +#include <lemon/graph_adaptor.h>
2.8 +#include <lemon/maps.h>
2.9
2.10 #include <lemon/concept/graph.h>
2.11 #include <lemon/concept/undir_graph.h>
2.12 #include <lemon/concept_check.h>
2.13
2.14 -/// \ingroup flowalgs
2.15 +#include <lemon/bin_heap.h>
2.16 +#include <lemon/linear_heap.h>
2.17 +
2.18 +#include <stack>
2.19 +#include <functional>
2.20 +
2.21 +/// \ingroup topology
2.22 /// \file
2.23 /// \brief Topology related algorithms
2.24 ///
2.25 /// Topology related algorithms
2.26 -///\todo Place the file contents is the module tree.
2.27
2.28 namespace lemon {
2.29
2.30 + /// \ingroup topology
2.31 + ///
2.32 + /// \brief Check that the given undirected graph is connected.
2.33 + ///
2.34 + /// Check that the given undirected graph connected.
2.35 + /// \param graph The undirected graph.
2.36 + /// \return %True when there is path between any two nodes in the graph.
2.37 + /// \warning The empty graph is not connected.
2.38 + template <typename UndirGraph>
2.39 + bool connected(const UndirGraph& graph) {
2.40 + checkConcept<concept::UndirGraph, UndirGraph>();
2.41 + typedef typename UndirGraph::NodeIt NodeIt;
2.42 + if (NodeIt(graph) == INVALID) return false;
2.43 + Dfs<UndirGraph> dfs(graph);
2.44 + dfs.run(NodeIt(graph));
2.45 + for (NodeIt it(graph); it != INVALID; ++it) {
2.46 + if (!dfs.reached(it)) {
2.47 + return false;
2.48 + }
2.49 + }
2.50 + return true;
2.51 + }
2.52 +
2.53 + /// \ingroup topology
2.54 + ///
2.55 + /// \brief Count the number of connected components of an undirected graph
2.56 + ///
2.57 + /// Count the number of connected components of an undirected graph
2.58 + ///
2.59 + /// \param g The graph. In must be undirected.
2.60 + /// \return The number of components
2.61 + template <typename UndirGraph>
2.62 + int countConnectedComponents(const UndirGraph &graph) {
2.63 + checkConcept<concept::UndirGraph, UndirGraph>();
2.64 + typedef typename UndirGraph::Node Node;
2.65 + typedef typename UndirGraph::Edge Edge;
2.66 +
2.67 + typedef NullMap<Node, Edge> PredMap;
2.68 + typedef NullMap<Node, int> DistMap;
2.69 +
2.70 + int compNum = 0;
2.71 + typename Bfs<UndirGraph>::
2.72 + template DefPredMap<PredMap>::
2.73 + template DefDistMap<DistMap>::
2.74 + Create bfs(graph);
2.75 +
2.76 + PredMap predMap;
2.77 + bfs.predMap(predMap);
2.78 +
2.79 + DistMap distMap;
2.80 + bfs.distMap(distMap);
2.81 +
2.82 + bfs.init();
2.83 + for(typename UndirGraph::NodeIt n(graph); n != INVALID; ++n) {
2.84 + if (!bfs.reached(n)) {
2.85 + bfs.addSource(n);
2.86 + bfs.start();
2.87 + ++compNum;
2.88 + }
2.89 + }
2.90 + return compNum;
2.91 + }
2.92 +
2.93 + /// \ingroup topology
2.94 + ///
2.95 + /// \brief Find the connected components of an undirected graph
2.96 + ///
2.97 + /// Find the connected components of an undirected graph.
2.98 + ///
2.99 + /// \param g The graph. In must be undirected.
2.100 + /// \retval comp A writable node map. The values will be set from 0 to
2.101 + /// the number of the connected components minus one. Each values of the map
2.102 + /// will be set exactly once, the values of a certain component will be
2.103 + /// set continuously.
2.104 + /// \return The number of components
2.105 + template <class UndirGraph, class NodeMap>
2.106 + int connectedComponents(const UndirGraph &graph, NodeMap &compMap) {
2.107 + checkConcept<concept::UndirGraph, UndirGraph>();
2.108 + typedef typename UndirGraph::Node Node;
2.109 + typedef typename UndirGraph::Edge Edge;
2.110 + checkConcept<concept::WriteMap<Node, int>, NodeMap>();
2.111 +
2.112 + typedef NullMap<Node, Edge> PredMap;
2.113 + typedef NullMap<Node, int> DistMap;
2.114 +
2.115 + int compNum = 0;
2.116 + typename Bfs<UndirGraph>::
2.117 + template DefPredMap<PredMap>::
2.118 + template DefDistMap<DistMap>::
2.119 + Create bfs(graph);
2.120 +
2.121 + PredMap predMap;
2.122 + bfs.predMap(predMap);
2.123 +
2.124 + DistMap distMap;
2.125 + bfs.distMap(distMap);
2.126 +
2.127 + bfs.init();
2.128 + for(typename UndirGraph::NodeIt n(graph); n != INVALID; ++n) {
2.129 + if(!bfs.reached(n)) {
2.130 + bfs.addSource(n);
2.131 + while (!bfs.emptyQueue()) {
2.132 + compMap.set(bfs.nextNode(), compNum);
2.133 + bfs.processNextNode();
2.134 + }
2.135 + ++compNum;
2.136 + }
2.137 + }
2.138 + return compNum;
2.139 + }
2.140 +
2.141 + namespace _topology_bits {
2.142 +
2.143 + template <typename Graph, typename Iterator >
2.144 + struct LeaveOrderVisitor : public DfsVisitor<Graph> {
2.145 + public:
2.146 + typedef typename Graph::Node Node;
2.147 + LeaveOrderVisitor(Iterator it) : _it(it) {}
2.148 +
2.149 + void leave(const Node& node) {
2.150 + *(_it++) = node;
2.151 + }
2.152 +
2.153 + private:
2.154 + Iterator _it;
2.155 + };
2.156 +
2.157 + template <typename Graph, typename Map>
2.158 + struct FillMapVisitor : public DfsVisitor<Graph> {
2.159 + public:
2.160 + typedef typename Graph::Node Node;
2.161 + typedef typename Map::Value Value;
2.162 +
2.163 + FillMapVisitor(Map& map, Value& value)
2.164 + : _map(map), _value(value) {}
2.165 +
2.166 + void reach(const Node& node) {
2.167 + _map.set(node, _value);
2.168 + }
2.169 + private:
2.170 + Map& _map;
2.171 + Value& _value;
2.172 + };
2.173 +
2.174 + template <typename Graph, typename EdgeMap>
2.175 + struct StronglyConnectedCutEdgesVisitor : public DfsVisitor<Graph> {
2.176 + public:
2.177 + typedef typename Graph::Node Node;
2.178 + typedef typename Graph::Edge Edge;
2.179 +
2.180 + StronglyConnectedCutEdgesVisitor(const Graph& graph, EdgeMap& cutMap,
2.181 + int& cutNum)
2.182 + : _graph(graph), _cutMap(cutMap), _cutNum(cutNum),
2.183 + _compMap(graph), _num(0) {
2.184 + }
2.185 +
2.186 + void stop(const Node&) {
2.187 + ++_num;
2.188 + }
2.189 +
2.190 + void reach(const Node& node) {
2.191 + _compMap.set(node, _num);
2.192 + }
2.193 +
2.194 + void examine(const Edge& edge) {
2.195 + if (_compMap[_graph.source(edge)] != _compMap[_graph.target(edge)]) {
2.196 + _cutMap.set(edge, true);
2.197 + ++_cutNum;
2.198 + }
2.199 + }
2.200 + private:
2.201 + const Graph& _graph;
2.202 + EdgeMap& _cutMap;
2.203 + int& _cutNum;
2.204 +
2.205 + typename Graph::template NodeMap<int> _compMap;
2.206 + int _num;
2.207 + };
2.208 +
2.209 + }
2.210 +
2.211 +
2.212 + /// \ingroup topology
2.213 + ///
2.214 + /// \brief Check that the given directed graph is strongly connected.
2.215 + ///
2.216 + /// Check that the given directed graph is strongly connected. The
2.217 + /// graph is strongly connected when any two nodes of the graph are
2.218 + /// connected with directed pathes in both direction.
2.219 + /// \return %False when the graph is not strongly connected.
2.220 + /// \see connected
2.221 + ///
2.222 + /// \waning Empty graph is not strongly connected.
2.223 + template <typename Graph>
2.224 + bool stronglyConnected(const Graph& graph) {
2.225 + checkConcept<concept::StaticGraph, Graph>();
2.226 + if (NodeIt(graph) == INVALID) return false;
2.227 +
2.228 + typedef typename Graph::Node Node;
2.229 + typedef typename Graph::NodeIt NodeIt;
2.230 +
2.231 + using namespace _topology_bits;
2.232 +
2.233 + typedef DfsVisitor<Graph> Visitor;
2.234 + Visitor visitor;
2.235 +
2.236 + DfsVisit<Graph, Visitor> dfs(graph, visitor);
2.237 + dfs.init();
2.238 + dfs.addSource(NodeIt(graph));
2.239 + dfs.start();
2.240 +
2.241 + for (NodeIt it(graph); it != INVALID; ++it) {
2.242 + if (!dfs.reached(it)) {
2.243 + return false;
2.244 + }
2.245 + }
2.246 +
2.247 + typedef RevGraphAdaptor<const Graph> RGraph;
2.248 + RGraph rgraph(graph);
2.249 +
2.250 + typedef DfsVisitor<Graph> RVisitor;
2.251 + RVisitor rvisitor;
2.252 +
2.253 + DfsVisit<RGraph, RVisitor> rdfs(rgraph, rvisitor);
2.254 + rdfs.init();
2.255 + rdfs.addSource(NodeIt(graph));
2.256 + rdfs.start();
2.257 +
2.258 + for (NodeIt it(graph); it != INVALID; ++it) {
2.259 + if (!rdfs.reached(it)) {
2.260 + return false;
2.261 + }
2.262 + }
2.263 +
2.264 + return true;
2.265 + }
2.266 +
2.267 + /// \ingroup topology
2.268 + ///
2.269 + /// \brief Count the strongly connected components of a directed graph
2.270 + ///
2.271 + /// Count the strongly connected components of a directed graph.
2.272 + /// The strongly connected components are the classes of an equivalence
2.273 + /// relation on the nodes of the graph. Two nodes are connected with
2.274 + /// directed paths in both direction.
2.275 + ///
2.276 + /// \param g The graph.
2.277 + /// \return The number of components
2.278 + template <typename Graph>
2.279 + int countStronglyConnectedComponents(const Graph& graph) {
2.280 + checkConcept<concept::StaticGraph, Graph>();
2.281 +
2.282 + using namespace _topology_bits;
2.283 +
2.284 + typedef typename Graph::Node Node;
2.285 + typedef typename Graph::Edge Edge;
2.286 + typedef typename Graph::NodeIt NodeIt;
2.287 + typedef typename Graph::EdgeIt EdgeIt;
2.288 +
2.289 + typedef std::vector<Node> Container;
2.290 + typedef typename Container::iterator Iterator;
2.291 +
2.292 + Container nodes(countNodes(graph));
2.293 + typedef LeaveOrderVisitor<Graph, Iterator> Visitor;
2.294 + Visitor visitor(nodes.begin());
2.295 +
2.296 + DfsVisit<Graph, Visitor> dfs(graph, visitor);
2.297 + dfs.init();
2.298 + for (NodeIt it(graph); it != INVALID; ++it) {
2.299 + if (!dfs.reached(it)) {
2.300 + dfs.addSource(it);
2.301 + dfs.start();
2.302 + }
2.303 + }
2.304 +
2.305 + typedef typename Container::reverse_iterator RIterator;
2.306 + typedef RevGraphAdaptor<const Graph> RGraph;
2.307 +
2.308 + RGraph rgraph(graph);
2.309 +
2.310 + typedef DfsVisitor<Graph> RVisitor;
2.311 + RVisitor rvisitor;
2.312 +
2.313 + DfsVisit<RGraph, RVisitor> rdfs(rgraph, rvisitor);
2.314 +
2.315 + int compNum = 0;
2.316 +
2.317 + rdfs.init();
2.318 + for (RIterator it = nodes.rbegin(); it != nodes.rend(); ++it) {
2.319 + if (!rdfs.reached(*it)) {
2.320 + rdfs.addSource(*it);
2.321 + rdfs.start();
2.322 + ++compNum;
2.323 + }
2.324 + }
2.325 + return compNum;
2.326 + }
2.327 +
2.328 + /// \ingroup topology
2.329 + ///
2.330 + /// \brief Find the strongly connected components of a directed graph
2.331 + ///
2.332 + /// Find the strongly connected components of a directed graph.
2.333 + /// The strongly connected components are the classes of an equivalence
2.334 + /// relation on the nodes of the graph. Two nodes are in relationship
2.335 + /// when there are directed paths between them in both direction.
2.336 + ///
2.337 + /// \param g The graph.
2.338 + /// \retval comp A writable node map. The values will be set from 0 to
2.339 + /// the number of the strongly connected components minus one. Each values
2.340 + /// of the map will be set exactly once, the values of a certain component
2.341 + /// will be set continuously.
2.342 + /// \return The number of components
2.343 + template <typename Graph, typename NodeMap>
2.344 + int stronglyConnectedComponents(const Graph& graph, NodeMap& compMap) {
2.345 + checkConcept<concept::StaticGraph, Graph>();
2.346 + typedef typename Graph::Node Node;
2.347 + typedef typename Graph::NodeIt NodeIt;
2.348 + checkConcept<concept::WriteMap<Node, int>, NodeMap>();
2.349 +
2.350 + using namespace _topology_bits;
2.351 +
2.352 + typedef std::vector<Node> Container;
2.353 + typedef typename Container::iterator Iterator;
2.354 +
2.355 + Container nodes(countNodes(graph));
2.356 + typedef LeaveOrderVisitor<Graph, Iterator> Visitor;
2.357 + Visitor visitor(nodes.begin());
2.358 +
2.359 + DfsVisit<Graph, Visitor> dfs(graph, visitor);
2.360 + dfs.init();
2.361 + for (NodeIt it(graph); it != INVALID; ++it) {
2.362 + if (!dfs.reached(it)) {
2.363 + dfs.addSource(it);
2.364 + dfs.start();
2.365 + }
2.366 + }
2.367 +
2.368 + typedef typename Container::reverse_iterator RIterator;
2.369 + typedef RevGraphAdaptor<const Graph> RGraph;
2.370 +
2.371 + RGraph rgraph(graph);
2.372 +
2.373 + int compNum = 0;
2.374 +
2.375 + typedef FillMapVisitor<RGraph, NodeMap> RVisitor;
2.376 + RVisitor rvisitor(compMap, compNum);
2.377 +
2.378 + DfsVisit<RGraph, RVisitor> rdfs(rgraph, rvisitor);
2.379 +
2.380 + rdfs.init();
2.381 + for (RIterator it = nodes.rbegin(); it != nodes.rend(); ++it) {
2.382 + if (!rdfs.reached(*it)) {
2.383 + rdfs.addSource(*it);
2.384 + rdfs.start();
2.385 + ++compNum;
2.386 + }
2.387 + }
2.388 + return compNum;
2.389 + }
2.390 +
2.391 + /// \ingroup topology
2.392 + ///
2.393 + /// \brief Find the cut edges of the strongly connected components.
2.394 + ///
2.395 + /// Find the cut edges of the strongly connected components.
2.396 + /// The strongly connected components are the classes of an equivalence
2.397 + /// relation on the nodes of the graph. Two nodes are in relationship
2.398 + /// when there are directed paths between them in both direction.
2.399 + /// The strongly connected components are separated by the cut edges.
2.400 + ///
2.401 + /// \param g The graph.
2.402 + /// \retval comp A writable edge map. The values will be set true when
2.403 + /// the edge is cut edge otherwise false.
2.404 + ///
2.405 + /// \return The number of cut edges
2.406 + template <typename Graph, typename EdgeMap>
2.407 + int stronglyConnectedCutEdges(const Graph& graph, EdgeMap& cutMap) {
2.408 + checkConcept<concept::StaticGraph, Graph>();
2.409 + typedef typename Graph::Node Node;
2.410 + typedef typename Graph::Edge Edge;
2.411 + typedef typename Graph::NodeIt NodeIt;
2.412 + checkConcept<concept::WriteMap<Edge, bool>, EdgeMap>();
2.413 +
2.414 + using namespace _topology_bits;
2.415 +
2.416 + typedef std::vector<Node> Container;
2.417 + typedef typename Container::iterator Iterator;
2.418 +
2.419 + Container nodes(countNodes(graph));
2.420 + typedef LeaveOrderVisitor<Graph, Iterator> Visitor;
2.421 + Visitor visitor(nodes.begin());
2.422 +
2.423 + DfsVisit<Graph, Visitor> dfs(graph, visitor);
2.424 + dfs.init();
2.425 + for (NodeIt it(graph); it != INVALID; ++it) {
2.426 + if (!dfs.reached(it)) {
2.427 + dfs.addSource(it);
2.428 + dfs.start();
2.429 + }
2.430 + }
2.431 +
2.432 + typedef typename Container::reverse_iterator RIterator;
2.433 + typedef RevGraphAdaptor<const Graph> RGraph;
2.434 +
2.435 + RGraph rgraph(graph);
2.436 +
2.437 + int cutNum = 0;
2.438 +
2.439 + typedef StronglyConnectedCutEdgesVisitor<RGraph, EdgeMap> RVisitor;
2.440 + RVisitor rvisitor(rgraph, cutMap, cutNum);
2.441 +
2.442 + DfsVisit<RGraph, RVisitor> rdfs(rgraph, rvisitor);
2.443 +
2.444 + rdfs.init();
2.445 + for (RIterator it = nodes.rbegin(); it != nodes.rend(); ++it) {
2.446 + if (!rdfs.reached(*it)) {
2.447 + rdfs.addSource(*it);
2.448 + rdfs.start();
2.449 + }
2.450 + }
2.451 + return cutNum;
2.452 + }
2.453 +
2.454 namespace _topology_bits {
2.455
2.456 - template <typename NodeMap>
2.457 - class BackCounterMap {
2.458 + template <typename Graph>
2.459 + class CountNodeBiconnectedComponentsVisitor : public DfsVisitor<Graph> {
2.460 public:
2.461 - BackCounterMap(NodeMap& _nodeMap, int _counter)
2.462 - : nodeMap(_nodeMap), counter(_counter) {}
2.463 + typedef typename Graph::Node Node;
2.464 + typedef typename Graph::Edge Edge;
2.465 + typedef typename Graph::UndirEdge UndirEdge;
2.466
2.467 - void set(typename NodeMap::Key key, bool val) {
2.468 - if (val) {
2.469 - nodeMap.set(key, --counter);
2.470 - } else {
2.471 - nodeMap.set(key, -1);
2.472 + CountNodeBiconnectedComponentsVisitor(const Graph& graph, int &compNum)
2.473 + : _graph(graph), _compNum(compNum),
2.474 + _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
2.475 +
2.476 + void start(const Node& node) {
2.477 + _predMap.set(node, INVALID);
2.478 + }
2.479 +
2.480 + void reach(const Node& node) {
2.481 + _numMap.set(node, _num);
2.482 + _retMap.set(node, _num);
2.483 + ++_num;
2.484 + }
2.485 +
2.486 + void discover(const Edge& edge) {
2.487 + _predMap.set(_graph.target(edge), _graph.source(edge));
2.488 + }
2.489 +
2.490 + void examine(const Edge& edge) {
2.491 + if (_graph.source(edge) == _graph.target(edge) &&
2.492 + _graph.direction(edge)) {
2.493 + ++_compNum;
2.494 + return;
2.495 + }
2.496 + if (_predMap[_graph.source(edge)] == _graph.target(edge)) {
2.497 + return;
2.498 + }
2.499 + if (_retMap[_graph.source(edge)] > _numMap[_graph.target(edge)]) {
2.500 + _retMap.set(_graph.source(edge), _numMap[_graph.target(edge)]);
2.501 }
2.502 }
2.503
2.504 - bool operator[](typename NodeMap::Key key) const {
2.505 - return nodeMap[key] != -1;
2.506 + void backtrack(const Edge& edge) {
2.507 + if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
2.508 + _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
2.509 + }
2.510 + if (_numMap[_graph.source(edge)] <= _retMap[_graph.target(edge)]) {
2.511 + ++_compNum;
2.512 + }
2.513 + }
2.514 +
2.515 + private:
2.516 + const Graph& _graph;
2.517 + int& _compNum;
2.518 +
2.519 + typename Graph::template NodeMap<int> _numMap;
2.520 + typename Graph::template NodeMap<int> _retMap;
2.521 + typename Graph::template NodeMap<Node> _predMap;
2.522 + int _num;
2.523 + };
2.524 +
2.525 + template <typename Graph, typename EdgeMap>
2.526 + class NodeBiconnectedComponentsVisitor : public DfsVisitor<Graph> {
2.527 + public:
2.528 + typedef typename Graph::Node Node;
2.529 + typedef typename Graph::Edge Edge;
2.530 + typedef typename Graph::UndirEdge UndirEdge;
2.531 +
2.532 + NodeBiconnectedComponentsVisitor(const Graph& graph,
2.533 + EdgeMap& compMap, int &compNum)
2.534 + : _graph(graph), _compMap(compMap), _compNum(compNum),
2.535 + _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
2.536 +
2.537 + void start(const Node& node) {
2.538 + _predMap.set(node, INVALID);
2.539 + }
2.540 +
2.541 + void reach(const Node& node) {
2.542 + _numMap.set(node, _num);
2.543 + _retMap.set(node, _num);
2.544 + ++_num;
2.545 + }
2.546 +
2.547 + void discover(const Edge& edge) {
2.548 + Node target = _graph.target(edge);
2.549 + _predMap.set(target, edge);
2.550 + _edgeStack.push(edge);
2.551 + }
2.552 +
2.553 + void examine(const Edge& edge) {
2.554 + Node source = _graph.source(edge);
2.555 + Node target = _graph.target(edge);
2.556 + if (source == target && _graph.direction(edge)) {
2.557 + _compMap.set(edge, _compNum);
2.558 + ++_compNum;
2.559 + return;
2.560 + }
2.561 + if (_numMap[target] < _numMap[source]) {
2.562 + if (_predMap[source] != _graph.oppositeEdge(edge)) {
2.563 + _edgeStack.push(edge);
2.564 + }
2.565 + }
2.566 + if (_predMap[source] != INVALID &&
2.567 + target == _graph.source(_predMap[source])) {
2.568 + return;
2.569 + }
2.570 + if (_retMap[source] > _numMap[target]) {
2.571 + _retMap.set(source, _numMap[target]);
2.572 + }
2.573 + }
2.574 +
2.575 + void backtrack(const Edge& edge) {
2.576 + Node source = _graph.source(edge);
2.577 + Node target = _graph.target(edge);
2.578 + if (_retMap[source] > _retMap[target]) {
2.579 + _retMap.set(source, _retMap[target]);
2.580 + }
2.581 + if (_numMap[source] <= _retMap[target]) {
2.582 + while (_edgeStack.top() != edge) {
2.583 + _compMap.set(_edgeStack.top(), _compNum);
2.584 + _edgeStack.pop();
2.585 + }
2.586 + _compMap.set(edge, _compNum);
2.587 + _edgeStack.pop();
2.588 + ++_compNum;
2.589 + }
2.590 + }
2.591 +
2.592 + private:
2.593 + const Graph& _graph;
2.594 + EdgeMap& _compMap;
2.595 + int& _compNum;
2.596 +
2.597 + typename Graph::template NodeMap<int> _numMap;
2.598 + typename Graph::template NodeMap<int> _retMap;
2.599 + typename Graph::template NodeMap<Edge> _predMap;
2.600 + std::stack<UndirEdge> _edgeStack;
2.601 + int _num;
2.602 + };
2.603 +
2.604 +
2.605 + template <typename Graph, typename NodeMap>
2.606 + class NodeBiconnectedCutNodesVisitor : public DfsVisitor<Graph> {
2.607 + public:
2.608 + typedef typename Graph::Node Node;
2.609 + typedef typename Graph::Edge Edge;
2.610 + typedef typename Graph::UndirEdge UndirEdge;
2.611 +
2.612 + NodeBiconnectedCutNodesVisitor(const Graph& graph, NodeMap& cutMap,
2.613 + int& cutNum)
2.614 + : _graph(graph), _cutMap(cutMap), _cutNum(cutNum),
2.615 + _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
2.616 +
2.617 + void start(const Node& node) {
2.618 + _predMap.set(node, INVALID);
2.619 + rootCut = false;
2.620 + }
2.621 +
2.622 + void reach(const Node& node) {
2.623 + _numMap.set(node, _num);
2.624 + _retMap.set(node, _num);
2.625 + ++_num;
2.626 + }
2.627 +
2.628 + void discover(const Edge& edge) {
2.629 + _predMap.set(_graph.target(edge), _graph.source(edge));
2.630 + }
2.631 +
2.632 + void examine(const Edge& edge) {
2.633 + if (_graph.source(edge) == _graph.target(edge) &&
2.634 + _graph.direction(edge)) {
2.635 + if (!_cutMap[_graph.source(edge)]) {
2.636 + _cutMap.set(_graph.source(edge), true);
2.637 + ++_cutNum;
2.638 + }
2.639 + return;
2.640 + }
2.641 + if (_predMap[_graph.source(edge)] == _graph.target(edge)) return;
2.642 + if (_retMap[_graph.source(edge)] > _numMap[_graph.target(edge)]) {
2.643 + _retMap.set(_graph.source(edge), _numMap[_graph.target(edge)]);
2.644 + }
2.645 + }
2.646 +
2.647 + void backtrack(const Edge& edge) {
2.648 + if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
2.649 + _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
2.650 + }
2.651 + if (_numMap[_graph.source(edge)] <= _retMap[_graph.target(edge)]) {
2.652 + if (_predMap[_graph.source(edge)] != INVALID) {
2.653 + if (!_cutMap[_graph.source(edge)]) {
2.654 + _cutMap.set(_graph.source(edge), true);
2.655 + ++_cutNum;
2.656 + }
2.657 + } else if (rootCut) {
2.658 + if (!_cutMap[_graph.source(edge)]) {
2.659 + _cutMap.set(_graph.source(edge), true);
2.660 + ++_cutNum;
2.661 + }
2.662 + } else {
2.663 + rootCut = true;
2.664 + }
2.665 + }
2.666 + }
2.667 +
2.668 + private:
2.669 + const Graph& _graph;
2.670 + NodeMap& _cutMap;
2.671 + int& _cutNum;
2.672 +
2.673 + typename Graph::template NodeMap<int> _numMap;
2.674 + typename Graph::template NodeMap<int> _retMap;
2.675 + typename Graph::template NodeMap<Node> _predMap;
2.676 + std::stack<UndirEdge> _edgeStack;
2.677 + int _num;
2.678 + bool rootCut;
2.679 + };
2.680 +
2.681 + }
2.682 +
2.683 + template <typename UndirGraph>
2.684 + int countNodeBiconnectedComponents(const UndirGraph& graph);
2.685 +
2.686 + /// \ingroup topology
2.687 + ///
2.688 + /// \brief Checks the graph is node biconnected.
2.689 + ///
2.690 + /// This function checks that the undirected graph is node biconnected
2.691 + /// graph. The graph is node biconnected if any two undirected edge is
2.692 + /// on same circle.
2.693 + ///
2.694 + /// \param graph The graph.
2.695 + /// \return %True when the graph node biconnected.
2.696 + /// \todo Make it faster.
2.697 + template <typename UndirGraph>
2.698 + bool nodeBiconnected(const UndirGraph& graph) {
2.699 + return countNodeBiconnectedComponents(graph) == 1;
2.700 + }
2.701 +
2.702 + /// \ingroup topology
2.703 + ///
2.704 + /// \brief Count the biconnected components.
2.705 + ///
2.706 + /// This function finds the node biconnected components in an undirected
2.707 + /// graph. The biconnected components are the classes of an equivalence
2.708 + /// relation on the undirected edges. Two undirected edge is in relationship
2.709 + /// when they are on same circle.
2.710 + ///
2.711 + /// \param graph The graph.
2.712 + /// \return The number of components.
2.713 + template <typename UndirGraph>
2.714 + int countNodeBiconnectedComponents(const UndirGraph& graph) {
2.715 + checkConcept<concept::UndirGraph, UndirGraph>();
2.716 + typedef typename UndirGraph::NodeIt NodeIt;
2.717 +
2.718 + using namespace _topology_bits;
2.719 +
2.720 + typedef CountNodeBiconnectedComponentsVisitor<UndirGraph> Visitor;
2.721 +
2.722 + int compNum = 0;
2.723 + Visitor visitor(graph, compNum);
2.724 +
2.725 + DfsVisit<UndirGraph, Visitor> dfs(graph, visitor);
2.726 + dfs.init();
2.727 +
2.728 + for (NodeIt it(graph); it != INVALID; ++it) {
2.729 + if (!dfs.reached(it)) {
2.730 + dfs.addSource(it);
2.731 + dfs.start();
2.732 + }
2.733 + }
2.734 + return compNum;
2.735 + }
2.736 +
2.737 + /// \ingroup topology
2.738 + ///
2.739 + /// \brief Find the node biconnected components.
2.740 + ///
2.741 + /// This function finds the node biconnected components in an undirected
2.742 + /// graph. The node biconnected components are the classes of an equivalence
2.743 + /// relation on the undirected edges. Two undirected edge are in relationship
2.744 + /// when they are on same circle.
2.745 + ///
2.746 + /// \param graph The graph.
2.747 + /// \retval comp A writable undir edge map. The values will be set from 0 to
2.748 + /// the number of the biconnected components minus one. Each values
2.749 + /// of the map will be set exactly once, the values of a certain component
2.750 + /// will be set continuously.
2.751 + /// \return The number of components.
2.752 + template <typename UndirGraph, typename UndirEdgeMap>
2.753 + int nodeBiconnectedComponents(const UndirGraph& graph,
2.754 + UndirEdgeMap& compMap) {
2.755 + checkConcept<concept::UndirGraph, UndirGraph>();
2.756 + typedef typename UndirGraph::NodeIt NodeIt;
2.757 + typedef typename UndirGraph::UndirEdge UndirEdge;
2.758 + checkConcept<concept::WriteMap<UndirEdge, int>, UndirEdgeMap>();
2.759 +
2.760 + using namespace _topology_bits;
2.761 +
2.762 + typedef NodeBiconnectedComponentsVisitor<UndirGraph, UndirEdgeMap> Visitor;
2.763 +
2.764 + int compNum = 0;
2.765 + Visitor visitor(graph, compMap, compNum);
2.766 +
2.767 + DfsVisit<UndirGraph, Visitor> dfs(graph, visitor);
2.768 + dfs.init();
2.769 +
2.770 + for (NodeIt it(graph); it != INVALID; ++it) {
2.771 + if (!dfs.reached(it)) {
2.772 + dfs.addSource(it);
2.773 + dfs.start();
2.774 + }
2.775 + }
2.776 + return compNum;
2.777 + }
2.778 +
2.779 + /// \ingroup topology
2.780 + ///
2.781 + /// \brief Find the node biconnected cut nodes.
2.782 + ///
2.783 + /// This function finds the node biconnected cut nodes in an undirected
2.784 + /// graph. The node biconnected components are the classes of an equivalence
2.785 + /// relation on the undirected edges. Two undirected edges are in
2.786 + /// relationship when they are on same circle. The biconnected components
2.787 + /// are separted by nodes which are the cut nodes of the components.
2.788 + ///
2.789 + /// \param graph The graph.
2.790 + /// \retval comp A writable edge map. The values will be set true when
2.791 + /// the node separate two or more components.
2.792 + /// \return The number of the cut nodes.
2.793 + template <typename UndirGraph, typename NodeMap>
2.794 + int nodeBiconnectedCutNodes(const UndirGraph& graph, NodeMap& cutMap) {
2.795 + checkConcept<concept::UndirGraph, UndirGraph>();
2.796 + typedef typename UndirGraph::Node Node;
2.797 + typedef typename UndirGraph::NodeIt NodeIt;
2.798 + checkConcept<concept::WriteMap<Node, bool>, NodeMap>();
2.799 +
2.800 + using namespace _topology_bits;
2.801 +
2.802 + typedef NodeBiconnectedCutNodesVisitor<UndirGraph, NodeMap> Visitor;
2.803 +
2.804 + int cutNum = 0;
2.805 + Visitor visitor(graph, cutMap, cutNum);
2.806 +
2.807 + DfsVisit<UndirGraph, Visitor> dfs(graph, visitor);
2.808 + dfs.init();
2.809 +
2.810 + for (NodeIt it(graph); it != INVALID; ++it) {
2.811 + if (!dfs.reached(it)) {
2.812 + dfs.addSource(it);
2.813 + dfs.start();
2.814 + }
2.815 + }
2.816 + return cutNum;
2.817 + }
2.818 +
2.819 + namespace _topology_bits {
2.820 +
2.821 + template <typename Graph>
2.822 + class CountEdgeBiconnectedComponentsVisitor : public DfsVisitor<Graph> {
2.823 + public:
2.824 + typedef typename Graph::Node Node;
2.825 + typedef typename Graph::Edge Edge;
2.826 + typedef typename Graph::UndirEdge UndirEdge;
2.827 +
2.828 + CountEdgeBiconnectedComponentsVisitor(const Graph& graph, int &compNum)
2.829 + : _graph(graph), _compNum(compNum),
2.830 + _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
2.831 +
2.832 + void start(const Node& node) {
2.833 + _predMap.set(node, INVALID);
2.834 + }
2.835 +
2.836 + void reach(const Node& node) {
2.837 + _numMap.set(node, _num);
2.838 + _retMap.set(node, _num);
2.839 + ++_num;
2.840 + }
2.841 +
2.842 + void leave(const Node& node) {
2.843 + if (_numMap[node] <= _retMap[node]) {
2.844 + ++_compNum;
2.845 + }
2.846 + }
2.847 +
2.848 + void discover(const Edge& edge) {
2.849 + _predMap.set(_graph.target(edge), edge);
2.850 + }
2.851 +
2.852 + void examine(const Edge& edge) {
2.853 + if (_predMap[_graph.source(edge)] == _graph.oppositeEdge(edge)) {
2.854 + return;
2.855 + }
2.856 + if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
2.857 + _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
2.858 + }
2.859 + }
2.860 +
2.861 + void backtrack(const Edge& edge) {
2.862 + if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
2.863 + _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
2.864 + }
2.865 + }
2.866 +
2.867 + private:
2.868 + const Graph& _graph;
2.869 + int& _compNum;
2.870 +
2.871 + typename Graph::template NodeMap<int> _numMap;
2.872 + typename Graph::template NodeMap<int> _retMap;
2.873 + typename Graph::template NodeMap<Edge> _predMap;
2.874 + int _num;
2.875 + };
2.876 +
2.877 + template <typename Graph, typename NodeMap>
2.878 + class EdgeBiconnectedComponentsVisitor : public DfsVisitor<Graph> {
2.879 + public:
2.880 + typedef typename Graph::Node Node;
2.881 + typedef typename Graph::Edge Edge;
2.882 + typedef typename Graph::UndirEdge UndirEdge;
2.883 +
2.884 + EdgeBiconnectedComponentsVisitor(const Graph& graph,
2.885 + NodeMap& compMap, int &compNum)
2.886 + : _graph(graph), _compMap(compMap), _compNum(compNum),
2.887 + _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
2.888 +
2.889 + void start(const Node& node) {
2.890 + _predMap.set(node, INVALID);
2.891 + }
2.892 +
2.893 + void reach(const Node& node) {
2.894 + _numMap.set(node, _num);
2.895 + _retMap.set(node, _num);
2.896 + _nodeStack.push(node);
2.897 + ++_num;
2.898 + }
2.899 +
2.900 + void leave(const Node& node) {
2.901 + if (_numMap[node] <= _retMap[node]) {
2.902 + while (_nodeStack.top() != node) {
2.903 + _compMap.set(_nodeStack.top(), _compNum);
2.904 + _nodeStack.pop();
2.905 + }
2.906 + _compMap.set(node, _compNum);
2.907 + _nodeStack.pop();
2.908 + ++_compNum;
2.909 + }
2.910 + }
2.911 +
2.912 + void discover(const Edge& edge) {
2.913 + _predMap.set(_graph.target(edge), edge);
2.914 + }
2.915 +
2.916 + void examine(const Edge& edge) {
2.917 + if (_predMap[_graph.source(edge)] == _graph.oppositeEdge(edge)) {
2.918 + return;
2.919 + }
2.920 + if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
2.921 + _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
2.922 + }
2.923 + }
2.924 +
2.925 + void backtrack(const Edge& edge) {
2.926 + if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
2.927 + _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
2.928 + }
2.929 + }
2.930 +
2.931 + private:
2.932 + const Graph& _graph;
2.933 + NodeMap& _compMap;
2.934 + int& _compNum;
2.935 +
2.936 + typename Graph::template NodeMap<int> _numMap;
2.937 + typename Graph::template NodeMap<int> _retMap;
2.938 + typename Graph::template NodeMap<Edge> _predMap;
2.939 + std::stack<Node> _nodeStack;
2.940 + int _num;
2.941 + };
2.942 +
2.943 +
2.944 + template <typename Graph, typename EdgeMap>
2.945 + class EdgeBiconnectedCutEdgesVisitor : public DfsVisitor<Graph> {
2.946 + public:
2.947 + typedef typename Graph::Node Node;
2.948 + typedef typename Graph::Edge Edge;
2.949 + typedef typename Graph::UndirEdge UndirEdge;
2.950 +
2.951 + EdgeBiconnectedCutEdgesVisitor(const Graph& graph,
2.952 + EdgeMap& cutMap, int &cutNum)
2.953 + : _graph(graph), _cutMap(cutMap), _cutNum(cutNum),
2.954 + _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
2.955 +
2.956 + void start(const Node& node) {
2.957 + _predMap[node] = INVALID;
2.958 + }
2.959 +
2.960 + void reach(const Node& node) {
2.961 + _numMap.set(node, _num);
2.962 + _retMap.set(node, _num);
2.963 + ++_num;
2.964 + }
2.965 +
2.966 + void leave(const Node& node) {
2.967 + if (_numMap[node] <= _retMap[node]) {
2.968 + if (_predMap[node] != INVALID) {
2.969 + _cutMap.set(_predMap[node], true);
2.970 + ++_cutNum;
2.971 + }
2.972 + }
2.973 + }
2.974 +
2.975 + void discover(const Edge& edge) {
2.976 + _predMap.set(_graph.target(edge), edge);
2.977 + }
2.978 +
2.979 + void examine(const Edge& edge) {
2.980 + if (_predMap[_graph.source(edge)] == _graph.oppositeEdge(edge)) {
2.981 + return;
2.982 + }
2.983 + if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
2.984 + _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
2.985 + }
2.986 + }
2.987 +
2.988 + void backtrack(const Edge& edge) {
2.989 + if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
2.990 + _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
2.991 + }
2.992 + }
2.993 +
2.994 + private:
2.995 + const Graph& _graph;
2.996 + EdgeMap& _cutMap;
2.997 + int& _cutNum;
2.998 +
2.999 + typename Graph::template NodeMap<int> _numMap;
2.1000 + typename Graph::template NodeMap<int> _retMap;
2.1001 + typename Graph::template NodeMap<Edge> _predMap;
2.1002 + int _num;
2.1003 + };
2.1004 + }
2.1005 +
2.1006 + template <typename UndirGraph>
2.1007 + int countEdgeBiconnectedComponents(const UndirGraph& graph);
2.1008 +
2.1009 + /// \ingroup topology
2.1010 + ///
2.1011 + /// \brief Checks that the graph is edge biconnected.
2.1012 + ///
2.1013 + /// This function checks that the graph is edge biconnected. The undirected
2.1014 + /// graph is edge biconnected when any two nodes are connected with two
2.1015 + /// edge-disjoint paths.
2.1016 + ///
2.1017 + /// \param graph The undirected graph.
2.1018 + /// \return The number of components.
2.1019 + /// \todo Make it faster.
2.1020 + template <typename UndirGraph>
2.1021 + bool edgeBiconnected(const UndirGraph& graph) {
2.1022 + return countEdgeBiconnectedComponents(graph) == 1;
2.1023 + }
2.1024 +
2.1025 + /// \ingroup topology
2.1026 + ///
2.1027 + /// \brief Count the edge biconnected components.
2.1028 + ///
2.1029 + /// This function count the edge biconnected components in an undirected
2.1030 + /// graph. The edge biconnected components are the classes of an equivalence
2.1031 + /// relation on the nodes. Two nodes are in relationship when they are
2.1032 + /// connected with at least two edge-disjoint paths.
2.1033 + ///
2.1034 + /// \param graph The undirected graph.
2.1035 + /// \return The number of components.
2.1036 + template <typename UndirGraph>
2.1037 + int countEdgeBiconnectedComponents(const UndirGraph& graph) {
2.1038 + checkConcept<concept::UndirGraph, UndirGraph>();
2.1039 + typedef typename UndirGraph::NodeIt NodeIt;
2.1040 +
2.1041 + using namespace _topology_bits;
2.1042 +
2.1043 + typedef CountEdgeBiconnectedComponentsVisitor<UndirGraph> Visitor;
2.1044 +
2.1045 + int compNum = 0;
2.1046 + Visitor visitor(graph, compNum);
2.1047 +
2.1048 + DfsVisit<UndirGraph, Visitor> dfs(graph, visitor);
2.1049 + dfs.init();
2.1050 +
2.1051 + for (NodeIt it(graph); it != INVALID; ++it) {
2.1052 + if (!dfs.reached(it)) {
2.1053 + dfs.addSource(it);
2.1054 + dfs.start();
2.1055 + }
2.1056 + }
2.1057 + return compNum;
2.1058 + }
2.1059 +
2.1060 + /// \ingroup topology
2.1061 + ///
2.1062 + /// \brief Find the edge biconnected components.
2.1063 + ///
2.1064 + /// This function finds the edge biconnected components in an undirected
2.1065 + /// graph. The edge biconnected components are the classes of an equivalence
2.1066 + /// relation on the nodes. Two nodes are in relationship when they are
2.1067 + /// connected at least two edge-disjoint paths.
2.1068 + ///
2.1069 + /// \param graph The graph.
2.1070 + /// \retval comp A writable node map. The values will be set from 0 to
2.1071 + /// the number of the biconnected components minus one. Each values
2.1072 + /// of the map will be set exactly once, the values of a certain component
2.1073 + /// will be set continuously.
2.1074 + /// \return The number of components.
2.1075 + template <typename UndirGraph, typename NodeMap>
2.1076 + int edgeBiconnectedComponents(const UndirGraph& graph, NodeMap& compMap) {
2.1077 + checkConcept<concept::UndirGraph, UndirGraph>();
2.1078 + typedef typename UndirGraph::NodeIt NodeIt;
2.1079 + typedef typename UndirGraph::Node Node;
2.1080 + checkConcept<concept::WriteMap<Node, int>, NodeMap>();
2.1081 +
2.1082 + using namespace _topology_bits;
2.1083 +
2.1084 + typedef EdgeBiconnectedComponentsVisitor<UndirGraph, NodeMap> Visitor;
2.1085 +
2.1086 + int compNum = 0;
2.1087 + Visitor visitor(graph, compMap, compNum);
2.1088 +
2.1089 + DfsVisit<UndirGraph, Visitor> dfs(graph, visitor);
2.1090 + dfs.init();
2.1091 +
2.1092 + for (NodeIt it(graph); it != INVALID; ++it) {
2.1093 + if (!dfs.reached(it)) {
2.1094 + dfs.addSource(it);
2.1095 + dfs.start();
2.1096 + }
2.1097 + }
2.1098 + return compNum;
2.1099 + }
2.1100 +
2.1101 + /// \ingroup topology
2.1102 + ///
2.1103 + /// \brief Find the edge biconnected cut edges.
2.1104 + ///
2.1105 + /// This function finds the edge biconnected components in an undirected
2.1106 + /// graph. The edge biconnected components are the classes of an equivalence
2.1107 + /// relation on the nodes. Two nodes are in relationship when they are
2.1108 + /// connected with at least two edge-disjoint paths. The edge biconnected
2.1109 + /// components are separted by edges which are the cut edges of the
2.1110 + /// components.
2.1111 + ///
2.1112 + /// \param graph The graph.
2.1113 + /// \retval comp A writable node map. The values will be set true when the
2.1114 + /// edge is a cut edge.
2.1115 + /// \return The number of cut edges.
2.1116 + template <typename UndirGraph, typename UndirEdgeMap>
2.1117 + int edgeBiconnectedCutEdges(const UndirGraph& graph, UndirEdgeMap& cutMap) {
2.1118 + checkConcept<concept::UndirGraph, UndirGraph>();
2.1119 + typedef typename UndirGraph::NodeIt NodeIt;
2.1120 + typedef typename UndirGraph::UndirEdge UndirEdge;
2.1121 + checkConcept<concept::WriteMap<UndirEdge, bool>, UndirEdgeMap>();
2.1122 +
2.1123 + using namespace _topology_bits;
2.1124 +
2.1125 + typedef EdgeBiconnectedCutEdgesVisitor<UndirGraph, UndirEdgeMap> Visitor;
2.1126 +
2.1127 + int cutNum = 0;
2.1128 + Visitor visitor(graph, cutMap, cutNum);
2.1129 +
2.1130 + DfsVisit<UndirGraph, Visitor> dfs(graph, visitor);
2.1131 + dfs.init();
2.1132 +
2.1133 + for (NodeIt it(graph); it != INVALID; ++it) {
2.1134 + if (!dfs.reached(it)) {
2.1135 + dfs.addSource(it);
2.1136 + dfs.start();
2.1137 + }
2.1138 + }
2.1139 + return cutNum;
2.1140 + }
2.1141 +
2.1142 +
2.1143 + namespace _topology_bits {
2.1144 +
2.1145 + template <typename Graph, typename IntNodeMap>
2.1146 + class TopologicalSortVisitor : public DfsVisitor<Graph> {
2.1147 + public:
2.1148 + typedef typename Graph::Node Node;
2.1149 + typedef typename Graph::Edge edge;
2.1150 +
2.1151 + TopologicalSortVisitor(IntNodeMap& order, int num)
2.1152 + : _order(order), _num(num) {}
2.1153 +
2.1154 + void leave(const Node& node) {
2.1155 + _order.set(node, --_num);
2.1156 }
2.1157
2.1158 private:
2.1159 - NodeMap& nodeMap;
2.1160 - int counter;
2.1161 + IntNodeMap& _order;
2.1162 + int _num;
2.1163 };
2.1164 +
2.1165 }
2.1166
2.1167 - // \todo Its to special output // ReadWriteMap
2.1168 + /// \ingroup topology
2.1169 + ///
2.1170 + /// \brief Sort the nodes of a DAG into topolgical order.
2.1171 + ///
2.1172 + /// Sort the nodes of a DAG into topolgical order.
2.1173 + ///
2.1174 + /// \param g The graph. In must be directed and acyclic.
2.1175 + /// \retval comp A writable node map. The values will be set from 0 to
2.1176 + /// the number of the nodes in the graph minus one. Each values of the map
2.1177 + /// will be set exactly once, the values will be set descending order.
2.1178 + ///
2.1179 + /// \see checkedTopologicalSort
2.1180 + /// \see dag
2.1181 template <typename Graph, typename NodeMap>
2.1182 - bool topological_sort(const Graph& graph, NodeMap& nodeMap) {
2.1183 + void topologicalSort(const Graph& graph, NodeMap& order) {
2.1184 + using namespace _topology_bits;
2.1185 +
2.1186 + checkConcept<concept::StaticGraph, Graph>();
2.1187 + checkConcept<concept::WriteMap<typename Graph::Node, int>, NodeMap>();
2.1188 +
2.1189 + typedef typename Graph::Node Node;
2.1190 + typedef typename Graph::NodeIt NodeIt;
2.1191 + typedef typename Graph::Edge Edge;
2.1192 +
2.1193 + TopologicalSortVisitor<Graph, NodeMap>
2.1194 + visitor(order, countNodes(graph));
2.1195 +
2.1196 + DfsVisit<Graph, TopologicalSortVisitor<Graph, NodeMap> >
2.1197 + dfs(graph, visitor);
2.1198 +
2.1199 + dfs.init();
2.1200 + for (NodeIt it(graph); it != INVALID; ++it) {
2.1201 + if (!dfs.reached(it)) {
2.1202 + dfs.addSource(it);
2.1203 + dfs.start();
2.1204 + }
2.1205 + }
2.1206 + }
2.1207 +
2.1208 + /// \ingroup topology
2.1209 + ///
2.1210 + /// \brief Sort the nodes of a DAG into topolgical order.
2.1211 + ///
2.1212 + /// Sort the nodes of a DAG into topolgical order. It also checks
2.1213 + /// that the given graph is DAG.
2.1214 + ///
2.1215 + /// \param g The graph. In must be directed and acyclic.
2.1216 + /// \retval order A readable - writable node map. The values will be set
2.1217 + /// from 0 to the number of the nodes in the graph minus one. Each values
2.1218 + /// of the map will be set exactly once, the values will be set descending
2.1219 + /// order.
2.1220 + /// \return %False when the graph is not DAG.
2.1221 + ///
2.1222 + /// \see topologicalSort
2.1223 + /// \see dag
2.1224 + template <typename Graph, typename NodeMap>
2.1225 + bool checkedTopologicalSort(const Graph& graph, NodeMap& order) {
2.1226 using namespace _topology_bits;
2.1227
2.1228 checkConcept<concept::StaticGraph, Graph>();
2.1229 @@ -72,35 +1231,39 @@
2.1230 typedef typename Graph::NodeIt NodeIt;
2.1231 typedef typename Graph::Edge Edge;
2.1232
2.1233 - typedef BackCounterMap<NodeMap> ProcessedMap;
2.1234 + order = constMap<Node, int, -1>();
2.1235
2.1236 - typename Dfs<Graph>::template DefProcessedMap<ProcessedMap>::
2.1237 - Create dfs(graph);
2.1238 + TopologicalSortVisitor<Graph, NodeMap>
2.1239 + visitor(order, countNodes(graph));
2.1240
2.1241 - ProcessedMap processed(nodeMap, countNodes(graph));
2.1242 + DfsVisit<Graph, TopologicalSortVisitor<Graph, NodeMap> >
2.1243 + dfs(graph, visitor);
2.1244
2.1245 - dfs.processedMap(processed);
2.1246 dfs.init();
2.1247 for (NodeIt it(graph); it != INVALID; ++it) {
2.1248 if (!dfs.reached(it)) {
2.1249 dfs.addSource(it);
2.1250 while (!dfs.emptyQueue()) {
2.1251 - Edge edge = dfs.nextEdge();
2.1252 - Node target = graph.target(edge);
2.1253 - if (dfs.reached(target) && !processed[target]) {
2.1254 - return false;
2.1255 - }
2.1256 - dfs.processNextEdge();
2.1257 - }
2.1258 + Edge edge = dfs.nextEdge();
2.1259 + Node target = graph.target(edge);
2.1260 + if (dfs.reached(target) && order[target] == -1) {
2.1261 + return false;
2.1262 + }
2.1263 + dfs.processNextEdge();
2.1264 + }
2.1265 }
2.1266 - }
2.1267 + }
2.1268 return true;
2.1269 }
2.1270
2.1271 - /// \brief Check that the given graph is a DAG.
2.1272 + /// \ingroup topology
2.1273 ///
2.1274 - /// Check that the given graph is a DAG. The DAG is
2.1275 + /// \brief Check that the given directed graph is a DAG.
2.1276 + ///
2.1277 + /// Check that the given directed graph is a DAG. The DAG is
2.1278 /// an Directed Acyclic Graph.
2.1279 + /// \return %False when the graph is not DAG.
2.1280 + /// \see acyclic
2.1281 template <typename Graph>
2.1282 bool dag(const Graph& graph) {
2.1283
2.1284 @@ -135,29 +1298,14 @@
2.1285 return true;
2.1286 }
2.1287
2.1288 - // UndirGraph algorithms
2.1289 -
2.1290 - /// \brief Check that the given undirected graph is connected.
2.1291 + /// \ingroup topology
2.1292 ///
2.1293 - /// Check that the given undirected graph connected.
2.1294 - template <typename UndirGraph>
2.1295 - bool connected(const UndirGraph& graph) {
2.1296 - checkConcept<concept::UndirGraph, UndirGraph>();
2.1297 - typedef typename UndirGraph::NodeIt NodeIt;
2.1298 - if (NodeIt(graph) == INVALID) return false;
2.1299 - Dfs<UndirGraph> dfs(graph);
2.1300 - dfs.run(NodeIt(graph));
2.1301 - for (NodeIt it(graph); it != INVALID; ++it) {
2.1302 - if (!dfs.reached(it)) {
2.1303 - return false;
2.1304 - }
2.1305 - }
2.1306 - return true;
2.1307 - }
2.1308 -
2.1309 /// \brief Check that the given undirected graph is acyclic.
2.1310 ///
2.1311 /// Check that the given undirected graph acyclic.
2.1312 + /// \param graph The undirected graph.
2.1313 + /// \return %True when there is no circle in the graph.
2.1314 + /// \see dag
2.1315 template <typename UndirGraph>
2.1316 bool acyclic(const UndirGraph& graph) {
2.1317 checkConcept<concept::UndirGraph, UndirGraph>();
2.1318 @@ -184,16 +1332,19 @@
2.1319 return true;
2.1320 }
2.1321
2.1322 + /// \ingroup topology
2.1323 + ///
2.1324 /// \brief Check that the given undirected graph is tree.
2.1325 ///
2.1326 /// Check that the given undirected graph is tree.
2.1327 + /// \param graph The undirected graph.
2.1328 + /// \return %True when the graph is acyclic and connected.
2.1329 template <typename UndirGraph>
2.1330 bool tree(const UndirGraph& graph) {
2.1331 checkConcept<concept::UndirGraph, UndirGraph>();
2.1332 typedef typename UndirGraph::Node Node;
2.1333 typedef typename UndirGraph::NodeIt NodeIt;
2.1334 typedef typename UndirGraph::Edge Edge;
2.1335 - if (NodeIt(graph) == INVALID) return false;
2.1336 Dfs<UndirGraph> dfs(graph);
2.1337 dfs.init();
2.1338 dfs.addSource(NodeIt(graph));
2.1339 @@ -214,208 +1365,45 @@
2.1340 }
2.1341 return true;
2.1342 }
2.1343 -
2.1344 - ///Count the number of connected components of an undirected graph
2.1345
2.1346 - ///Count the number of connected components of an undirected graph
2.1347 + /// \ingroup topology
2.1348 ///
2.1349 - ///\param g The graph. In must be undirected.
2.1350 - ///\return The number of components
2.1351 - template <class UndirGraph>
2.1352 - int countConnectedComponents(const UndirGraph &g) {
2.1353 + /// \brief Check that the given undirected graph is bipartite.
2.1354 + ///
2.1355 + /// Check that the given undirected graph is bipartite.
2.1356 + /// \param graph The undirected graph.
2.1357 + /// \return %True when the nodes can be separated into two sets that
2.1358 + /// there are not connected nodes in neither sets.
2.1359 + template <typename UndirGraph>
2.1360 + bool bipartite(const UndirGraph& graph) {
2.1361 checkConcept<concept::UndirGraph, UndirGraph>();
2.1362 - int c = 0;
2.1363 - Bfs<UndirGraph> bfs(g);
2.1364 - bfs.init();
2.1365 - for(typename UndirGraph::NodeIt n(g); n != INVALID; ++n) {
2.1366 - if(!bfs.reached(n)) {
2.1367 - bfs.addSource(n);
2.1368 - bfs.start();
2.1369 - ++c;
2.1370 - }
2.1371 - }
2.1372 - return c;
2.1373 - }
2.1374 -
2.1375 -
2.1376 - ///Find the connected components of an undirected graph
2.1377 -
2.1378 - ///Find the connected components of an undirected graph
2.1379 - ///
2.1380 - ///\param g The graph. In must be undirected.
2.1381 - ///\retval comp A writable node map. The values will be set from 0 to
2.1382 - ///the number of the connected components minus one. Each values of the map
2.1383 - ///will be set exactly once, the values of a certain component will be
2.1384 - ///set continuously.
2.1385 - ///\return The number of components
2.1386 - ///\todo Test required
2.1387 - template <class UndirGraph, class IntNodeMap>
2.1388 - int connectedComponents(const UndirGraph &g, IntNodeMap &comp) {
2.1389 - checkConcept<concept::UndirGraph, UndirGraph>();
2.1390 - checkConcept<concept::WriteMap<typename UndirGraph::Node, int>,
2.1391 - IntNodeMap>();
2.1392 - int c = 0;
2.1393 - Bfs<UndirGraph> bfs(g);
2.1394 - bfs.init();
2.1395 - for(typename UndirGraph::NodeIt n(g); n != INVALID; ++n) {
2.1396 - if(!bfs.reached(n)) {
2.1397 - bfs.addSource(n);
2.1398 - while (!bfs.emptyQueue()) {
2.1399 - comp[bfs.nextNode()] = c;
2.1400 - bfs.processNextNode();
2.1401 - }
2.1402 - ++c;
2.1403 - }
2.1404 - }
2.1405 - return c;
2.1406 - }
2.1407 -
2.1408 - namespace _components_bits {
2.1409 -
2.1410 - template <typename Key, typename IntMap>
2.1411 - struct FillWriteMap : public MapBase<Key, bool> {
2.1412 - public:
2.1413 - FillWriteMap(IntMap& _map, int& _comp)
2.1414 - : map(_map), comp(_comp) {}
2.1415 - void set(Key key, bool value) {
2.1416 - if (value) { map.set(key, comp); }
2.1417 - }
2.1418 - private:
2.1419 - IntMap& map;
2.1420 - int& comp;
2.1421 - };
2.1422 -
2.1423 - template <typename Key, typename Container = std::vector<Key> >
2.1424 - struct BackInserterWriteMap : public MapBase<Key, bool> {
2.1425 - public:
2.1426 - BackInserterWriteMap(Container& _container)
2.1427 - : container(_container) {}
2.1428 - void set(Key key, bool value) {
2.1429 - if (value) { container.push_back(key); }
2.1430 - }
2.1431 - private:
2.1432 - Container& container;
2.1433 - };
2.1434 -
2.1435 - }
2.1436 -
2.1437 - /// \brief Count the strongly connected components of a directed graph
2.1438 - ///
2.1439 - /// Count the strongly connected components of a directed graph
2.1440 - ///
2.1441 - /// \param g The graph.
2.1442 - /// \return The number of components
2.1443 - template <typename Graph>
2.1444 - int countStronglyConnectedComponents(const Graph& graph) {
2.1445 - checkConcept<concept::StaticGraph, Graph>();
2.1446 -
2.1447 - using namespace _components_bits;
2.1448 -
2.1449 - typedef typename Graph::Node Node;
2.1450 - typedef typename Graph::Edge Edge;
2.1451 - typedef typename Graph::NodeIt NodeIt;
2.1452 - typedef typename Graph::EdgeIt EdgeIt;
2.1453 -
2.1454 -
2.1455 - typename Dfs<Graph>::
2.1456 - template DefProcessedMap<BackInserterWriteMap<Node> >::
2.1457 - Create dfs(graph);
2.1458 -
2.1459 - std::vector<Node> nodes;
2.1460 - BackInserterWriteMap<Node> processed(nodes);
2.1461 - dfs.processedMap(processed);
2.1462 -
2.1463 + typedef typename UndirGraph::Node Node;
2.1464 + typedef typename UndirGraph::NodeIt NodeIt;
2.1465 + typedef typename UndirGraph::Edge Edge;
2.1466 + if (NodeIt(graph) == INVALID) return false;
2.1467 + Dfs<UndirGraph> dfs(graph);
2.1468 dfs.init();
2.1469 + typename UndirGraph::template NodeMap<bool> red(graph);
2.1470 for (NodeIt it(graph); it != INVALID; ++it) {
2.1471 if (!dfs.reached(it)) {
2.1472 dfs.addSource(it);
2.1473 - dfs.start();
2.1474 + red[it] = true;
2.1475 + while (!dfs.emptyQueue()) {
2.1476 + Edge edge = dfs.nextEdge();
2.1477 + Node source = graph.source(edge);
2.1478 + Node target = graph.target(edge);
2.1479 + if (dfs.reached(target) && red[source] == red[target]) {
2.1480 + return false;
2.1481 + } else {
2.1482 + red[target] = !red[source];
2.1483 + }
2.1484 + dfs.processNextEdge();
2.1485 + }
2.1486 }
2.1487 }
2.1488 -
2.1489 - typedef RevGraphAdaptor<const Graph> RGraph;
2.1490 -
2.1491 - RGraph rgraph(graph);
2.1492 -
2.1493 - Dfs<RGraph> rdfs(rgraph);
2.1494 -
2.1495 - int num = 0;
2.1496 -
2.1497 - rdfs.init();
2.1498 - for (typename std::vector<Node>::reverse_iterator
2.1499 - it = nodes.rbegin(); it != nodes.rend(); ++it) {
2.1500 - if (!rdfs.reached(*it)) {
2.1501 - rdfs.addSource(*it);
2.1502 - rdfs.start();
2.1503 - ++num;
2.1504 - }
2.1505 - }
2.1506 - return num;
2.1507 + return true;
2.1508 }
2.1509 -
2.1510 - /// \brief Find the strongly connected components of a directed graph
2.1511 - ///
2.1512 - /// Find the strongly connected components of a directed graph
2.1513 - ///
2.1514 - /// \param g The graph.
2.1515 - /// \retval comp A writable node map. The values will be set from 0 to
2.1516 - /// the number of the strongly connected components minus one. Each values
2.1517 - /// of the map will be set exactly once, the values of a certain component
2.1518 - /// will be set continuously.
2.1519 - /// \return The number of components
2.1520 - template <typename Graph, typename IntNodeMap>
2.1521 - int stronglyConnectedComponents(const Graph& graph, IntNodeMap& comp) {
2.1522 - checkConcept<concept::StaticGraph, Graph>();
2.1523 - checkConcept<concept::WriteMap<typename Graph::Node, int>, IntNodeMap>();
2.1524 -
2.1525 - using namespace _components_bits;
2.1526 -
2.1527 - typedef typename Graph::Node Node;
2.1528 - typedef typename Graph::Edge Edge;
2.1529 - typedef typename Graph::NodeIt NodeIt;
2.1530 - typedef typename Graph::EdgeIt EdgeIt;
2.1531 -
2.1532 -
2.1533 - typename Dfs<Graph>::
2.1534 - template DefProcessedMap<BackInserterWriteMap<Node> >::
2.1535 - Create dfs(graph);
2.1536 -
2.1537 - std::vector<Node> nodes;
2.1538 - BackInserterWriteMap<Node> processed(nodes);
2.1539 - dfs.processedMap(processed);
2.1540 -
2.1541 - dfs.init();
2.1542 - for (NodeIt it(graph); it != INVALID; ++it) {
2.1543 - if (!dfs.reached(it)) {
2.1544 - dfs.addSource(it);
2.1545 - dfs.start();
2.1546 - }
2.1547 - }
2.1548 -
2.1549 - typedef RevGraphAdaptor<const Graph> RGraph;
2.1550 -
2.1551 - RGraph rgraph(graph);
2.1552 -
2.1553 - typename Dfs<RGraph>::
2.1554 - template DefProcessedMap<FillWriteMap<Node, IntNodeMap> >::
2.1555 - Create rdfs(rgraph);
2.1556 -
2.1557 - int num = 0;
2.1558 - FillWriteMap<Node, IntNodeMap> rprocessed(comp, num);
2.1559 - rdfs.processedMap(rprocessed);
2.1560 -
2.1561 - rdfs.init();
2.1562 - for (typename std::vector<Node>::reverse_iterator
2.1563 - it = nodes.rbegin(); it != nodes.rend(); ++it) {
2.1564 - if (!rdfs.reached(*it)) {
2.1565 - rdfs.addSource(*it);
2.1566 - rdfs.start();
2.1567 - ++num;
2.1568 - }
2.1569 - }
2.1570 - return num;
2.1571 - }
2.1572 -
2.1573 +
2.1574 } //namespace lemon
2.1575
2.1576 #endif //LEMON_TOPOLOGY_H