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