Branch data Line data Source code
1 : : /* -*- mode: C++; indent-tabs-mode: nil; -*-
2 : : *
3 : : * This file is a part of LEMON, a generic C++ optimization library.
4 : : *
5 : : * Copyright (C) 2003-2010
6 : : * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 : : * (Egervary Research Group on Combinatorial Optimization, EGRES).
8 : : *
9 : : * Permission to use, modify and distribute this software is granted
10 : : * provided that this copyright notice appears in all copies. For
11 : : * precise terms see the accompanying LICENSE file.
12 : : *
13 : : * This software is provided "AS IS" with no warranty of any kind,
14 : : * express or implied, and with no claim as to its suitability for any
15 : : * purpose.
16 : : *
17 : : */
18 : :
19 : : #ifndef LEMON_CONNECTIVITY_H
20 : : #define LEMON_CONNECTIVITY_H
21 : :
22 : : #include <lemon/dfs.h>
23 : : #include <lemon/bfs.h>
24 : : #include <lemon/core.h>
25 : : #include <lemon/maps.h>
26 : : #include <lemon/adaptors.h>
27 : :
28 : : #include <lemon/concepts/digraph.h>
29 : : #include <lemon/concepts/graph.h>
30 : : #include <lemon/concept_check.h>
31 : :
32 : : #include <stack>
33 : : #include <functional>
34 : :
35 : : /// \ingroup graph_properties
36 : : /// \file
37 : : /// \brief Connectivity algorithms
38 : : ///
39 : : /// Connectivity algorithms
40 : :
41 : : namespace lemon {
42 : :
43 : : /// \ingroup graph_properties
44 : : ///
45 : : /// \brief Check whether an undirected graph is connected.
46 : : ///
47 : : /// This function checks whether the given undirected graph is connected,
48 : : /// i.e. there is a path between any two nodes in the graph.
49 : : ///
50 : : /// \return \c true if the graph is connected.
51 : : /// \note By definition, the empty graph is connected.
52 : : ///
53 : : /// \see countConnectedComponents(), connectedComponents()
54 : : /// \see stronglyConnected()
55 : : template <typename Graph>
56 : : bool connected(const Graph& graph) {
57 : : checkConcept<concepts::Graph, Graph>();
58 : : typedef typename Graph::NodeIt NodeIt;
59 : : if (NodeIt(graph) == INVALID) return true;
60 : : Dfs<Graph> dfs(graph);
61 : : dfs.run(NodeIt(graph));
62 : : for (NodeIt it(graph); it != INVALID; ++it) {
63 : : if (!dfs.reached(it)) {
64 : : return false;
65 : : }
66 : : }
67 : : return true;
68 : : }
69 : :
70 : : /// \ingroup graph_properties
71 : : ///
72 : : /// \brief Count the number of connected components of an undirected graph
73 : : ///
74 : : /// This function counts the number of connected components of the given
75 : : /// undirected graph.
76 : : ///
77 : : /// The connected components are the classes of an equivalence relation
78 : : /// on the nodes of an undirected graph. Two nodes are in the same class
79 : : /// if they are connected with a path.
80 : : ///
81 : : /// \return The number of connected components.
82 : : /// \note By definition, the empty graph consists
83 : : /// of zero connected components.
84 : : ///
85 : : /// \see connected(), connectedComponents()
86 : : template <typename Graph>
87 : : int countConnectedComponents(const Graph &graph) {
88 : : checkConcept<concepts::Graph, Graph>();
89 : : typedef typename Graph::Node Node;
90 : : typedef typename Graph::Arc Arc;
91 : :
92 : : typedef NullMap<Node, Arc> PredMap;
93 : : typedef NullMap<Node, int> DistMap;
94 : :
95 : : int compNum = 0;
96 : : typename Bfs<Graph>::
97 : : template SetPredMap<PredMap>::
98 : : template SetDistMap<DistMap>::
99 : : Create bfs(graph);
100 : :
101 : : PredMap predMap;
102 : : bfs.predMap(predMap);
103 : :
104 : : DistMap distMap;
105 : : bfs.distMap(distMap);
106 : :
107 : : bfs.init();
108 : : for(typename Graph::NodeIt n(graph); n != INVALID; ++n) {
109 : : if (!bfs.reached(n)) {
110 : : bfs.addSource(n);
111 : : bfs.start();
112 : : ++compNum;
113 : : }
114 : : }
115 : : return compNum;
116 : : }
117 : :
118 : : /// \ingroup graph_properties
119 : : ///
120 : : /// \brief Find the connected components of an undirected graph
121 : : ///
122 : : /// This function finds the connected components of the given undirected
123 : : /// graph.
124 : : ///
125 : : /// The connected components are the classes of an equivalence relation
126 : : /// on the nodes of an undirected graph. Two nodes are in the same class
127 : : /// if they are connected with a path.
128 : : ///
129 : : /// \image html connected_components.png
130 : : /// \image latex connected_components.eps "Connected components" width=\textwidth
131 : : ///
132 : : /// \param graph The undirected graph.
133 : : /// \retval compMap A writable node map. The values will be set from 0 to
134 : : /// the number of the connected components minus one. Each value of the map
135 : : /// will be set exactly once, and the values of a certain component will be
136 : : /// set continuously.
137 : : /// \return The number of connected components.
138 : : /// \note By definition, the empty graph consists
139 : : /// of zero connected components.
140 : : ///
141 : : /// \see connected(), countConnectedComponents()
142 : : template <class Graph, class NodeMap>
143 : : int connectedComponents(const Graph &graph, NodeMap &compMap) {
144 : : checkConcept<concepts::Graph, Graph>();
145 : : typedef typename Graph::Node Node;
146 : : typedef typename Graph::Arc Arc;
147 : : checkConcept<concepts::WriteMap<Node, int>, NodeMap>();
148 : :
149 : : typedef NullMap<Node, Arc> PredMap;
150 : : typedef NullMap<Node, int> DistMap;
151 : :
152 : : int compNum = 0;
153 : : typename Bfs<Graph>::
154 : : template SetPredMap<PredMap>::
155 : : template SetDistMap<DistMap>::
156 : : Create bfs(graph);
157 : :
158 : : PredMap predMap;
159 : : bfs.predMap(predMap);
160 : :
161 : : DistMap distMap;
162 : : bfs.distMap(distMap);
163 : :
164 : : bfs.init();
165 : : for(typename Graph::NodeIt n(graph); n != INVALID; ++n) {
166 : : if(!bfs.reached(n)) {
167 : : bfs.addSource(n);
168 : : while (!bfs.emptyQueue()) {
169 : : compMap.set(bfs.nextNode(), compNum);
170 : : bfs.processNextNode();
171 : : }
172 : : ++compNum;
173 : : }
174 : : }
175 : : return compNum;
176 : : }
177 : :
178 : : namespace _connectivity_bits {
179 : :
180 : : template <typename Digraph, typename Iterator >
181 : : struct LeaveOrderVisitor : public DfsVisitor<Digraph> {
182 : : public:
183 : : typedef typename Digraph::Node Node;
184 : : LeaveOrderVisitor(Iterator it) : _it(it) {}
185 : :
186 : : void leave(const Node& node) {
187 : : *(_it++) = node;
188 : : }
189 : :
190 : : private:
191 : : Iterator _it;
192 : : };
193 : :
194 : : template <typename Digraph, typename Map>
195 : : struct FillMapVisitor : public DfsVisitor<Digraph> {
196 : : public:
197 : : typedef typename Digraph::Node Node;
198 : : typedef typename Map::Value Value;
199 : :
200 : : FillMapVisitor(Map& map, Value& value)
201 : : : _map(map), _value(value) {}
202 : :
203 : : void reach(const Node& node) {
204 : : _map.set(node, _value);
205 : : }
206 : : private:
207 : : Map& _map;
208 : : Value& _value;
209 : : };
210 : :
211 : : template <typename Digraph, typename ArcMap>
212 : : struct StronglyConnectedCutArcsVisitor : public DfsVisitor<Digraph> {
213 : : public:
214 : : typedef typename Digraph::Node Node;
215 : : typedef typename Digraph::Arc Arc;
216 : :
217 : : StronglyConnectedCutArcsVisitor(const Digraph& digraph,
218 : : ArcMap& cutMap,
219 : : int& cutNum)
220 : : : _digraph(digraph), _cutMap(cutMap), _cutNum(cutNum),
221 : : _compMap(digraph, -1), _num(-1) {
222 : : }
223 : :
224 : : void start(const Node&) {
225 : : ++_num;
226 : : }
227 : :
228 : : void reach(const Node& node) {
229 : : _compMap.set(node, _num);
230 : : }
231 : :
232 : : void examine(const Arc& arc) {
233 : : if (_compMap[_digraph.source(arc)] !=
234 : : _compMap[_digraph.target(arc)]) {
235 : : _cutMap.set(arc, true);
236 : : ++_cutNum;
237 : : }
238 : : }
239 : : private:
240 : : const Digraph& _digraph;
241 : : ArcMap& _cutMap;
242 : : int& _cutNum;
243 : :
244 : : typename Digraph::template NodeMap<int> _compMap;
245 : : int _num;
246 : : };
247 : :
248 : : }
249 : :
250 : :
251 : : /// \ingroup graph_properties
252 : : ///
253 : : /// \brief Check whether a directed graph is strongly connected.
254 : : ///
255 : : /// This function checks whether the given directed graph is strongly
256 : : /// connected, i.e. any two nodes of the digraph are
257 : : /// connected with directed paths in both direction.
258 : : ///
259 : : /// \return \c true if the digraph is strongly connected.
260 : : /// \note By definition, the empty digraph is strongly connected.
261 : : ///
262 : : /// \see countStronglyConnectedComponents(), stronglyConnectedComponents()
263 : : /// \see connected()
264 : : template <typename Digraph>
265 : : bool stronglyConnected(const Digraph& digraph) {
266 : : checkConcept<concepts::Digraph, Digraph>();
267 : :
268 : : typedef typename Digraph::NodeIt NodeIt;
269 : :
270 : : typename Digraph::Node source = NodeIt(digraph);
271 : : if (source == INVALID) return true;
272 : :
273 : : using namespace _connectivity_bits;
274 : :
275 : : typedef DfsVisitor<Digraph> Visitor;
276 : : Visitor visitor;
277 : :
278 : : DfsVisit<Digraph, Visitor> dfs(digraph, visitor);
279 : : dfs.init();
280 : : dfs.addSource(source);
281 : : dfs.start();
282 : :
283 : : for (NodeIt it(digraph); it != INVALID; ++it) {
284 : : if (!dfs.reached(it)) {
285 : : return false;
286 : : }
287 : : }
288 : :
289 : : typedef ReverseDigraph<const Digraph> RDigraph;
290 : : typedef typename RDigraph::NodeIt RNodeIt;
291 : : RDigraph rdigraph(digraph);
292 : :
293 : : typedef DfsVisitor<RDigraph> RVisitor;
294 : : RVisitor rvisitor;
295 : :
296 : : DfsVisit<RDigraph, RVisitor> rdfs(rdigraph, rvisitor);
297 : : rdfs.init();
298 : : rdfs.addSource(source);
299 : : rdfs.start();
300 : :
301 : : for (RNodeIt it(rdigraph); it != INVALID; ++it) {
302 : : if (!rdfs.reached(it)) {
303 : : return false;
304 : : }
305 : : }
306 : :
307 : : return true;
308 : : }
309 : :
310 : : /// \ingroup graph_properties
311 : : ///
312 : : /// \brief Count the number of strongly connected components of a
313 : : /// directed graph
314 : : ///
315 : : /// This function counts the number of strongly connected components of
316 : : /// the given directed graph.
317 : : ///
318 : : /// The strongly connected components are the classes of an
319 : : /// equivalence relation on the nodes of a digraph. Two nodes are in
320 : : /// the same class if they are connected with directed paths in both
321 : : /// direction.
322 : : ///
323 : : /// \return The number of strongly connected components.
324 : : /// \note By definition, the empty digraph has zero
325 : : /// strongly connected components.
326 : : ///
327 : : /// \see stronglyConnected(), stronglyConnectedComponents()
328 : : template <typename Digraph>
329 : : int countStronglyConnectedComponents(const Digraph& digraph) {
330 : : checkConcept<concepts::Digraph, Digraph>();
331 : :
332 : : using namespace _connectivity_bits;
333 : :
334 : : typedef typename Digraph::Node Node;
335 : : typedef typename Digraph::NodeIt NodeIt;
336 : :
337 : : typedef std::vector<Node> Container;
338 : : typedef typename Container::iterator Iterator;
339 : :
340 : : Container nodes(countNodes(digraph));
341 : : typedef LeaveOrderVisitor<Digraph, Iterator> Visitor;
342 : : Visitor visitor(nodes.begin());
343 : :
344 : : DfsVisit<Digraph, Visitor> dfs(digraph, visitor);
345 : : dfs.init();
346 : : for (NodeIt it(digraph); it != INVALID; ++it) {
347 : : if (!dfs.reached(it)) {
348 : : dfs.addSource(it);
349 : : dfs.start();
350 : : }
351 : : }
352 : :
353 : : typedef typename Container::reverse_iterator RIterator;
354 : : typedef ReverseDigraph<const Digraph> RDigraph;
355 : :
356 : : RDigraph rdigraph(digraph);
357 : :
358 : : typedef DfsVisitor<Digraph> RVisitor;
359 : : RVisitor rvisitor;
360 : :
361 : : DfsVisit<RDigraph, RVisitor> rdfs(rdigraph, rvisitor);
362 : :
363 : : int compNum = 0;
364 : :
365 : : rdfs.init();
366 : : for (RIterator it = nodes.rbegin(); it != nodes.rend(); ++it) {
367 : : if (!rdfs.reached(*it)) {
368 : : rdfs.addSource(*it);
369 : : rdfs.start();
370 : : ++compNum;
371 : : }
372 : : }
373 : : return compNum;
374 : : }
375 : :
376 : : /// \ingroup graph_properties
377 : : ///
378 : : /// \brief Find the strongly connected components of a directed graph
379 : : ///
380 : : /// This function finds the strongly connected components of the given
381 : : /// directed graph. In addition, the numbering of the components will
382 : : /// satisfy that there is no arc going from a higher numbered component
383 : : /// to a lower one (i.e. it provides a topological order of the components).
384 : : ///
385 : : /// The strongly connected components are the classes of an
386 : : /// equivalence relation on the nodes of a digraph. Two nodes are in
387 : : /// the same class if they are connected with directed paths in both
388 : : /// direction.
389 : : ///
390 : : /// \image html strongly_connected_components.png
391 : : /// \image latex strongly_connected_components.eps "Strongly connected components" width=\textwidth
392 : : ///
393 : : /// \param digraph The digraph.
394 : : /// \retval compMap A writable node map. The values will be set from 0 to
395 : : /// the number of the strongly connected components minus one. Each value
396 : : /// of the map will be set exactly once, and the values of a certain
397 : : /// component will be set continuously.
398 : : /// \return The number of strongly connected components.
399 : : /// \note By definition, the empty digraph has zero
400 : : /// strongly connected components.
401 : : ///
402 : : /// \see stronglyConnected(), countStronglyConnectedComponents()
403 : : template <typename Digraph, typename NodeMap>
404 : : int stronglyConnectedComponents(const Digraph& digraph, NodeMap& compMap) {
405 : : checkConcept<concepts::Digraph, Digraph>();
406 : : typedef typename Digraph::Node Node;
407 : : typedef typename Digraph::NodeIt NodeIt;
408 : : checkConcept<concepts::WriteMap<Node, int>, NodeMap>();
409 : :
410 : : using namespace _connectivity_bits;
411 : :
412 : : typedef std::vector<Node> Container;
413 : : typedef typename Container::iterator Iterator;
414 : :
415 : : Container nodes(countNodes(digraph));
416 : : typedef LeaveOrderVisitor<Digraph, Iterator> Visitor;
417 : : Visitor visitor(nodes.begin());
418 : :
419 : : DfsVisit<Digraph, Visitor> dfs(digraph, visitor);
420 : : dfs.init();
421 : : for (NodeIt it(digraph); it != INVALID; ++it) {
422 : : if (!dfs.reached(it)) {
423 : : dfs.addSource(it);
424 : : dfs.start();
425 : : }
426 : : }
427 : :
428 : : typedef typename Container::reverse_iterator RIterator;
429 : : typedef ReverseDigraph<const Digraph> RDigraph;
430 : :
431 : : RDigraph rdigraph(digraph);
432 : :
433 : : int compNum = 0;
434 : :
435 : : typedef FillMapVisitor<RDigraph, NodeMap> RVisitor;
436 : : RVisitor rvisitor(compMap, compNum);
437 : :
438 : : DfsVisit<RDigraph, RVisitor> rdfs(rdigraph, rvisitor);
439 : :
440 : : rdfs.init();
441 : : for (RIterator it = nodes.rbegin(); it != nodes.rend(); ++it) {
442 : : if (!rdfs.reached(*it)) {
443 : : rdfs.addSource(*it);
444 : : rdfs.start();
445 : : ++compNum;
446 : : }
447 : : }
448 : : return compNum;
449 : : }
450 : :
451 : : /// \ingroup graph_properties
452 : : ///
453 : : /// \brief Find the cut arcs of the strongly connected components.
454 : : ///
455 : : /// This function finds the cut arcs of the strongly connected components
456 : : /// of the given digraph.
457 : : ///
458 : : /// The strongly connected components are the classes of an
459 : : /// equivalence relation on the nodes of a digraph. Two nodes are in
460 : : /// the same class if they are connected with directed paths in both
461 : : /// direction.
462 : : /// The strongly connected components are separated by the cut arcs.
463 : : ///
464 : : /// \param digraph The digraph.
465 : : /// \retval cutMap A writable arc map. The values will be set to \c true
466 : : /// for the cut arcs (exactly once for each cut arc), and will not be
467 : : /// changed for other arcs.
468 : : /// \return The number of cut arcs.
469 : : ///
470 : : /// \see stronglyConnected(), stronglyConnectedComponents()
471 : : template <typename Digraph, typename ArcMap>
472 : : int stronglyConnectedCutArcs(const Digraph& digraph, ArcMap& cutMap) {
473 : : checkConcept<concepts::Digraph, Digraph>();
474 : : typedef typename Digraph::Node Node;
475 : : typedef typename Digraph::Arc Arc;
476 : : typedef typename Digraph::NodeIt NodeIt;
477 : : checkConcept<concepts::WriteMap<Arc, bool>, ArcMap>();
478 : :
479 : : using namespace _connectivity_bits;
480 : :
481 : : typedef std::vector<Node> Container;
482 : : typedef typename Container::iterator Iterator;
483 : :
484 : : Container nodes(countNodes(digraph));
485 : : typedef LeaveOrderVisitor<Digraph, Iterator> Visitor;
486 : : Visitor visitor(nodes.begin());
487 : :
488 : : DfsVisit<Digraph, Visitor> dfs(digraph, visitor);
489 : : dfs.init();
490 : : for (NodeIt it(digraph); it != INVALID; ++it) {
491 : : if (!dfs.reached(it)) {
492 : : dfs.addSource(it);
493 : : dfs.start();
494 : : }
495 : : }
496 : :
497 : : typedef typename Container::reverse_iterator RIterator;
498 : : typedef ReverseDigraph<const Digraph> RDigraph;
499 : :
500 : : RDigraph rdigraph(digraph);
501 : :
502 : : int cutNum = 0;
503 : :
504 : : typedef StronglyConnectedCutArcsVisitor<RDigraph, ArcMap> RVisitor;
505 : : RVisitor rvisitor(rdigraph, cutMap, cutNum);
506 : :
507 : : DfsVisit<RDigraph, RVisitor> rdfs(rdigraph, rvisitor);
508 : :
509 : : rdfs.init();
510 : : for (RIterator it = nodes.rbegin(); it != nodes.rend(); ++it) {
511 : : if (!rdfs.reached(*it)) {
512 : : rdfs.addSource(*it);
513 : : rdfs.start();
514 : : }
515 : : }
516 : : return cutNum;
517 : : }
518 : :
519 : : namespace _connectivity_bits {
520 : :
521 : : template <typename Digraph>
522 : : class CountBiNodeConnectedComponentsVisitor : public DfsVisitor<Digraph> {
523 : : public:
524 : : typedef typename Digraph::Node Node;
525 : : typedef typename Digraph::Arc Arc;
526 : : typedef typename Digraph::Edge Edge;
527 : :
528 : : CountBiNodeConnectedComponentsVisitor(const Digraph& graph, int &compNum)
529 : : : _graph(graph), _compNum(compNum),
530 : : _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
531 : :
532 : : void start(const Node& node) {
533 : : _predMap.set(node, INVALID);
534 : : }
535 : :
536 : : void reach(const Node& node) {
537 : : _numMap.set(node, _num);
538 : : _retMap.set(node, _num);
539 : : ++_num;
540 : : }
541 : :
542 : : void discover(const Arc& edge) {
543 : : _predMap.set(_graph.target(edge), _graph.source(edge));
544 : : }
545 : :
546 : : void examine(const Arc& edge) {
547 : : if (_graph.source(edge) == _graph.target(edge) &&
548 : : _graph.direction(edge)) {
549 : : ++_compNum;
550 : : return;
551 : : }
552 : : if (_predMap[_graph.source(edge)] == _graph.target(edge)) {
553 : : return;
554 : : }
555 : : if (_retMap[_graph.source(edge)] > _numMap[_graph.target(edge)]) {
556 : : _retMap.set(_graph.source(edge), _numMap[_graph.target(edge)]);
557 : : }
558 : : }
559 : :
560 : : void backtrack(const Arc& edge) {
561 : : if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
562 : : _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
563 : : }
564 : : if (_numMap[_graph.source(edge)] <= _retMap[_graph.target(edge)]) {
565 : : ++_compNum;
566 : : }
567 : : }
568 : :
569 : : private:
570 : : const Digraph& _graph;
571 : : int& _compNum;
572 : :
573 : : typename Digraph::template NodeMap<int> _numMap;
574 : : typename Digraph::template NodeMap<int> _retMap;
575 : : typename Digraph::template NodeMap<Node> _predMap;
576 : : int _num;
577 : : };
578 : :
579 : : template <typename Digraph, typename ArcMap>
580 : : class BiNodeConnectedComponentsVisitor : public DfsVisitor<Digraph> {
581 : : public:
582 : : typedef typename Digraph::Node Node;
583 : : typedef typename Digraph::Arc Arc;
584 : : typedef typename Digraph::Edge Edge;
585 : :
586 : : BiNodeConnectedComponentsVisitor(const Digraph& graph,
587 : : ArcMap& compMap, int &compNum)
588 : : : _graph(graph), _compMap(compMap), _compNum(compNum),
589 : : _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
590 : :
591 : : void start(const Node& node) {
592 : : _predMap.set(node, INVALID);
593 : : }
594 : :
595 : : void reach(const Node& node) {
596 : : _numMap.set(node, _num);
597 : : _retMap.set(node, _num);
598 : : ++_num;
599 : : }
600 : :
601 : : void discover(const Arc& edge) {
602 : : Node target = _graph.target(edge);
603 : : _predMap.set(target, edge);
604 : : _edgeStack.push(edge);
605 : : }
606 : :
607 : : void examine(const Arc& edge) {
608 : : Node source = _graph.source(edge);
609 : : Node target = _graph.target(edge);
610 : : if (source == target && _graph.direction(edge)) {
611 : : _compMap.set(edge, _compNum);
612 : : ++_compNum;
613 : : return;
614 : : }
615 : : if (_numMap[target] < _numMap[source]) {
616 : : if (_predMap[source] != _graph.oppositeArc(edge)) {
617 : : _edgeStack.push(edge);
618 : : }
619 : : }
620 : : if (_predMap[source] != INVALID &&
621 : : target == _graph.source(_predMap[source])) {
622 : : return;
623 : : }
624 : : if (_retMap[source] > _numMap[target]) {
625 : : _retMap.set(source, _numMap[target]);
626 : : }
627 : : }
628 : :
629 : : void backtrack(const Arc& edge) {
630 : : Node source = _graph.source(edge);
631 : : Node target = _graph.target(edge);
632 : : if (_retMap[source] > _retMap[target]) {
633 : : _retMap.set(source, _retMap[target]);
634 : : }
635 : : if (_numMap[source] <= _retMap[target]) {
636 : : while (_edgeStack.top() != edge) {
637 : : _compMap.set(_edgeStack.top(), _compNum);
638 : : _edgeStack.pop();
639 : : }
640 : : _compMap.set(edge, _compNum);
641 : : _edgeStack.pop();
642 : : ++_compNum;
643 : : }
644 : : }
645 : :
646 : : private:
647 : : const Digraph& _graph;
648 : : ArcMap& _compMap;
649 : : int& _compNum;
650 : :
651 : : typename Digraph::template NodeMap<int> _numMap;
652 : : typename Digraph::template NodeMap<int> _retMap;
653 : : typename Digraph::template NodeMap<Arc> _predMap;
654 : : std::stack<Edge> _edgeStack;
655 : : int _num;
656 : : };
657 : :
658 : :
659 : : template <typename Digraph, typename NodeMap>
660 : : class BiNodeConnectedCutNodesVisitor : public DfsVisitor<Digraph> {
661 : : public:
662 : : typedef typename Digraph::Node Node;
663 : : typedef typename Digraph::Arc Arc;
664 : : typedef typename Digraph::Edge Edge;
665 : :
666 : : BiNodeConnectedCutNodesVisitor(const Digraph& graph, NodeMap& cutMap,
667 : : int& cutNum)
668 : : : _graph(graph), _cutMap(cutMap), _cutNum(cutNum),
669 : : _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
670 : :
671 : : void start(const Node& node) {
672 : : _predMap.set(node, INVALID);
673 : : rootCut = false;
674 : : }
675 : :
676 : : void reach(const Node& node) {
677 : : _numMap.set(node, _num);
678 : : _retMap.set(node, _num);
679 : : ++_num;
680 : : }
681 : :
682 : : void discover(const Arc& edge) {
683 : : _predMap.set(_graph.target(edge), _graph.source(edge));
684 : : }
685 : :
686 : : void examine(const Arc& edge) {
687 : : if (_graph.source(edge) == _graph.target(edge) &&
688 : : _graph.direction(edge)) {
689 : : if (!_cutMap[_graph.source(edge)]) {
690 : : _cutMap.set(_graph.source(edge), true);
691 : : ++_cutNum;
692 : : }
693 : : return;
694 : : }
695 : : if (_predMap[_graph.source(edge)] == _graph.target(edge)) return;
696 : : if (_retMap[_graph.source(edge)] > _numMap[_graph.target(edge)]) {
697 : : _retMap.set(_graph.source(edge), _numMap[_graph.target(edge)]);
698 : : }
699 : : }
700 : :
701 : : void backtrack(const Arc& edge) {
702 : : if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
703 : : _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
704 : : }
705 : : if (_numMap[_graph.source(edge)] <= _retMap[_graph.target(edge)]) {
706 : : if (_predMap[_graph.source(edge)] != INVALID) {
707 : : if (!_cutMap[_graph.source(edge)]) {
708 : : _cutMap.set(_graph.source(edge), true);
709 : : ++_cutNum;
710 : : }
711 : : } else if (rootCut) {
712 : : if (!_cutMap[_graph.source(edge)]) {
713 : : _cutMap.set(_graph.source(edge), true);
714 : : ++_cutNum;
715 : : }
716 : : } else {
717 : : rootCut = true;
718 : : }
719 : : }
720 : : }
721 : :
722 : : private:
723 : : const Digraph& _graph;
724 : : NodeMap& _cutMap;
725 : : int& _cutNum;
726 : :
727 : : typename Digraph::template NodeMap<int> _numMap;
728 : : typename Digraph::template NodeMap<int> _retMap;
729 : : typename Digraph::template NodeMap<Node> _predMap;
730 : : std::stack<Edge> _edgeStack;
731 : : int _num;
732 : : bool rootCut;
733 : : };
734 : :
735 : : }
736 : :
737 : : template <typename Graph>
738 : : int countBiNodeConnectedComponents(const Graph& graph);
739 : :
740 : : /// \ingroup graph_properties
741 : : ///
742 : : /// \brief Check whether an undirected graph is bi-node-connected.
743 : : ///
744 : : /// This function checks whether the given undirected graph is
745 : : /// bi-node-connected, i.e. any two edges are on same circle.
746 : : ///
747 : : /// \return \c true if the graph bi-node-connected.
748 : : /// \note By definition, the empty graph is bi-node-connected.
749 : : ///
750 : : /// \see countBiNodeConnectedComponents(), biNodeConnectedComponents()
751 : : template <typename Graph>
752 : : bool biNodeConnected(const Graph& graph) {
753 : : return countBiNodeConnectedComponents(graph) <= 1;
754 : : }
755 : :
756 : : /// \ingroup graph_properties
757 : : ///
758 : : /// \brief Count the number of bi-node-connected components of an
759 : : /// undirected graph.
760 : : ///
761 : : /// This function counts the number of bi-node-connected components of
762 : : /// the given undirected graph.
763 : : ///
764 : : /// The bi-node-connected components are the classes of an equivalence
765 : : /// relation on the edges of a undirected graph. Two edges are in the
766 : : /// same class if they are on same circle.
767 : : ///
768 : : /// \return The number of bi-node-connected components.
769 : : ///
770 : : /// \see biNodeConnected(), biNodeConnectedComponents()
771 : : template <typename Graph>
772 : : int countBiNodeConnectedComponents(const Graph& graph) {
773 : : checkConcept<concepts::Graph, Graph>();
774 : : typedef typename Graph::NodeIt NodeIt;
775 : :
776 : : using namespace _connectivity_bits;
777 : :
778 : : typedef CountBiNodeConnectedComponentsVisitor<Graph> Visitor;
779 : :
780 : : int compNum = 0;
781 : : Visitor visitor(graph, compNum);
782 : :
783 : : DfsVisit<Graph, Visitor> dfs(graph, visitor);
784 : : dfs.init();
785 : :
786 : : for (NodeIt it(graph); it != INVALID; ++it) {
787 : : if (!dfs.reached(it)) {
788 : : dfs.addSource(it);
789 : : dfs.start();
790 : : }
791 : : }
792 : : return compNum;
793 : : }
794 : :
795 : : /// \ingroup graph_properties
796 : : ///
797 : : /// \brief Find the bi-node-connected components of an undirected graph.
798 : : ///
799 : : /// This function finds the bi-node-connected components of the given
800 : : /// undirected graph.
801 : : ///
802 : : /// The bi-node-connected components are the classes of an equivalence
803 : : /// relation on the edges of a undirected graph. Two edges are in the
804 : : /// same class if they are on same circle.
805 : : ///
806 : : /// \image html node_biconnected_components.png
807 : : /// \image latex node_biconnected_components.eps "bi-node-connected components" width=\textwidth
808 : : ///
809 : : /// \param graph The undirected graph.
810 : : /// \retval compMap A writable edge map. The values will be set from 0
811 : : /// to the number of the bi-node-connected components minus one. Each
812 : : /// value of the map will be set exactly once, and the values of a
813 : : /// certain component will be set continuously.
814 : : /// \return The number of bi-node-connected components.
815 : : ///
816 : : /// \see biNodeConnected(), countBiNodeConnectedComponents()
817 : : template <typename Graph, typename EdgeMap>
818 : : int biNodeConnectedComponents(const Graph& graph,
819 : : EdgeMap& compMap) {
820 : : checkConcept<concepts::Graph, Graph>();
821 : : typedef typename Graph::NodeIt NodeIt;
822 : : typedef typename Graph::Edge Edge;
823 : : checkConcept<concepts::WriteMap<Edge, int>, EdgeMap>();
824 : :
825 : : using namespace _connectivity_bits;
826 : :
827 : : typedef BiNodeConnectedComponentsVisitor<Graph, EdgeMap> Visitor;
828 : :
829 : : int compNum = 0;
830 : : Visitor visitor(graph, compMap, compNum);
831 : :
832 : : DfsVisit<Graph, Visitor> dfs(graph, visitor);
833 : : dfs.init();
834 : :
835 : : for (NodeIt it(graph); it != INVALID; ++it) {
836 : : if (!dfs.reached(it)) {
837 : : dfs.addSource(it);
838 : : dfs.start();
839 : : }
840 : : }
841 : : return compNum;
842 : : }
843 : :
844 : : /// \ingroup graph_properties
845 : : ///
846 : : /// \brief Find the bi-node-connected cut nodes in an undirected graph.
847 : : ///
848 : : /// This function finds the bi-node-connected cut nodes in the given
849 : : /// undirected graph.
850 : : ///
851 : : /// The bi-node-connected components are the classes of an equivalence
852 : : /// relation on the edges of a undirected graph. Two edges are in the
853 : : /// same class if they are on same circle.
854 : : /// The bi-node-connected components are separted by the cut nodes of
855 : : /// the components.
856 : : ///
857 : : /// \param graph The undirected graph.
858 : : /// \retval cutMap A writable node map. The values will be set to
859 : : /// \c true for the nodes that separate two or more components
860 : : /// (exactly once for each cut node), and will not be changed for
861 : : /// other nodes.
862 : : /// \return The number of the cut nodes.
863 : : ///
864 : : /// \see biNodeConnected(), biNodeConnectedComponents()
865 : : template <typename Graph, typename NodeMap>
866 : : int biNodeConnectedCutNodes(const Graph& graph, NodeMap& cutMap) {
867 : : checkConcept<concepts::Graph, Graph>();
868 : : typedef typename Graph::Node Node;
869 : : typedef typename Graph::NodeIt NodeIt;
870 : : checkConcept<concepts::WriteMap<Node, bool>, NodeMap>();
871 : :
872 : : using namespace _connectivity_bits;
873 : :
874 : : typedef BiNodeConnectedCutNodesVisitor<Graph, NodeMap> Visitor;
875 : :
876 : : int cutNum = 0;
877 : : Visitor visitor(graph, cutMap, cutNum);
878 : :
879 : : DfsVisit<Graph, Visitor> dfs(graph, visitor);
880 : : dfs.init();
881 : :
882 : : for (NodeIt it(graph); it != INVALID; ++it) {
883 : : if (!dfs.reached(it)) {
884 : : dfs.addSource(it);
885 : : dfs.start();
886 : : }
887 : : }
888 : : return cutNum;
889 : : }
890 : :
891 : : namespace _connectivity_bits {
892 : :
893 : : template <typename Digraph>
894 : : class CountBiEdgeConnectedComponentsVisitor : public DfsVisitor<Digraph> {
895 : : public:
896 : : typedef typename Digraph::Node Node;
897 : : typedef typename Digraph::Arc Arc;
898 : : typedef typename Digraph::Edge Edge;
899 : :
900 : : CountBiEdgeConnectedComponentsVisitor(const Digraph& graph, int &compNum)
901 : : : _graph(graph), _compNum(compNum),
902 : : _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
903 : :
904 : : void start(const Node& node) {
905 : : _predMap.set(node, INVALID);
906 : : }
907 : :
908 : : void reach(const Node& node) {
909 : : _numMap.set(node, _num);
910 : : _retMap.set(node, _num);
911 : : ++_num;
912 : : }
913 : :
914 : : void leave(const Node& node) {
915 : : if (_numMap[node] <= _retMap[node]) {
916 : : ++_compNum;
917 : : }
918 : : }
919 : :
920 : : void discover(const Arc& edge) {
921 : : _predMap.set(_graph.target(edge), edge);
922 : : }
923 : :
924 : : void examine(const Arc& edge) {
925 : : if (_predMap[_graph.source(edge)] == _graph.oppositeArc(edge)) {
926 : : return;
927 : : }
928 : : if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
929 : : _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
930 : : }
931 : : }
932 : :
933 : : void backtrack(const Arc& edge) {
934 : : if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
935 : : _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
936 : : }
937 : : }
938 : :
939 : : private:
940 : : const Digraph& _graph;
941 : : int& _compNum;
942 : :
943 : : typename Digraph::template NodeMap<int> _numMap;
944 : : typename Digraph::template NodeMap<int> _retMap;
945 : : typename Digraph::template NodeMap<Arc> _predMap;
946 : : int _num;
947 : : };
948 : :
949 : : template <typename Digraph, typename NodeMap>
950 : : class BiEdgeConnectedComponentsVisitor : public DfsVisitor<Digraph> {
951 : : public:
952 : : typedef typename Digraph::Node Node;
953 : : typedef typename Digraph::Arc Arc;
954 : : typedef typename Digraph::Edge Edge;
955 : :
956 : : BiEdgeConnectedComponentsVisitor(const Digraph& graph,
957 : : NodeMap& compMap, int &compNum)
958 : : : _graph(graph), _compMap(compMap), _compNum(compNum),
959 : : _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
960 : :
961 : : void start(const Node& node) {
962 : : _predMap.set(node, INVALID);
963 : : }
964 : :
965 : : void reach(const Node& node) {
966 : : _numMap.set(node, _num);
967 : : _retMap.set(node, _num);
968 : : _nodeStack.push(node);
969 : : ++_num;
970 : : }
971 : :
972 : : void leave(const Node& node) {
973 : : if (_numMap[node] <= _retMap[node]) {
974 : : while (_nodeStack.top() != node) {
975 : : _compMap.set(_nodeStack.top(), _compNum);
976 : : _nodeStack.pop();
977 : : }
978 : : _compMap.set(node, _compNum);
979 : : _nodeStack.pop();
980 : : ++_compNum;
981 : : }
982 : : }
983 : :
984 : : void discover(const Arc& edge) {
985 : : _predMap.set(_graph.target(edge), edge);
986 : : }
987 : :
988 : : void examine(const Arc& edge) {
989 : : if (_predMap[_graph.source(edge)] == _graph.oppositeArc(edge)) {
990 : : return;
991 : : }
992 : : if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
993 : : _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
994 : : }
995 : : }
996 : :
997 : : void backtrack(const Arc& edge) {
998 : : if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
999 : : _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
1000 : : }
1001 : : }
1002 : :
1003 : : private:
1004 : : const Digraph& _graph;
1005 : : NodeMap& _compMap;
1006 : : int& _compNum;
1007 : :
1008 : : typename Digraph::template NodeMap<int> _numMap;
1009 : : typename Digraph::template NodeMap<int> _retMap;
1010 : : typename Digraph::template NodeMap<Arc> _predMap;
1011 : : std::stack<Node> _nodeStack;
1012 : : int _num;
1013 : : };
1014 : :
1015 : :
1016 : : template <typename Digraph, typename ArcMap>
1017 : : class BiEdgeConnectedCutEdgesVisitor : public DfsVisitor<Digraph> {
1018 : : public:
1019 : : typedef typename Digraph::Node Node;
1020 : : typedef typename Digraph::Arc Arc;
1021 : : typedef typename Digraph::Edge Edge;
1022 : :
1023 : : BiEdgeConnectedCutEdgesVisitor(const Digraph& graph,
1024 : : ArcMap& cutMap, int &cutNum)
1025 : : : _graph(graph), _cutMap(cutMap), _cutNum(cutNum),
1026 : : _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
1027 : :
1028 : : void start(const Node& node) {
1029 : : _predMap[node] = INVALID;
1030 : : }
1031 : :
1032 : : void reach(const Node& node) {
1033 : : _numMap.set(node, _num);
1034 : : _retMap.set(node, _num);
1035 : : ++_num;
1036 : : }
1037 : :
1038 : : void leave(const Node& node) {
1039 : : if (_numMap[node] <= _retMap[node]) {
1040 : : if (_predMap[node] != INVALID) {
1041 : : _cutMap.set(_predMap[node], true);
1042 : : ++_cutNum;
1043 : : }
1044 : : }
1045 : : }
1046 : :
1047 : : void discover(const Arc& edge) {
1048 : : _predMap.set(_graph.target(edge), edge);
1049 : : }
1050 : :
1051 : : void examine(const Arc& edge) {
1052 : : if (_predMap[_graph.source(edge)] == _graph.oppositeArc(edge)) {
1053 : : return;
1054 : : }
1055 : : if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
1056 : : _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
1057 : : }
1058 : : }
1059 : :
1060 : : void backtrack(const Arc& edge) {
1061 : : if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
1062 : : _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
1063 : : }
1064 : : }
1065 : :
1066 : : private:
1067 : : const Digraph& _graph;
1068 : : ArcMap& _cutMap;
1069 : : int& _cutNum;
1070 : :
1071 : : typename Digraph::template NodeMap<int> _numMap;
1072 : : typename Digraph::template NodeMap<int> _retMap;
1073 : : typename Digraph::template NodeMap<Arc> _predMap;
1074 : : int _num;
1075 : : };
1076 : : }
1077 : :
1078 : : template <typename Graph>
1079 : : int countBiEdgeConnectedComponents(const Graph& graph);
1080 : :
1081 : : /// \ingroup graph_properties
1082 : : ///
1083 : : /// \brief Check whether an undirected graph is bi-edge-connected.
1084 : : ///
1085 : : /// This function checks whether the given undirected graph is
1086 : : /// bi-edge-connected, i.e. any two nodes are connected with at least
1087 : : /// two edge-disjoint paths.
1088 : : ///
1089 : : /// \return \c true if the graph is bi-edge-connected.
1090 : : /// \note By definition, the empty graph is bi-edge-connected.
1091 : : ///
1092 : : /// \see countBiEdgeConnectedComponents(), biEdgeConnectedComponents()
1093 : : template <typename Graph>
1094 : : bool biEdgeConnected(const Graph& graph) {
1095 : : return countBiEdgeConnectedComponents(graph) <= 1;
1096 : : }
1097 : :
1098 : : /// \ingroup graph_properties
1099 : : ///
1100 : : /// \brief Count the number of bi-edge-connected components of an
1101 : : /// undirected graph.
1102 : : ///
1103 : : /// This function counts the number of bi-edge-connected components of
1104 : : /// the given undirected graph.
1105 : : ///
1106 : : /// The bi-edge-connected components are the classes of an equivalence
1107 : : /// relation on the nodes of an undirected graph. Two nodes are in the
1108 : : /// same class if they are connected with at least two edge-disjoint
1109 : : /// paths.
1110 : : ///
1111 : : /// \return The number of bi-edge-connected components.
1112 : : ///
1113 : : /// \see biEdgeConnected(), biEdgeConnectedComponents()
1114 : : template <typename Graph>
1115 : : int countBiEdgeConnectedComponents(const Graph& graph) {
1116 : : checkConcept<concepts::Graph, Graph>();
1117 : : typedef typename Graph::NodeIt NodeIt;
1118 : :
1119 : : using namespace _connectivity_bits;
1120 : :
1121 : : typedef CountBiEdgeConnectedComponentsVisitor<Graph> Visitor;
1122 : :
1123 : : int compNum = 0;
1124 : : Visitor visitor(graph, compNum);
1125 : :
1126 : : DfsVisit<Graph, Visitor> dfs(graph, visitor);
1127 : : dfs.init();
1128 : :
1129 : : for (NodeIt it(graph); it != INVALID; ++it) {
1130 : : if (!dfs.reached(it)) {
1131 : : dfs.addSource(it);
1132 : : dfs.start();
1133 : : }
1134 : : }
1135 : : return compNum;
1136 : : }
1137 : :
1138 : : /// \ingroup graph_properties
1139 : : ///
1140 : : /// \brief Find the bi-edge-connected components of an undirected graph.
1141 : : ///
1142 : : /// This function finds the bi-edge-connected components of the given
1143 : : /// undirected graph.
1144 : : ///
1145 : : /// The bi-edge-connected components are the classes of an equivalence
1146 : : /// relation on the nodes of an undirected graph. Two nodes are in the
1147 : : /// same class if they are connected with at least two edge-disjoint
1148 : : /// paths.
1149 : : ///
1150 : : /// \image html edge_biconnected_components.png
1151 : : /// \image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth
1152 : : ///
1153 : : /// \param graph The undirected graph.
1154 : : /// \retval compMap A writable node map. The values will be set from 0 to
1155 : : /// the number of the bi-edge-connected components minus one. Each value
1156 : : /// of the map will be set exactly once, and the values of a certain
1157 : : /// component will be set continuously.
1158 : : /// \return The number of bi-edge-connected components.
1159 : : ///
1160 : : /// \see biEdgeConnected(), countBiEdgeConnectedComponents()
1161 : : template <typename Graph, typename NodeMap>
1162 : : int biEdgeConnectedComponents(const Graph& graph, NodeMap& compMap) {
1163 : : checkConcept<concepts::Graph, Graph>();
1164 : : typedef typename Graph::NodeIt NodeIt;
1165 : : typedef typename Graph::Node Node;
1166 : : checkConcept<concepts::WriteMap<Node, int>, NodeMap>();
1167 : :
1168 : : using namespace _connectivity_bits;
1169 : :
1170 : : typedef BiEdgeConnectedComponentsVisitor<Graph, NodeMap> Visitor;
1171 : :
1172 : : int compNum = 0;
1173 : : Visitor visitor(graph, compMap, compNum);
1174 : :
1175 : : DfsVisit<Graph, Visitor> dfs(graph, visitor);
1176 : : dfs.init();
1177 : :
1178 : : for (NodeIt it(graph); it != INVALID; ++it) {
1179 : : if (!dfs.reached(it)) {
1180 : : dfs.addSource(it);
1181 : : dfs.start();
1182 : : }
1183 : : }
1184 : : return compNum;
1185 : : }
1186 : :
1187 : : /// \ingroup graph_properties
1188 : : ///
1189 : : /// \brief Find the bi-edge-connected cut edges in an undirected graph.
1190 : : ///
1191 : : /// This function finds the bi-edge-connected cut edges in the given
1192 : : /// undirected graph.
1193 : : ///
1194 : : /// The bi-edge-connected components are the classes of an equivalence
1195 : : /// relation on the nodes of an undirected graph. Two nodes are in the
1196 : : /// same class if they are connected with at least two edge-disjoint
1197 : : /// paths.
1198 : : /// The bi-edge-connected components are separted by the cut edges of
1199 : : /// the components.
1200 : : ///
1201 : : /// \param graph The undirected graph.
1202 : : /// \retval cutMap A writable edge map. The values will be set to \c true
1203 : : /// for the cut edges (exactly once for each cut edge), and will not be
1204 : : /// changed for other edges.
1205 : : /// \return The number of cut edges.
1206 : : ///
1207 : : /// \see biEdgeConnected(), biEdgeConnectedComponents()
1208 : : template <typename Graph, typename EdgeMap>
1209 : : int biEdgeConnectedCutEdges(const Graph& graph, EdgeMap& cutMap) {
1210 : : checkConcept<concepts::Graph, Graph>();
1211 : : typedef typename Graph::NodeIt NodeIt;
1212 : : typedef typename Graph::Edge Edge;
1213 : : checkConcept<concepts::WriteMap<Edge, bool>, EdgeMap>();
1214 : :
1215 : : using namespace _connectivity_bits;
1216 : :
1217 : : typedef BiEdgeConnectedCutEdgesVisitor<Graph, EdgeMap> Visitor;
1218 : :
1219 : : int cutNum = 0;
1220 : : Visitor visitor(graph, cutMap, cutNum);
1221 : :
1222 : : DfsVisit<Graph, Visitor> dfs(graph, visitor);
1223 : : dfs.init();
1224 : :
1225 : : for (NodeIt it(graph); it != INVALID; ++it) {
1226 : : if (!dfs.reached(it)) {
1227 : : dfs.addSource(it);
1228 : : dfs.start();
1229 : : }
1230 : : }
1231 : : return cutNum;
1232 : : }
1233 : :
1234 : :
1235 : : namespace _connectivity_bits {
1236 : :
1237 : : template <typename Digraph, typename IntNodeMap>
1238 : : class TopologicalSortVisitor : public DfsVisitor<Digraph> {
1239 : : public:
1240 : : typedef typename Digraph::Node Node;
1241 : : typedef typename Digraph::Arc edge;
1242 : :
1243 : 51 : TopologicalSortVisitor(IntNodeMap& order, int num)
1244 : 51 : : _order(order), _num(num) {}
1245 : :
1246 : 270 : void leave(const Node& node) {
1247 : 270 : _order.set(node, --_num);
1248 : 270 : }
1249 : :
1250 : : private:
1251 : : IntNodeMap& _order;
1252 : : int _num;
1253 : : };
1254 : :
1255 : : }
1256 : :
1257 : : /// \ingroup graph_properties
1258 : : ///
1259 : : /// \brief Check whether a digraph is DAG.
1260 : : ///
1261 : : /// This function checks whether the given digraph is DAG, i.e.
1262 : : /// \e Directed \e Acyclic \e Graph.
1263 : : /// \return \c true if there is no directed cycle in the digraph.
1264 : : /// \see acyclic()
1265 : : template <typename Digraph>
1266 : : bool dag(const Digraph& digraph) {
1267 : :
1268 : : checkConcept<concepts::Digraph, Digraph>();
1269 : :
1270 : : typedef typename Digraph::Node Node;
1271 : : typedef typename Digraph::NodeIt NodeIt;
1272 : : typedef typename Digraph::Arc Arc;
1273 : :
1274 : : typedef typename Digraph::template NodeMap<bool> ProcessedMap;
1275 : :
1276 : : typename Dfs<Digraph>::template SetProcessedMap<ProcessedMap>::
1277 : : Create dfs(digraph);
1278 : :
1279 : : ProcessedMap processed(digraph);
1280 : : dfs.processedMap(processed);
1281 : :
1282 : : dfs.init();
1283 : : for (NodeIt it(digraph); it != INVALID; ++it) {
1284 : : if (!dfs.reached(it)) {
1285 : : dfs.addSource(it);
1286 : : while (!dfs.emptyQueue()) {
1287 : : Arc arc = dfs.nextArc();
1288 : : Node target = digraph.target(arc);
1289 : : if (dfs.reached(target) && !processed[target]) {
1290 : : return false;
1291 : : }
1292 : : dfs.processNextArc();
1293 : : }
1294 : : }
1295 : : }
1296 : : return true;
1297 : : }
1298 : :
1299 : : /// \ingroup graph_properties
1300 : : ///
1301 : : /// \brief Sort the nodes of a DAG into topolgical order.
1302 : : ///
1303 : : /// This function sorts the nodes of the given acyclic digraph (DAG)
1304 : : /// into topolgical order.
1305 : : ///
1306 : : /// \param digraph The digraph, which must be DAG.
1307 : : /// \retval order A writable node map. The values will be set from 0 to
1308 : : /// the number of the nodes in the digraph minus one. Each value of the
1309 : : /// map will be set exactly once, and the values will be set descending
1310 : : /// order.
1311 : : ///
1312 : : /// \see dag(), checkedTopologicalSort()
1313 : : template <typename Digraph, typename NodeMap>
1314 : 51 : void topologicalSort(const Digraph& digraph, NodeMap& order) {
1315 : : using namespace _connectivity_bits;
1316 : :
1317 [ + - ]: 51 : checkConcept<concepts::Digraph, Digraph>();
1318 [ + - ]: 51 : checkConcept<concepts::WriteMap<typename Digraph::Node, int>, NodeMap>();
1319 : :
1320 : : typedef typename Digraph::NodeIt NodeIt;
1321 : :
1322 : : TopologicalSortVisitor<Digraph, NodeMap>
1323 [ + - ][ + - ]: 51 : visitor(order, countNodes(digraph));
1324 : :
1325 : : DfsVisit<Digraph, TopologicalSortVisitor<Digraph, NodeMap> >
1326 [ + - ]: 51 : dfs(digraph, visitor);
1327 : :
1328 [ + - ]: 51 : dfs.init();
1329 [ + - ][ + - ]: 321 : for (NodeIt it(digraph); it != INVALID; ++it) {
[ + - ][ + - ]
[ + + ]
1330 [ + - ][ + + ]: 270 : if (!dfs.reached(it)) {
1331 [ + - ]: 114 : dfs.addSource(it);
1332 [ + - ]: 114 : dfs.start();
1333 : : }
1334 : 51 : }
1335 : 51 : }
1336 : :
1337 : : /// \ingroup graph_properties
1338 : : ///
1339 : : /// \brief Sort the nodes of a DAG into topolgical order.
1340 : : ///
1341 : : /// This function sorts the nodes of the given acyclic digraph (DAG)
1342 : : /// into topolgical order and also checks whether the given digraph
1343 : : /// is DAG.
1344 : : ///
1345 : : /// \param digraph The digraph.
1346 : : /// \retval order A readable and writable node map. The values will be
1347 : : /// set from 0 to the number of the nodes in the digraph minus one.
1348 : : /// Each value of the map will be set exactly once, and the values will
1349 : : /// be set descending order.
1350 : : /// \return \c false if the digraph is not DAG.
1351 : : ///
1352 : : /// \see dag(), topologicalSort()
1353 : : template <typename Digraph, typename NodeMap>
1354 : : bool checkedTopologicalSort(const Digraph& digraph, NodeMap& order) {
1355 : : using namespace _connectivity_bits;
1356 : :
1357 : : checkConcept<concepts::Digraph, Digraph>();
1358 : : checkConcept<concepts::ReadWriteMap<typename Digraph::Node, int>,
1359 : : NodeMap>();
1360 : :
1361 : : typedef typename Digraph::Node Node;
1362 : : typedef typename Digraph::NodeIt NodeIt;
1363 : : typedef typename Digraph::Arc Arc;
1364 : :
1365 : : for (NodeIt it(digraph); it != INVALID; ++it) {
1366 : : order.set(it, -1);
1367 : : }
1368 : :
1369 : : TopologicalSortVisitor<Digraph, NodeMap>
1370 : : visitor(order, countNodes(digraph));
1371 : :
1372 : : DfsVisit<Digraph, TopologicalSortVisitor<Digraph, NodeMap> >
1373 : : dfs(digraph, visitor);
1374 : :
1375 : : dfs.init();
1376 : : for (NodeIt it(digraph); it != INVALID; ++it) {
1377 : : if (!dfs.reached(it)) {
1378 : : dfs.addSource(it);
1379 : : while (!dfs.emptyQueue()) {
1380 : : Arc arc = dfs.nextArc();
1381 : : Node target = digraph.target(arc);
1382 : : if (dfs.reached(target) && order[target] == -1) {
1383 : : return false;
1384 : : }
1385 : : dfs.processNextArc();
1386 : : }
1387 : : }
1388 : : }
1389 : : return true;
1390 : : }
1391 : :
1392 : : /// \ingroup graph_properties
1393 : : ///
1394 : : /// \brief Check whether an undirected graph is acyclic.
1395 : : ///
1396 : : /// This function checks whether the given undirected graph is acyclic.
1397 : : /// \return \c true if there is no cycle in the graph.
1398 : : /// \see dag()
1399 : : template <typename Graph>
1400 : : bool acyclic(const Graph& graph) {
1401 : : checkConcept<concepts::Graph, Graph>();
1402 : : typedef typename Graph::Node Node;
1403 : : typedef typename Graph::NodeIt NodeIt;
1404 : : typedef typename Graph::Arc Arc;
1405 : : Dfs<Graph> dfs(graph);
1406 : : dfs.init();
1407 : : for (NodeIt it(graph); it != INVALID; ++it) {
1408 : : if (!dfs.reached(it)) {
1409 : : dfs.addSource(it);
1410 : : while (!dfs.emptyQueue()) {
1411 : : Arc arc = dfs.nextArc();
1412 : : Node source = graph.source(arc);
1413 : : Node target = graph.target(arc);
1414 : : if (dfs.reached(target) &&
1415 : : dfs.predArc(source) != graph.oppositeArc(arc)) {
1416 : : return false;
1417 : : }
1418 : : dfs.processNextArc();
1419 : : }
1420 : : }
1421 : : }
1422 : : return true;
1423 : : }
1424 : :
1425 : : /// \ingroup graph_properties
1426 : : ///
1427 : : /// \brief Check whether an undirected graph is tree.
1428 : : ///
1429 : : /// This function checks whether the given undirected graph is tree.
1430 : : /// \return \c true if the graph is acyclic and connected.
1431 : : /// \see acyclic(), connected()
1432 : : template <typename Graph>
1433 : : bool tree(const Graph& graph) {
1434 : : checkConcept<concepts::Graph, Graph>();
1435 : : typedef typename Graph::Node Node;
1436 : : typedef typename Graph::NodeIt NodeIt;
1437 : : typedef typename Graph::Arc Arc;
1438 : : if (NodeIt(graph) == INVALID) return true;
1439 : : Dfs<Graph> dfs(graph);
1440 : : dfs.init();
1441 : : dfs.addSource(NodeIt(graph));
1442 : : while (!dfs.emptyQueue()) {
1443 : : Arc arc = dfs.nextArc();
1444 : : Node source = graph.source(arc);
1445 : : Node target = graph.target(arc);
1446 : : if (dfs.reached(target) &&
1447 : : dfs.predArc(source) != graph.oppositeArc(arc)) {
1448 : : return false;
1449 : : }
1450 : : dfs.processNextArc();
1451 : : }
1452 : : for (NodeIt it(graph); it != INVALID; ++it) {
1453 : : if (!dfs.reached(it)) {
1454 : : return false;
1455 : : }
1456 : : }
1457 : : return true;
1458 : : }
1459 : :
1460 : : namespace _connectivity_bits {
1461 : :
1462 : : template <typename Digraph>
1463 : : class BipartiteVisitor : public BfsVisitor<Digraph> {
1464 : : public:
1465 : : typedef typename Digraph::Arc Arc;
1466 : : typedef typename Digraph::Node Node;
1467 : :
1468 : : BipartiteVisitor(const Digraph& graph, bool& bipartite)
1469 : : : _graph(graph), _part(graph), _bipartite(bipartite) {}
1470 : :
1471 : : void start(const Node& node) {
1472 : : _part[node] = true;
1473 : : }
1474 : : void discover(const Arc& edge) {
1475 : : _part.set(_graph.target(edge), !_part[_graph.source(edge)]);
1476 : : }
1477 : : void examine(const Arc& edge) {
1478 : : _bipartite = _bipartite &&
1479 : : _part[_graph.target(edge)] != _part[_graph.source(edge)];
1480 : : }
1481 : :
1482 : : private:
1483 : :
1484 : : const Digraph& _graph;
1485 : : typename Digraph::template NodeMap<bool> _part;
1486 : : bool& _bipartite;
1487 : : };
1488 : :
1489 : : template <typename Digraph, typename PartMap>
1490 : : class BipartitePartitionsVisitor : public BfsVisitor<Digraph> {
1491 : : public:
1492 : : typedef typename Digraph::Arc Arc;
1493 : : typedef typename Digraph::Node Node;
1494 : :
1495 : : BipartitePartitionsVisitor(const Digraph& graph,
1496 : : PartMap& part, bool& bipartite)
1497 : : : _graph(graph), _part(part), _bipartite(bipartite) {}
1498 : :
1499 : : void start(const Node& node) {
1500 : : _part.set(node, true);
1501 : : }
1502 : : void discover(const Arc& edge) {
1503 : : _part.set(_graph.target(edge), !_part[_graph.source(edge)]);
1504 : : }
1505 : : void examine(const Arc& edge) {
1506 : : _bipartite = _bipartite &&
1507 : : _part[_graph.target(edge)] != _part[_graph.source(edge)];
1508 : : }
1509 : :
1510 : : private:
1511 : :
1512 : : const Digraph& _graph;
1513 : : PartMap& _part;
1514 : : bool& _bipartite;
1515 : : };
1516 : : }
1517 : :
1518 : : /// \ingroup graph_properties
1519 : : ///
1520 : : /// \brief Check whether an undirected graph is bipartite.
1521 : : ///
1522 : : /// The function checks whether the given undirected graph is bipartite.
1523 : : /// \return \c true if the graph is bipartite.
1524 : : ///
1525 : : /// \see bipartitePartitions()
1526 : : template<typename Graph>
1527 : : bool bipartite(const Graph &graph){
1528 : : using namespace _connectivity_bits;
1529 : :
1530 : : checkConcept<concepts::Graph, Graph>();
1531 : :
1532 : : typedef typename Graph::NodeIt NodeIt;
1533 : :
1534 : : bool bipartite = true;
1535 : :
1536 : : BipartiteVisitor<Graph>
1537 : : visitor(graph, bipartite);
1538 : : BfsVisit<Graph, BipartiteVisitor<Graph> >
1539 : : bfs(graph, visitor);
1540 : : bfs.init();
1541 : : for(NodeIt it(graph); it != INVALID; ++it) {
1542 : : if(!bfs.reached(it)){
1543 : : bfs.addSource(it);
1544 : : while (!bfs.emptyQueue()) {
1545 : : bfs.processNextNode();
1546 : : if (!bipartite) return false;
1547 : : }
1548 : : }
1549 : : }
1550 : : return true;
1551 : : }
1552 : :
1553 : : /// \ingroup graph_properties
1554 : : ///
1555 : : /// \brief Find the bipartite partitions of an undirected graph.
1556 : : ///
1557 : : /// This function checks whether the given undirected graph is bipartite
1558 : : /// and gives back the bipartite partitions.
1559 : : ///
1560 : : /// \image html bipartite_partitions.png
1561 : : /// \image latex bipartite_partitions.eps "Bipartite partititions" width=\textwidth
1562 : : ///
1563 : : /// \param graph The undirected graph.
1564 : : /// \retval partMap A writable node map of \c bool (or convertible) value
1565 : : /// type. The values will be set to \c true for one component and
1566 : : /// \c false for the other one.
1567 : : /// \return \c true if the graph is bipartite, \c false otherwise.
1568 : : ///
1569 : : /// \see bipartite()
1570 : : template<typename Graph, typename NodeMap>
1571 : : bool bipartitePartitions(const Graph &graph, NodeMap &partMap){
1572 : : using namespace _connectivity_bits;
1573 : :
1574 : : checkConcept<concepts::Graph, Graph>();
1575 : : checkConcept<concepts::WriteMap<typename Graph::Node, bool>, NodeMap>();
1576 : :
1577 : : typedef typename Graph::NodeIt NodeIt;
1578 : :
1579 : : bool bipartite = true;
1580 : :
1581 : : BipartitePartitionsVisitor<Graph, NodeMap>
1582 : : visitor(graph, partMap, bipartite);
1583 : : BfsVisit<Graph, BipartitePartitionsVisitor<Graph, NodeMap> >
1584 : : bfs(graph, visitor);
1585 : : bfs.init();
1586 : : for(NodeIt it(graph); it != INVALID; ++it) {
1587 : : if(!bfs.reached(it)){
1588 : : bfs.addSource(it);
1589 : : while (!bfs.emptyQueue()) {
1590 : : bfs.processNextNode();
1591 : : if (!bipartite) return false;
1592 : : }
1593 : : }
1594 : : }
1595 : : return true;
1596 : : }
1597 : :
1598 : : /// \ingroup graph_properties
1599 : : ///
1600 : : /// \brief Check whether the given graph contains no loop arcs/edges.
1601 : : ///
1602 : : /// This function returns \c true if there are no loop arcs/edges in
1603 : : /// the given graph. It works for both directed and undirected graphs.
1604 : : template <typename Graph>
1605 : : bool loopFree(const Graph& graph) {
1606 : : for (typename Graph::ArcIt it(graph); it != INVALID; ++it) {
1607 : : if (graph.source(it) == graph.target(it)) return false;
1608 : : }
1609 : : return true;
1610 : : }
1611 : :
1612 : : /// \ingroup graph_properties
1613 : : ///
1614 : : /// \brief Check whether the given graph contains no parallel arcs/edges.
1615 : : ///
1616 : : /// This function returns \c true if there are no parallel arcs/edges in
1617 : : /// the given graph. It works for both directed and undirected graphs.
1618 : : template <typename Graph>
1619 : : bool parallelFree(const Graph& graph) {
1620 : : typename Graph::template NodeMap<int> reached(graph, 0);
1621 : : int cnt = 1;
1622 : : for (typename Graph::NodeIt n(graph); n != INVALID; ++n) {
1623 : : for (typename Graph::OutArcIt a(graph, n); a != INVALID; ++a) {
1624 : : if (reached[graph.target(a)] == cnt) return false;
1625 : : reached[graph.target(a)] = cnt;
1626 : : }
1627 : : ++cnt;
1628 : : }
1629 : : return true;
1630 : : }
1631 : :
1632 : : /// \ingroup graph_properties
1633 : : ///
1634 : : /// \brief Check whether the given graph is simple.
1635 : : ///
1636 : : /// This function returns \c true if the given graph is simple, i.e.
1637 : : /// it contains no loop arcs/edges and no parallel arcs/edges.
1638 : : /// The function works for both directed and undirected graphs.
1639 : : /// \see loopFree(), parallelFree()
1640 : : template <typename Graph>
1641 : : bool simpleGraph(const Graph& graph) {
1642 : : typename Graph::template NodeMap<int> reached(graph, 0);
1643 : : int cnt = 1;
1644 : : for (typename Graph::NodeIt n(graph); n != INVALID; ++n) {
1645 : : reached[n] = cnt;
1646 : : for (typename Graph::OutArcIt a(graph, n); a != INVALID; ++a) {
1647 : : if (reached[graph.target(a)] == cnt) return false;
1648 : : reached[graph.target(a)] = cnt;
1649 : : }
1650 : : ++cnt;
1651 : : }
1652 : : return true;
1653 : : }
1654 : :
1655 : : } //namespace lemon
1656 : :
1657 : : #endif //LEMON_CONNECTIVITY_H
|
