1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
3 * This file is a part of LEMON, a generic C++ optimization library.
5 * Copyright (C) 2003-2009
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
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.
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
19 #ifndef LEMON_CONNECTIVITY_H
20 #define LEMON_CONNECTIVITY_H
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>
28 #include <lemon/concepts/digraph.h>
29 #include <lemon/concepts/graph.h>
30 #include <lemon/concept_check.h>
35 /// \ingroup graph_properties
37 /// \brief Connectivity algorithms
39 /// Connectivity algorithms
43 /// \ingroup graph_properties
45 /// \brief Check whether an undirected graph is connected.
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.
50 /// \return \c true if the graph is connected.
51 /// \note By definition, the empty graph is connected.
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)) {
70 /// \ingroup graph_properties
72 /// \brief Count the number of connected components of an undirected graph
74 /// This function counts the number of connected components of the given
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.
81 /// \return The number of connected components.
82 /// \note By definition, the empty graph consists
83 /// of zero connected components.
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;
92 typedef NullMap<Node, Arc> PredMap;
93 typedef NullMap<Node, int> DistMap;
97 template SetPredMap<PredMap>::
98 template SetDistMap<DistMap>::
102 bfs.predMap(predMap);
105 bfs.distMap(distMap);
108 for(typename Graph::NodeIt n(graph); n != INVALID; ++n) {
109 if (!bfs.reached(n)) {
118 /// \ingroup graph_properties
120 /// \brief Find the connected components of an undirected graph
122 /// This function finds the connected components of the given undirected
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.
129 /// \image html connected_components.png
130 /// \image latex connected_components.eps "Connected components" width=\textwidth
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.
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>();
149 typedef NullMap<Node, Arc> PredMap;
150 typedef NullMap<Node, int> DistMap;
153 typename Bfs<Graph>::
154 template SetPredMap<PredMap>::
155 template SetDistMap<DistMap>::
159 bfs.predMap(predMap);
162 bfs.distMap(distMap);
165 for(typename Graph::NodeIt n(graph); n != INVALID; ++n) {
166 if(!bfs.reached(n)) {
168 while (!bfs.emptyQueue()) {
169 compMap.set(bfs.nextNode(), compNum);
170 bfs.processNextNode();
178 namespace _connectivity_bits {
180 template <typename Digraph, typename Iterator >
181 struct LeaveOrderVisitor : public DfsVisitor<Digraph> {
183 typedef typename Digraph::Node Node;
184 LeaveOrderVisitor(Iterator it) : _it(it) {}
186 void leave(const Node& node) {
194 template <typename Digraph, typename Map>
195 struct FillMapVisitor : public DfsVisitor<Digraph> {
197 typedef typename Digraph::Node Node;
198 typedef typename Map::Value Value;
200 FillMapVisitor(Map& map, Value& value)
201 : _map(map), _value(value) {}
203 void reach(const Node& node) {
204 _map.set(node, _value);
211 template <typename Digraph, typename ArcMap>
212 struct StronglyConnectedCutArcsVisitor : public DfsVisitor<Digraph> {
214 typedef typename Digraph::Node Node;
215 typedef typename Digraph::Arc Arc;
217 StronglyConnectedCutArcsVisitor(const Digraph& digraph,
220 : _digraph(digraph), _cutMap(cutMap), _cutNum(cutNum),
221 _compMap(digraph, -1), _num(-1) {
224 void start(const Node&) {
228 void reach(const Node& node) {
229 _compMap.set(node, _num);
232 void examine(const Arc& arc) {
233 if (_compMap[_digraph.source(arc)] !=
234 _compMap[_digraph.target(arc)]) {
235 _cutMap.set(arc, true);
240 const Digraph& _digraph;
244 typename Digraph::template NodeMap<int> _compMap;
251 /// \ingroup graph_properties
253 /// \brief Check whether a directed graph is strongly connected.
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.
259 /// \return \c true if the digraph is strongly connected.
260 /// \note By definition, the empty digraph is strongly connected.
262 /// \see countStronglyConnectedComponents(), stronglyConnectedComponents()
264 template <typename Digraph>
265 bool stronglyConnected(const Digraph& digraph) {
266 checkConcept<concepts::Digraph, Digraph>();
268 typedef typename Digraph::Node Node;
269 typedef typename Digraph::NodeIt NodeIt;
271 typename Digraph::Node source = NodeIt(digraph);
272 if (source == INVALID) return true;
274 using namespace _connectivity_bits;
276 typedef DfsVisitor<Digraph> Visitor;
279 DfsVisit<Digraph, Visitor> dfs(digraph, visitor);
281 dfs.addSource(source);
284 for (NodeIt it(digraph); it != INVALID; ++it) {
285 if (!dfs.reached(it)) {
290 typedef ReverseDigraph<const Digraph> RDigraph;
291 typedef typename RDigraph::NodeIt RNodeIt;
292 RDigraph rdigraph(digraph);
294 typedef DfsVisitor<RDigraph> RVisitor;
297 DfsVisit<RDigraph, RVisitor> rdfs(rdigraph, rvisitor);
299 rdfs.addSource(source);
302 for (RNodeIt it(rdigraph); it != INVALID; ++it) {
303 if (!rdfs.reached(it)) {
311 /// \ingroup graph_properties
313 /// \brief Count the number of strongly connected components of a
316 /// This function counts the number of strongly connected components of
317 /// the given directed graph.
319 /// The strongly connected components are the classes of an
320 /// equivalence relation on the nodes of a digraph. Two nodes are in
321 /// the same class if they are connected with directed paths in both
324 /// \return The number of strongly connected components.
325 /// \note By definition, the empty digraph has zero
326 /// strongly connected components.
328 /// \see stronglyConnected(), stronglyConnectedComponents()
329 template <typename Digraph>
330 int countStronglyConnectedComponents(const Digraph& digraph) {
331 checkConcept<concepts::Digraph, Digraph>();
333 using namespace _connectivity_bits;
335 typedef typename Digraph::Node Node;
336 typedef typename Digraph::Arc Arc;
337 typedef typename Digraph::NodeIt NodeIt;
338 typedef typename Digraph::ArcIt ArcIt;
340 typedef std::vector<Node> Container;
341 typedef typename Container::iterator Iterator;
343 Container nodes(countNodes(digraph));
344 typedef LeaveOrderVisitor<Digraph, Iterator> Visitor;
345 Visitor visitor(nodes.begin());
347 DfsVisit<Digraph, Visitor> dfs(digraph, visitor);
349 for (NodeIt it(digraph); it != INVALID; ++it) {
350 if (!dfs.reached(it)) {
356 typedef typename Container::reverse_iterator RIterator;
357 typedef ReverseDigraph<const Digraph> RDigraph;
359 RDigraph rdigraph(digraph);
361 typedef DfsVisitor<Digraph> RVisitor;
364 DfsVisit<RDigraph, RVisitor> rdfs(rdigraph, rvisitor);
369 for (RIterator it = nodes.rbegin(); it != nodes.rend(); ++it) {
370 if (!rdfs.reached(*it)) {
379 /// \ingroup graph_properties
381 /// \brief Find the strongly connected components of a directed graph
383 /// This function finds the strongly connected components of the given
384 /// directed graph. In addition, the numbering of the components will
385 /// satisfy that there is no arc going from a higher numbered component
386 /// to a lower one (i.e. it provides a topological order of the components).
388 /// The strongly connected components are the classes of an
389 /// equivalence relation on the nodes of a digraph. Two nodes are in
390 /// the same class if they are connected with directed paths in both
393 /// \image html strongly_connected_components.png
394 /// \image latex strongly_connected_components.eps "Strongly connected components" width=\textwidth
396 /// \param digraph The digraph.
397 /// \retval compMap A writable node map. The values will be set from 0 to
398 /// the number of the strongly connected components minus one. Each value
399 /// of the map will be set exactly once, and the values of a certain
400 /// component will be set continuously.
401 /// \return The number of strongly connected components.
402 /// \note By definition, the empty digraph has zero
403 /// strongly connected components.
405 /// \see stronglyConnected(), countStronglyConnectedComponents()
406 template <typename Digraph, typename NodeMap>
407 int stronglyConnectedComponents(const Digraph& digraph, NodeMap& compMap) {
408 checkConcept<concepts::Digraph, Digraph>();
409 typedef typename Digraph::Node Node;
410 typedef typename Digraph::NodeIt NodeIt;
411 checkConcept<concepts::WriteMap<Node, int>, NodeMap>();
413 using namespace _connectivity_bits;
415 typedef std::vector<Node> Container;
416 typedef typename Container::iterator Iterator;
418 Container nodes(countNodes(digraph));
419 typedef LeaveOrderVisitor<Digraph, Iterator> Visitor;
420 Visitor visitor(nodes.begin());
422 DfsVisit<Digraph, Visitor> dfs(digraph, visitor);
424 for (NodeIt it(digraph); it != INVALID; ++it) {
425 if (!dfs.reached(it)) {
431 typedef typename Container::reverse_iterator RIterator;
432 typedef ReverseDigraph<const Digraph> RDigraph;
434 RDigraph rdigraph(digraph);
438 typedef FillMapVisitor<RDigraph, NodeMap> RVisitor;
439 RVisitor rvisitor(compMap, compNum);
441 DfsVisit<RDigraph, RVisitor> rdfs(rdigraph, rvisitor);
444 for (RIterator it = nodes.rbegin(); it != nodes.rend(); ++it) {
445 if (!rdfs.reached(*it)) {
454 /// \ingroup graph_properties
456 /// \brief Find the cut arcs of the strongly connected components.
458 /// This function finds the cut arcs of the strongly connected components
459 /// of the given digraph.
461 /// The strongly connected components are the classes of an
462 /// equivalence relation on the nodes of a digraph. Two nodes are in
463 /// the same class if they are connected with directed paths in both
465 /// The strongly connected components are separated by the cut arcs.
467 /// \param digraph The digraph.
468 /// \retval cutMap A writable arc map. The values will be set to \c true
469 /// for the cut arcs (exactly once for each cut arc), and will not be
470 /// changed for other arcs.
471 /// \return The number of cut arcs.
473 /// \see stronglyConnected(), stronglyConnectedComponents()
474 template <typename Digraph, typename ArcMap>
475 int stronglyConnectedCutArcs(const Digraph& digraph, ArcMap& cutMap) {
476 checkConcept<concepts::Digraph, Digraph>();
477 typedef typename Digraph::Node Node;
478 typedef typename Digraph::Arc Arc;
479 typedef typename Digraph::NodeIt NodeIt;
480 checkConcept<concepts::WriteMap<Arc, bool>, ArcMap>();
482 using namespace _connectivity_bits;
484 typedef std::vector<Node> Container;
485 typedef typename Container::iterator Iterator;
487 Container nodes(countNodes(digraph));
488 typedef LeaveOrderVisitor<Digraph, Iterator> Visitor;
489 Visitor visitor(nodes.begin());
491 DfsVisit<Digraph, Visitor> dfs(digraph, visitor);
493 for (NodeIt it(digraph); it != INVALID; ++it) {
494 if (!dfs.reached(it)) {
500 typedef typename Container::reverse_iterator RIterator;
501 typedef ReverseDigraph<const Digraph> RDigraph;
503 RDigraph rdigraph(digraph);
507 typedef StronglyConnectedCutArcsVisitor<RDigraph, ArcMap> RVisitor;
508 RVisitor rvisitor(rdigraph, cutMap, cutNum);
510 DfsVisit<RDigraph, RVisitor> rdfs(rdigraph, rvisitor);
513 for (RIterator it = nodes.rbegin(); it != nodes.rend(); ++it) {
514 if (!rdfs.reached(*it)) {
522 namespace _connectivity_bits {
524 template <typename Digraph>
525 class CountBiNodeConnectedComponentsVisitor : public DfsVisitor<Digraph> {
527 typedef typename Digraph::Node Node;
528 typedef typename Digraph::Arc Arc;
529 typedef typename Digraph::Edge Edge;
531 CountBiNodeConnectedComponentsVisitor(const Digraph& graph, int &compNum)
532 : _graph(graph), _compNum(compNum),
533 _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
535 void start(const Node& node) {
536 _predMap.set(node, INVALID);
539 void reach(const Node& node) {
540 _numMap.set(node, _num);
541 _retMap.set(node, _num);
545 void discover(const Arc& edge) {
546 _predMap.set(_graph.target(edge), _graph.source(edge));
549 void examine(const Arc& edge) {
550 if (_graph.source(edge) == _graph.target(edge) &&
551 _graph.direction(edge)) {
555 if (_predMap[_graph.source(edge)] == _graph.target(edge)) {
558 if (_retMap[_graph.source(edge)] > _numMap[_graph.target(edge)]) {
559 _retMap.set(_graph.source(edge), _numMap[_graph.target(edge)]);
563 void backtrack(const Arc& edge) {
564 if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
565 _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
567 if (_numMap[_graph.source(edge)] <= _retMap[_graph.target(edge)]) {
573 const Digraph& _graph;
576 typename Digraph::template NodeMap<int> _numMap;
577 typename Digraph::template NodeMap<int> _retMap;
578 typename Digraph::template NodeMap<Node> _predMap;
582 template <typename Digraph, typename ArcMap>
583 class BiNodeConnectedComponentsVisitor : public DfsVisitor<Digraph> {
585 typedef typename Digraph::Node Node;
586 typedef typename Digraph::Arc Arc;
587 typedef typename Digraph::Edge Edge;
589 BiNodeConnectedComponentsVisitor(const Digraph& graph,
590 ArcMap& compMap, int &compNum)
591 : _graph(graph), _compMap(compMap), _compNum(compNum),
592 _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
594 void start(const Node& node) {
595 _predMap.set(node, INVALID);
598 void reach(const Node& node) {
599 _numMap.set(node, _num);
600 _retMap.set(node, _num);
604 void discover(const Arc& edge) {
605 Node target = _graph.target(edge);
606 _predMap.set(target, edge);
607 _edgeStack.push(edge);
610 void examine(const Arc& edge) {
611 Node source = _graph.source(edge);
612 Node target = _graph.target(edge);
613 if (source == target && _graph.direction(edge)) {
614 _compMap.set(edge, _compNum);
618 if (_numMap[target] < _numMap[source]) {
619 if (_predMap[source] != _graph.oppositeArc(edge)) {
620 _edgeStack.push(edge);
623 if (_predMap[source] != INVALID &&
624 target == _graph.source(_predMap[source])) {
627 if (_retMap[source] > _numMap[target]) {
628 _retMap.set(source, _numMap[target]);
632 void backtrack(const Arc& edge) {
633 Node source = _graph.source(edge);
634 Node target = _graph.target(edge);
635 if (_retMap[source] > _retMap[target]) {
636 _retMap.set(source, _retMap[target]);
638 if (_numMap[source] <= _retMap[target]) {
639 while (_edgeStack.top() != edge) {
640 _compMap.set(_edgeStack.top(), _compNum);
643 _compMap.set(edge, _compNum);
650 const Digraph& _graph;
654 typename Digraph::template NodeMap<int> _numMap;
655 typename Digraph::template NodeMap<int> _retMap;
656 typename Digraph::template NodeMap<Arc> _predMap;
657 std::stack<Edge> _edgeStack;
662 template <typename Digraph, typename NodeMap>
663 class BiNodeConnectedCutNodesVisitor : public DfsVisitor<Digraph> {
665 typedef typename Digraph::Node Node;
666 typedef typename Digraph::Arc Arc;
667 typedef typename Digraph::Edge Edge;
669 BiNodeConnectedCutNodesVisitor(const Digraph& graph, NodeMap& cutMap,
671 : _graph(graph), _cutMap(cutMap), _cutNum(cutNum),
672 _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
674 void start(const Node& node) {
675 _predMap.set(node, INVALID);
679 void reach(const Node& node) {
680 _numMap.set(node, _num);
681 _retMap.set(node, _num);
685 void discover(const Arc& edge) {
686 _predMap.set(_graph.target(edge), _graph.source(edge));
689 void examine(const Arc& edge) {
690 if (_graph.source(edge) == _graph.target(edge) &&
691 _graph.direction(edge)) {
692 if (!_cutMap[_graph.source(edge)]) {
693 _cutMap.set(_graph.source(edge), true);
698 if (_predMap[_graph.source(edge)] == _graph.target(edge)) return;
699 if (_retMap[_graph.source(edge)] > _numMap[_graph.target(edge)]) {
700 _retMap.set(_graph.source(edge), _numMap[_graph.target(edge)]);
704 void backtrack(const Arc& edge) {
705 if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
706 _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
708 if (_numMap[_graph.source(edge)] <= _retMap[_graph.target(edge)]) {
709 if (_predMap[_graph.source(edge)] != INVALID) {
710 if (!_cutMap[_graph.source(edge)]) {
711 _cutMap.set(_graph.source(edge), true);
714 } else if (rootCut) {
715 if (!_cutMap[_graph.source(edge)]) {
716 _cutMap.set(_graph.source(edge), true);
726 const Digraph& _graph;
730 typename Digraph::template NodeMap<int> _numMap;
731 typename Digraph::template NodeMap<int> _retMap;
732 typename Digraph::template NodeMap<Node> _predMap;
733 std::stack<Edge> _edgeStack;
740 template <typename Graph>
741 int countBiNodeConnectedComponents(const Graph& graph);
743 /// \ingroup graph_properties
745 /// \brief Check whether an undirected graph is bi-node-connected.
747 /// This function checks whether the given undirected graph is
748 /// bi-node-connected, i.e. a connected graph without articulation
751 /// \return \c true if the graph bi-node-connected.
752 /// \note By definition, the empty graph is bi-node-connected.
754 /// \see countBiNodeConnectedComponents(), biNodeConnectedComponents()
755 template <typename Graph>
756 bool biNodeConnected(const Graph& graph) {
757 bool hasNonIsolated = false, hasIsolated = false;
758 for (typename Graph::NodeIt n(graph); n != INVALID; ++n) {
759 if (typename Graph::OutArcIt(graph, n) == INVALID) {
760 if (hasIsolated || hasNonIsolated) {
769 hasNonIsolated = true;
773 return countBiNodeConnectedComponents(graph) <= 1;
776 /// \ingroup graph_properties
778 /// \brief Count the number of bi-node-connected components of an
779 /// undirected graph.
781 /// This function counts the number of bi-node-connected components of
782 /// the given undirected graph.
784 /// The bi-node-connected components are the classes of an equivalence
785 /// relation on the edges of a undirected graph. Two edges are in the
786 /// same class if they are on same circle.
788 /// \return The number of bi-node-connected components.
790 /// \see biNodeConnected(), biNodeConnectedComponents()
791 template <typename Graph>
792 int countBiNodeConnectedComponents(const Graph& graph) {
793 checkConcept<concepts::Graph, Graph>();
794 typedef typename Graph::NodeIt NodeIt;
796 using namespace _connectivity_bits;
798 typedef CountBiNodeConnectedComponentsVisitor<Graph> Visitor;
801 Visitor visitor(graph, compNum);
803 DfsVisit<Graph, Visitor> dfs(graph, visitor);
806 for (NodeIt it(graph); it != INVALID; ++it) {
807 if (!dfs.reached(it)) {
815 /// \ingroup graph_properties
817 /// \brief Find the bi-node-connected components of an undirected graph.
819 /// This function finds the bi-node-connected components of the given
820 /// undirected graph.
822 /// The bi-node-connected components are the classes of an equivalence
823 /// relation on the edges of a undirected graph. Two edges are in the
824 /// same class if they are on same circle.
826 /// \image html node_biconnected_components.png
827 /// \image latex node_biconnected_components.eps "bi-node-connected components" width=\textwidth
829 /// \param graph The undirected graph.
830 /// \retval compMap A writable edge map. The values will be set from 0
831 /// to the number of the bi-node-connected components minus one. Each
832 /// value of the map will be set exactly once, and the values of a
833 /// certain component will be set continuously.
834 /// \return The number of bi-node-connected components.
836 /// \see biNodeConnected(), countBiNodeConnectedComponents()
837 template <typename Graph, typename EdgeMap>
838 int biNodeConnectedComponents(const Graph& graph,
840 checkConcept<concepts::Graph, Graph>();
841 typedef typename Graph::NodeIt NodeIt;
842 typedef typename Graph::Edge Edge;
843 checkConcept<concepts::WriteMap<Edge, int>, EdgeMap>();
845 using namespace _connectivity_bits;
847 typedef BiNodeConnectedComponentsVisitor<Graph, EdgeMap> Visitor;
850 Visitor visitor(graph, compMap, compNum);
852 DfsVisit<Graph, Visitor> dfs(graph, visitor);
855 for (NodeIt it(graph); it != INVALID; ++it) {
856 if (!dfs.reached(it)) {
864 /// \ingroup graph_properties
866 /// \brief Find the bi-node-connected cut nodes in an undirected graph.
868 /// This function finds the bi-node-connected cut nodes in the given
869 /// undirected graph.
871 /// The bi-node-connected components are the classes of an equivalence
872 /// relation on the edges of a undirected graph. Two edges are in the
873 /// same class if they are on same circle.
874 /// The bi-node-connected components are separted by the cut nodes of
877 /// \param graph The undirected graph.
878 /// \retval cutMap A writable node map. The values will be set to
879 /// \c true for the nodes that separate two or more components
880 /// (exactly once for each cut node), and will not be changed for
882 /// \return The number of the cut nodes.
884 /// \see biNodeConnected(), biNodeConnectedComponents()
885 template <typename Graph, typename NodeMap>
886 int biNodeConnectedCutNodes(const Graph& graph, NodeMap& cutMap) {
887 checkConcept<concepts::Graph, Graph>();
888 typedef typename Graph::Node Node;
889 typedef typename Graph::NodeIt NodeIt;
890 checkConcept<concepts::WriteMap<Node, bool>, NodeMap>();
892 using namespace _connectivity_bits;
894 typedef BiNodeConnectedCutNodesVisitor<Graph, NodeMap> Visitor;
897 Visitor visitor(graph, cutMap, cutNum);
899 DfsVisit<Graph, Visitor> dfs(graph, visitor);
902 for (NodeIt it(graph); it != INVALID; ++it) {
903 if (!dfs.reached(it)) {
911 namespace _connectivity_bits {
913 template <typename Digraph>
914 class CountBiEdgeConnectedComponentsVisitor : public DfsVisitor<Digraph> {
916 typedef typename Digraph::Node Node;
917 typedef typename Digraph::Arc Arc;
918 typedef typename Digraph::Edge Edge;
920 CountBiEdgeConnectedComponentsVisitor(const Digraph& graph, int &compNum)
921 : _graph(graph), _compNum(compNum),
922 _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
924 void start(const Node& node) {
925 _predMap.set(node, INVALID);
928 void reach(const Node& node) {
929 _numMap.set(node, _num);
930 _retMap.set(node, _num);
934 void leave(const Node& node) {
935 if (_numMap[node] <= _retMap[node]) {
940 void discover(const Arc& edge) {
941 _predMap.set(_graph.target(edge), edge);
944 void examine(const Arc& edge) {
945 if (_predMap[_graph.source(edge)] == _graph.oppositeArc(edge)) {
948 if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
949 _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
953 void backtrack(const Arc& edge) {
954 if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
955 _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
960 const Digraph& _graph;
963 typename Digraph::template NodeMap<int> _numMap;
964 typename Digraph::template NodeMap<int> _retMap;
965 typename Digraph::template NodeMap<Arc> _predMap;
969 template <typename Digraph, typename NodeMap>
970 class BiEdgeConnectedComponentsVisitor : public DfsVisitor<Digraph> {
972 typedef typename Digraph::Node Node;
973 typedef typename Digraph::Arc Arc;
974 typedef typename Digraph::Edge Edge;
976 BiEdgeConnectedComponentsVisitor(const Digraph& graph,
977 NodeMap& compMap, int &compNum)
978 : _graph(graph), _compMap(compMap), _compNum(compNum),
979 _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
981 void start(const Node& node) {
982 _predMap.set(node, INVALID);
985 void reach(const Node& node) {
986 _numMap.set(node, _num);
987 _retMap.set(node, _num);
988 _nodeStack.push(node);
992 void leave(const Node& node) {
993 if (_numMap[node] <= _retMap[node]) {
994 while (_nodeStack.top() != node) {
995 _compMap.set(_nodeStack.top(), _compNum);
998 _compMap.set(node, _compNum);
1004 void discover(const Arc& edge) {
1005 _predMap.set(_graph.target(edge), edge);
1008 void examine(const Arc& edge) {
1009 if (_predMap[_graph.source(edge)] == _graph.oppositeArc(edge)) {
1012 if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
1013 _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
1017 void backtrack(const Arc& edge) {
1018 if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
1019 _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
1024 const Digraph& _graph;
1028 typename Digraph::template NodeMap<int> _numMap;
1029 typename Digraph::template NodeMap<int> _retMap;
1030 typename Digraph::template NodeMap<Arc> _predMap;
1031 std::stack<Node> _nodeStack;
1036 template <typename Digraph, typename ArcMap>
1037 class BiEdgeConnectedCutEdgesVisitor : public DfsVisitor<Digraph> {
1039 typedef typename Digraph::Node Node;
1040 typedef typename Digraph::Arc Arc;
1041 typedef typename Digraph::Edge Edge;
1043 BiEdgeConnectedCutEdgesVisitor(const Digraph& graph,
1044 ArcMap& cutMap, int &cutNum)
1045 : _graph(graph), _cutMap(cutMap), _cutNum(cutNum),
1046 _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
1048 void start(const Node& node) {
1049 _predMap[node] = INVALID;
1052 void reach(const Node& node) {
1053 _numMap.set(node, _num);
1054 _retMap.set(node, _num);
1058 void leave(const Node& node) {
1059 if (_numMap[node] <= _retMap[node]) {
1060 if (_predMap[node] != INVALID) {
1061 _cutMap.set(_predMap[node], true);
1067 void discover(const Arc& edge) {
1068 _predMap.set(_graph.target(edge), edge);
1071 void examine(const Arc& edge) {
1072 if (_predMap[_graph.source(edge)] == _graph.oppositeArc(edge)) {
1075 if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
1076 _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
1080 void backtrack(const Arc& edge) {
1081 if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
1082 _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
1087 const Digraph& _graph;
1091 typename Digraph::template NodeMap<int> _numMap;
1092 typename Digraph::template NodeMap<int> _retMap;
1093 typename Digraph::template NodeMap<Arc> _predMap;
1098 template <typename Graph>
1099 int countBiEdgeConnectedComponents(const Graph& graph);
1101 /// \ingroup graph_properties
1103 /// \brief Check whether an undirected graph is bi-edge-connected.
1105 /// This function checks whether the given undirected graph is
1106 /// bi-edge-connected, i.e. any two nodes are connected with at least
1107 /// two edge-disjoint paths.
1109 /// \return \c true if the graph is bi-edge-connected.
1110 /// \note By definition, the empty graph is bi-edge-connected.
1112 /// \see countBiEdgeConnectedComponents(), biEdgeConnectedComponents()
1113 template <typename Graph>
1114 bool biEdgeConnected(const Graph& graph) {
1115 return countBiEdgeConnectedComponents(graph) <= 1;
1118 /// \ingroup graph_properties
1120 /// \brief Count the number of bi-edge-connected components of an
1121 /// undirected graph.
1123 /// This function counts the number of bi-edge-connected components of
1124 /// the given undirected graph.
1126 /// The bi-edge-connected components are the classes of an equivalence
1127 /// relation on the nodes of an undirected graph. Two nodes are in the
1128 /// same class if they are connected with at least two edge-disjoint
1131 /// \return The number of bi-edge-connected components.
1133 /// \see biEdgeConnected(), biEdgeConnectedComponents()
1134 template <typename Graph>
1135 int countBiEdgeConnectedComponents(const Graph& graph) {
1136 checkConcept<concepts::Graph, Graph>();
1137 typedef typename Graph::NodeIt NodeIt;
1139 using namespace _connectivity_bits;
1141 typedef CountBiEdgeConnectedComponentsVisitor<Graph> Visitor;
1144 Visitor visitor(graph, compNum);
1146 DfsVisit<Graph, Visitor> dfs(graph, visitor);
1149 for (NodeIt it(graph); it != INVALID; ++it) {
1150 if (!dfs.reached(it)) {
1158 /// \ingroup graph_properties
1160 /// \brief Find the bi-edge-connected components of an undirected graph.
1162 /// This function finds the bi-edge-connected components of the given
1163 /// undirected graph.
1165 /// The bi-edge-connected components are the classes of an equivalence
1166 /// relation on the nodes of an undirected graph. Two nodes are in the
1167 /// same class if they are connected with at least two edge-disjoint
1170 /// \image html edge_biconnected_components.png
1171 /// \image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth
1173 /// \param graph The undirected graph.
1174 /// \retval compMap A writable node map. The values will be set from 0 to
1175 /// the number of the bi-edge-connected components minus one. Each value
1176 /// of the map will be set exactly once, and the values of a certain
1177 /// component will be set continuously.
1178 /// \return The number of bi-edge-connected components.
1180 /// \see biEdgeConnected(), countBiEdgeConnectedComponents()
1181 template <typename Graph, typename NodeMap>
1182 int biEdgeConnectedComponents(const Graph& graph, NodeMap& compMap) {
1183 checkConcept<concepts::Graph, Graph>();
1184 typedef typename Graph::NodeIt NodeIt;
1185 typedef typename Graph::Node Node;
1186 checkConcept<concepts::WriteMap<Node, int>, NodeMap>();
1188 using namespace _connectivity_bits;
1190 typedef BiEdgeConnectedComponentsVisitor<Graph, NodeMap> Visitor;
1193 Visitor visitor(graph, compMap, compNum);
1195 DfsVisit<Graph, Visitor> dfs(graph, visitor);
1198 for (NodeIt it(graph); it != INVALID; ++it) {
1199 if (!dfs.reached(it)) {
1207 /// \ingroup graph_properties
1209 /// \brief Find the bi-edge-connected cut edges in an undirected graph.
1211 /// This function finds the bi-edge-connected cut edges in the given
1212 /// undirected graph.
1214 /// The bi-edge-connected components are the classes of an equivalence
1215 /// relation on the nodes of an undirected graph. Two nodes are in the
1216 /// same class if they are connected with at least two edge-disjoint
1218 /// The bi-edge-connected components are separted by the cut edges of
1221 /// \param graph The undirected graph.
1222 /// \retval cutMap A writable edge map. The values will be set to \c true
1223 /// for the cut edges (exactly once for each cut edge), and will not be
1224 /// changed for other edges.
1225 /// \return The number of cut edges.
1227 /// \see biEdgeConnected(), biEdgeConnectedComponents()
1228 template <typename Graph, typename EdgeMap>
1229 int biEdgeConnectedCutEdges(const Graph& graph, EdgeMap& cutMap) {
1230 checkConcept<concepts::Graph, Graph>();
1231 typedef typename Graph::NodeIt NodeIt;
1232 typedef typename Graph::Edge Edge;
1233 checkConcept<concepts::WriteMap<Edge, bool>, EdgeMap>();
1235 using namespace _connectivity_bits;
1237 typedef BiEdgeConnectedCutEdgesVisitor<Graph, EdgeMap> Visitor;
1240 Visitor visitor(graph, cutMap, cutNum);
1242 DfsVisit<Graph, Visitor> dfs(graph, visitor);
1245 for (NodeIt it(graph); it != INVALID; ++it) {
1246 if (!dfs.reached(it)) {
1255 namespace _connectivity_bits {
1257 template <typename Digraph, typename IntNodeMap>
1258 class TopologicalSortVisitor : public DfsVisitor<Digraph> {
1260 typedef typename Digraph::Node Node;
1261 typedef typename Digraph::Arc edge;
1263 TopologicalSortVisitor(IntNodeMap& order, int num)
1264 : _order(order), _num(num) {}
1266 void leave(const Node& node) {
1267 _order.set(node, --_num);
1277 /// \ingroup graph_properties
1279 /// \brief Check whether a digraph is DAG.
1281 /// This function checks whether the given digraph is DAG, i.e.
1282 /// \e Directed \e Acyclic \e Graph.
1283 /// \return \c true if there is no directed cycle in the digraph.
1285 template <typename Digraph>
1286 bool dag(const Digraph& digraph) {
1288 checkConcept<concepts::Digraph, Digraph>();
1290 typedef typename Digraph::Node Node;
1291 typedef typename Digraph::NodeIt NodeIt;
1292 typedef typename Digraph::Arc Arc;
1294 typedef typename Digraph::template NodeMap<bool> ProcessedMap;
1296 typename Dfs<Digraph>::template SetProcessedMap<ProcessedMap>::
1297 Create dfs(digraph);
1299 ProcessedMap processed(digraph);
1300 dfs.processedMap(processed);
1303 for (NodeIt it(digraph); it != INVALID; ++it) {
1304 if (!dfs.reached(it)) {
1306 while (!dfs.emptyQueue()) {
1307 Arc arc = dfs.nextArc();
1308 Node target = digraph.target(arc);
1309 if (dfs.reached(target) && !processed[target]) {
1312 dfs.processNextArc();
1319 /// \ingroup graph_properties
1321 /// \brief Sort the nodes of a DAG into topolgical order.
1323 /// This function sorts the nodes of the given acyclic digraph (DAG)
1324 /// into topolgical order.
1326 /// \param digraph The digraph, which must be DAG.
1327 /// \retval order A writable node map. The values will be set from 0 to
1328 /// the number of the nodes in the digraph minus one. Each value of the
1329 /// map will be set exactly once, and the values will be set descending
1332 /// \see dag(), checkedTopologicalSort()
1333 template <typename Digraph, typename NodeMap>
1334 void topologicalSort(const Digraph& digraph, NodeMap& order) {
1335 using namespace _connectivity_bits;
1337 checkConcept<concepts::Digraph, Digraph>();
1338 checkConcept<concepts::WriteMap<typename Digraph::Node, int>, NodeMap>();
1340 typedef typename Digraph::Node Node;
1341 typedef typename Digraph::NodeIt NodeIt;
1342 typedef typename Digraph::Arc Arc;
1344 TopologicalSortVisitor<Digraph, NodeMap>
1345 visitor(order, countNodes(digraph));
1347 DfsVisit<Digraph, TopologicalSortVisitor<Digraph, NodeMap> >
1348 dfs(digraph, visitor);
1351 for (NodeIt it(digraph); it != INVALID; ++it) {
1352 if (!dfs.reached(it)) {
1359 /// \ingroup graph_properties
1361 /// \brief Sort the nodes of a DAG into topolgical order.
1363 /// This function sorts the nodes of the given acyclic digraph (DAG)
1364 /// into topolgical order and also checks whether the given digraph
1367 /// \param digraph The digraph.
1368 /// \retval order A readable and writable node map. The values will be
1369 /// set from 0 to the number of the nodes in the digraph minus one.
1370 /// Each value of the map will be set exactly once, and the values will
1371 /// be set descending order.
1372 /// \return \c false if the digraph is not DAG.
1374 /// \see dag(), topologicalSort()
1375 template <typename Digraph, typename NodeMap>
1376 bool checkedTopologicalSort(const Digraph& digraph, NodeMap& order) {
1377 using namespace _connectivity_bits;
1379 checkConcept<concepts::Digraph, Digraph>();
1380 checkConcept<concepts::ReadWriteMap<typename Digraph::Node, int>,
1383 typedef typename Digraph::Node Node;
1384 typedef typename Digraph::NodeIt NodeIt;
1385 typedef typename Digraph::Arc Arc;
1387 for (NodeIt it(digraph); it != INVALID; ++it) {
1391 TopologicalSortVisitor<Digraph, NodeMap>
1392 visitor(order, countNodes(digraph));
1394 DfsVisit<Digraph, TopologicalSortVisitor<Digraph, NodeMap> >
1395 dfs(digraph, visitor);
1398 for (NodeIt it(digraph); it != INVALID; ++it) {
1399 if (!dfs.reached(it)) {
1401 while (!dfs.emptyQueue()) {
1402 Arc arc = dfs.nextArc();
1403 Node target = digraph.target(arc);
1404 if (dfs.reached(target) && order[target] == -1) {
1407 dfs.processNextArc();
1414 /// \ingroup graph_properties
1416 /// \brief Check whether an undirected graph is acyclic.
1418 /// This function checks whether the given undirected graph is acyclic.
1419 /// \return \c true if there is no cycle in the graph.
1421 template <typename Graph>
1422 bool acyclic(const Graph& graph) {
1423 checkConcept<concepts::Graph, Graph>();
1424 typedef typename Graph::Node Node;
1425 typedef typename Graph::NodeIt NodeIt;
1426 typedef typename Graph::Arc Arc;
1427 Dfs<Graph> dfs(graph);
1429 for (NodeIt it(graph); it != INVALID; ++it) {
1430 if (!dfs.reached(it)) {
1432 while (!dfs.emptyQueue()) {
1433 Arc arc = dfs.nextArc();
1434 Node source = graph.source(arc);
1435 Node target = graph.target(arc);
1436 if (dfs.reached(target) &&
1437 dfs.predArc(source) != graph.oppositeArc(arc)) {
1440 dfs.processNextArc();
1447 /// \ingroup graph_properties
1449 /// \brief Check whether an undirected graph is tree.
1451 /// This function checks whether the given undirected graph is tree.
1452 /// \return \c true if the graph is acyclic and connected.
1453 /// \see acyclic(), connected()
1454 template <typename Graph>
1455 bool tree(const Graph& graph) {
1456 checkConcept<concepts::Graph, Graph>();
1457 typedef typename Graph::Node Node;
1458 typedef typename Graph::NodeIt NodeIt;
1459 typedef typename Graph::Arc Arc;
1460 if (NodeIt(graph) == INVALID) return true;
1461 Dfs<Graph> dfs(graph);
1463 dfs.addSource(NodeIt(graph));
1464 while (!dfs.emptyQueue()) {
1465 Arc arc = dfs.nextArc();
1466 Node source = graph.source(arc);
1467 Node target = graph.target(arc);
1468 if (dfs.reached(target) &&
1469 dfs.predArc(source) != graph.oppositeArc(arc)) {
1472 dfs.processNextArc();
1474 for (NodeIt it(graph); it != INVALID; ++it) {
1475 if (!dfs.reached(it)) {
1482 namespace _connectivity_bits {
1484 template <typename Digraph>
1485 class BipartiteVisitor : public BfsVisitor<Digraph> {
1487 typedef typename Digraph::Arc Arc;
1488 typedef typename Digraph::Node Node;
1490 BipartiteVisitor(const Digraph& graph, bool& bipartite)
1491 : _graph(graph), _part(graph), _bipartite(bipartite) {}
1493 void start(const Node& node) {
1496 void discover(const Arc& edge) {
1497 _part.set(_graph.target(edge), !_part[_graph.source(edge)]);
1499 void examine(const Arc& edge) {
1500 _bipartite = _bipartite &&
1501 _part[_graph.target(edge)] != _part[_graph.source(edge)];
1506 const Digraph& _graph;
1507 typename Digraph::template NodeMap<bool> _part;
1511 template <typename Digraph, typename PartMap>
1512 class BipartitePartitionsVisitor : public BfsVisitor<Digraph> {
1514 typedef typename Digraph::Arc Arc;
1515 typedef typename Digraph::Node Node;
1517 BipartitePartitionsVisitor(const Digraph& graph,
1518 PartMap& part, bool& bipartite)
1519 : _graph(graph), _part(part), _bipartite(bipartite) {}
1521 void start(const Node& node) {
1522 _part.set(node, true);
1524 void discover(const Arc& edge) {
1525 _part.set(_graph.target(edge), !_part[_graph.source(edge)]);
1527 void examine(const Arc& edge) {
1528 _bipartite = _bipartite &&
1529 _part[_graph.target(edge)] != _part[_graph.source(edge)];
1534 const Digraph& _graph;
1540 /// \ingroup graph_properties
1542 /// \brief Check whether an undirected graph is bipartite.
1544 /// The function checks whether the given undirected graph is bipartite.
1545 /// \return \c true if the graph is bipartite.
1547 /// \see bipartitePartitions()
1548 template<typename Graph>
1549 bool bipartite(const Graph &graph){
1550 using namespace _connectivity_bits;
1552 checkConcept<concepts::Graph, Graph>();
1554 typedef typename Graph::NodeIt NodeIt;
1555 typedef typename Graph::ArcIt ArcIt;
1557 bool bipartite = true;
1559 BipartiteVisitor<Graph>
1560 visitor(graph, bipartite);
1561 BfsVisit<Graph, BipartiteVisitor<Graph> >
1562 bfs(graph, visitor);
1564 for(NodeIt it(graph); it != INVALID; ++it) {
1565 if(!bfs.reached(it)){
1567 while (!bfs.emptyQueue()) {
1568 bfs.processNextNode();
1569 if (!bipartite) return false;
1576 /// \ingroup graph_properties
1578 /// \brief Find the bipartite partitions of an undirected graph.
1580 /// This function checks whether the given undirected graph is bipartite
1581 /// and gives back the bipartite partitions.
1583 /// \image html bipartite_partitions.png
1584 /// \image latex bipartite_partitions.eps "Bipartite partititions" width=\textwidth
1586 /// \param graph The undirected graph.
1587 /// \retval partMap A writable node map of \c bool (or convertible) value
1588 /// type. The values will be set to \c true for one component and
1589 /// \c false for the other one.
1590 /// \return \c true if the graph is bipartite, \c false otherwise.
1592 /// \see bipartite()
1593 template<typename Graph, typename NodeMap>
1594 bool bipartitePartitions(const Graph &graph, NodeMap &partMap){
1595 using namespace _connectivity_bits;
1597 checkConcept<concepts::Graph, Graph>();
1598 checkConcept<concepts::WriteMap<typename Graph::Node, bool>, NodeMap>();
1600 typedef typename Graph::Node Node;
1601 typedef typename Graph::NodeIt NodeIt;
1602 typedef typename Graph::ArcIt ArcIt;
1604 bool bipartite = true;
1606 BipartitePartitionsVisitor<Graph, NodeMap>
1607 visitor(graph, partMap, bipartite);
1608 BfsVisit<Graph, BipartitePartitionsVisitor<Graph, NodeMap> >
1609 bfs(graph, visitor);
1611 for(NodeIt it(graph); it != INVALID; ++it) {
1612 if(!bfs.reached(it)){
1614 while (!bfs.emptyQueue()) {
1615 bfs.processNextNode();
1616 if (!bipartite) return false;
1623 /// \ingroup graph_properties
1625 /// \brief Check whether the given graph contains no loop arcs/edges.
1627 /// This function returns \c true if there are no loop arcs/edges in
1628 /// the given graph. It works for both directed and undirected graphs.
1629 template <typename Graph>
1630 bool loopFree(const Graph& graph) {
1631 for (typename Graph::ArcIt it(graph); it != INVALID; ++it) {
1632 if (graph.source(it) == graph.target(it)) return false;
1637 /// \ingroup graph_properties
1639 /// \brief Check whether the given graph contains no parallel arcs/edges.
1641 /// This function returns \c true if there are no parallel arcs/edges in
1642 /// the given graph. It works for both directed and undirected graphs.
1643 template <typename Graph>
1644 bool parallelFree(const Graph& graph) {
1645 typename Graph::template NodeMap<int> reached(graph, 0);
1647 for (typename Graph::NodeIt n(graph); n != INVALID; ++n) {
1648 for (typename Graph::OutArcIt a(graph, n); a != INVALID; ++a) {
1649 if (reached[graph.target(a)] == cnt) return false;
1650 reached[graph.target(a)] = cnt;
1657 /// \ingroup graph_properties
1659 /// \brief Check whether the given graph is simple.
1661 /// This function returns \c true if the given graph is simple, i.e.
1662 /// it contains no loop arcs/edges and no parallel arcs/edges.
1663 /// The function works for both directed and undirected graphs.
1664 /// \see loopFree(), parallelFree()
1665 template <typename Graph>
1666 bool simpleGraph(const Graph& graph) {
1667 typename Graph::template NodeMap<int> reached(graph, 0);
1669 for (typename Graph::NodeIt n(graph); n != INVALID; ++n) {
1671 for (typename Graph::OutArcIt a(graph, n); a != INVALID; ++a) {
1672 if (reached[graph.target(a)] == cnt) return false;
1673 reached[graph.target(a)] = cnt;
1682 #endif //LEMON_CONNECTIVITY_H