... and fix another one.
3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2006
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_TOPOLOGY_H
20 #define LEMON_TOPOLOGY_H
22 #include <lemon/dfs.h>
23 #include <lemon/bfs.h>
24 #include <lemon/graph_utils.h>
25 #include <lemon/graph_adaptor.h>
26 #include <lemon/maps.h>
28 #include <lemon/concept/graph.h>
29 #include <lemon/concept/ugraph.h>
30 #include <lemon/concept_check.h>
32 #include <lemon/bin_heap.h>
33 #include <lemon/bucket_heap.h>
40 /// \brief Topology related algorithms
42 /// Topology related algorithms
48 /// \brief Check that the given undirected graph is connected.
50 /// Check that the given undirected graph connected.
51 /// \param graph The undirected graph.
52 /// \return %True when there is path between any two nodes in the graph.
53 /// \note By definition, the empty graph is connected.
54 template <typename UGraph>
55 bool connected(const UGraph& graph) {
56 checkConcept<concept::UGraph, UGraph>();
57 typedef typename UGraph::NodeIt NodeIt;
58 if (NodeIt(graph) == INVALID) return true;
59 Dfs<UGraph> dfs(graph);
60 dfs.run(NodeIt(graph));
61 for (NodeIt it(graph); it != INVALID; ++it) {
62 if (!dfs.reached(it)) {
71 /// \brief Count the number of connected components of an undirected graph
73 /// Count the number of connected components of an undirected graph
75 /// \param graph The graph. It should be undirected.
76 /// \return The number of components
77 /// \note By definition, the empty graph consists
78 /// of zero connected components.
79 template <typename UGraph>
80 int countConnectedComponents(const UGraph &graph) {
81 checkConcept<concept::UGraph, UGraph>();
82 typedef typename UGraph::Node Node;
83 typedef typename UGraph::Edge Edge;
85 typedef NullMap<Node, Edge> PredMap;
86 typedef NullMap<Node, int> DistMap;
89 typename Bfs<UGraph>::
90 template DefPredMap<PredMap>::
91 template DefDistMap<DistMap>::
101 for(typename UGraph::NodeIt n(graph); n != INVALID; ++n) {
102 if (!bfs.reached(n)) {
111 /// \ingroup topology
113 /// \brief Find the connected components of an undirected graph
115 /// Find the connected components of an undirected graph.
117 /// \image html connected_components.png
118 /// \image latex connected_components.eps "Connected components" width=\textwidth
120 /// \param graph The graph. It should be undirected.
121 /// \retval compMap A writable node map. The values will be set from 0 to
122 /// the number of the connected components minus one. Each values of the map
123 /// will be set exactly once, the values of a certain component will be
124 /// set continuously.
125 /// \return The number of components
127 template <class UGraph, class NodeMap>
128 int connectedComponents(const UGraph &graph, NodeMap &compMap) {
129 checkConcept<concept::UGraph, UGraph>();
130 typedef typename UGraph::Node Node;
131 typedef typename UGraph::Edge Edge;
132 checkConcept<concept::WriteMap<Node, int>, NodeMap>();
134 typedef NullMap<Node, Edge> PredMap;
135 typedef NullMap<Node, int> DistMap;
138 typename Bfs<UGraph>::
139 template DefPredMap<PredMap>::
140 template DefDistMap<DistMap>::
144 bfs.predMap(predMap);
147 bfs.distMap(distMap);
150 for(typename UGraph::NodeIt n(graph); n != INVALID; ++n) {
151 if(!bfs.reached(n)) {
153 while (!bfs.emptyQueue()) {
154 compMap.set(bfs.nextNode(), compNum);
155 bfs.processNextNode();
163 namespace _topology_bits {
165 template <typename Graph, typename Iterator >
166 struct LeaveOrderVisitor : public DfsVisitor<Graph> {
168 typedef typename Graph::Node Node;
169 LeaveOrderVisitor(Iterator it) : _it(it) {}
171 void leave(const Node& node) {
179 template <typename Graph, typename Map>
180 struct FillMapVisitor : public DfsVisitor<Graph> {
182 typedef typename Graph::Node Node;
183 typedef typename Map::Value Value;
185 FillMapVisitor(Map& map, Value& value)
186 : _map(map), _value(value) {}
188 void reach(const Node& node) {
189 _map.set(node, _value);
196 template <typename Graph, typename EdgeMap>
197 struct StronglyConnectedCutEdgesVisitor : public DfsVisitor<Graph> {
199 typedef typename Graph::Node Node;
200 typedef typename Graph::Edge Edge;
202 StronglyConnectedCutEdgesVisitor(const Graph& graph, EdgeMap& cutMap,
204 : _graph(graph), _cutMap(cutMap), _cutNum(cutNum),
205 _compMap(graph), _num(0) {
208 void stop(const Node&) {
212 void reach(const Node& node) {
213 _compMap.set(node, _num);
216 void examine(const Edge& edge) {
217 if (_compMap[_graph.source(edge)] != _compMap[_graph.target(edge)]) {
218 _cutMap.set(edge, true);
227 typename Graph::template NodeMap<int> _compMap;
234 /// \ingroup topology
236 /// \brief Check that the given directed graph is strongly connected.
238 /// Check that the given directed graph is strongly connected. The
239 /// graph is strongly connected when any two nodes of the graph are
240 /// connected with directed paths in both direction.
241 /// \return %False when the graph is not strongly connected.
244 /// \note By definition, the empty graph is strongly connected.
245 template <typename Graph>
246 bool stronglyConnected(const Graph& graph) {
247 checkConcept<concept::Graph, Graph>();
249 typedef typename Graph::Node Node;
250 typedef typename Graph::NodeIt NodeIt;
252 if (NodeIt(graph) == INVALID) return true;
254 using namespace _topology_bits;
256 typedef DfsVisitor<Graph> Visitor;
259 DfsVisit<Graph, Visitor> dfs(graph, visitor);
261 dfs.addSource(NodeIt(graph));
264 for (NodeIt it(graph); it != INVALID; ++it) {
265 if (!dfs.reached(it)) {
270 typedef RevGraphAdaptor<const Graph> RGraph;
271 RGraph rgraph(graph);
273 typedef DfsVisitor<Graph> RVisitor;
276 DfsVisit<RGraph, RVisitor> rdfs(rgraph, rvisitor);
278 rdfs.addSource(NodeIt(graph));
281 for (NodeIt it(graph); it != INVALID; ++it) {
282 if (!rdfs.reached(it)) {
290 /// \ingroup topology
292 /// \brief Count the strongly connected components of a directed graph
294 /// Count the strongly connected components of a directed graph.
295 /// The strongly connected components are the classes of an equivalence
296 /// relation on the nodes of the graph. Two nodes are connected with
297 /// directed paths in both direction.
299 /// \param graph The graph.
300 /// \return The number of components
301 /// \note By definition, the empty graph has zero
302 /// strongly connected components.
303 template <typename Graph>
304 int countStronglyConnectedComponents(const Graph& graph) {
305 checkConcept<concept::Graph, Graph>();
307 using namespace _topology_bits;
309 typedef typename Graph::Node Node;
310 typedef typename Graph::Edge Edge;
311 typedef typename Graph::NodeIt NodeIt;
312 typedef typename Graph::EdgeIt EdgeIt;
314 typedef std::vector<Node> Container;
315 typedef typename Container::iterator Iterator;
317 Container nodes(countNodes(graph));
318 typedef LeaveOrderVisitor<Graph, Iterator> Visitor;
319 Visitor visitor(nodes.begin());
321 DfsVisit<Graph, Visitor> dfs(graph, visitor);
323 for (NodeIt it(graph); it != INVALID; ++it) {
324 if (!dfs.reached(it)) {
330 typedef typename Container::reverse_iterator RIterator;
331 typedef RevGraphAdaptor<const Graph> RGraph;
333 RGraph rgraph(graph);
335 typedef DfsVisitor<Graph> RVisitor;
338 DfsVisit<RGraph, RVisitor> rdfs(rgraph, rvisitor);
343 for (RIterator it = nodes.rbegin(); it != nodes.rend(); ++it) {
344 if (!rdfs.reached(*it)) {
353 /// \ingroup topology
355 /// \brief Find the strongly connected components of a directed graph
357 /// Find the strongly connected components of a directed graph.
358 /// The strongly connected components are the classes of an equivalence
359 /// relation on the nodes of the graph. Two nodes are in relationship
360 /// when there are directed paths between them in both direction.
362 /// \image html strongly_connected_components.png
363 /// \image latex strongly_connected_components.eps "Strongly connected components" width=\textwidth
365 /// \param graph The graph.
366 /// \retval compMap A writable node map. The values will be set from 0 to
367 /// the number of the strongly connected components minus one. Each values
368 /// of the map will be set exactly once, the values of a certain component
369 /// will be set continuously.
370 /// \return The number of components
372 template <typename Graph, typename NodeMap>
373 int stronglyConnectedComponents(const Graph& graph, NodeMap& compMap) {
374 checkConcept<concept::Graph, Graph>();
375 typedef typename Graph::Node Node;
376 typedef typename Graph::NodeIt NodeIt;
377 checkConcept<concept::WriteMap<Node, int>, NodeMap>();
379 using namespace _topology_bits;
381 typedef std::vector<Node> Container;
382 typedef typename Container::iterator Iterator;
384 Container nodes(countNodes(graph));
385 typedef LeaveOrderVisitor<Graph, Iterator> Visitor;
386 Visitor visitor(nodes.begin());
388 DfsVisit<Graph, Visitor> dfs(graph, visitor);
390 for (NodeIt it(graph); it != INVALID; ++it) {
391 if (!dfs.reached(it)) {
397 typedef typename Container::reverse_iterator RIterator;
398 typedef RevGraphAdaptor<const Graph> RGraph;
400 RGraph rgraph(graph);
404 typedef FillMapVisitor<RGraph, NodeMap> RVisitor;
405 RVisitor rvisitor(compMap, compNum);
407 DfsVisit<RGraph, RVisitor> rdfs(rgraph, rvisitor);
410 for (RIterator it = nodes.rbegin(); it != nodes.rend(); ++it) {
411 if (!rdfs.reached(*it)) {
420 /// \ingroup topology
422 /// \brief Find the cut edges of the strongly connected components.
424 /// Find the cut edges of the strongly connected components.
425 /// The strongly connected components are the classes of an equivalence
426 /// relation on the nodes of the graph. Two nodes are in relationship
427 /// when there are directed paths between them in both direction.
428 /// The strongly connected components are separated by the cut edges.
430 /// \param graph The graph.
431 /// \retval cutMap A writable node map. The values will be set true when the
432 /// edge is a cut edge.
434 /// \return The number of cut edges
435 template <typename Graph, typename EdgeMap>
436 int stronglyConnectedCutEdges(const Graph& graph, EdgeMap& cutMap) {
437 checkConcept<concept::Graph, Graph>();
438 typedef typename Graph::Node Node;
439 typedef typename Graph::Edge Edge;
440 typedef typename Graph::NodeIt NodeIt;
441 checkConcept<concept::WriteMap<Edge, bool>, EdgeMap>();
443 using namespace _topology_bits;
445 typedef std::vector<Node> Container;
446 typedef typename Container::iterator Iterator;
448 Container nodes(countNodes(graph));
449 typedef LeaveOrderVisitor<Graph, Iterator> Visitor;
450 Visitor visitor(nodes.begin());
452 DfsVisit<Graph, Visitor> dfs(graph, visitor);
454 for (NodeIt it(graph); it != INVALID; ++it) {
455 if (!dfs.reached(it)) {
461 typedef typename Container::reverse_iterator RIterator;
462 typedef RevGraphAdaptor<const Graph> RGraph;
464 RGraph rgraph(graph);
468 typedef StronglyConnectedCutEdgesVisitor<RGraph, EdgeMap> RVisitor;
469 RVisitor rvisitor(rgraph, cutMap, cutNum);
471 DfsVisit<RGraph, RVisitor> rdfs(rgraph, rvisitor);
474 for (RIterator it = nodes.rbegin(); it != nodes.rend(); ++it) {
475 if (!rdfs.reached(*it)) {
483 namespace _topology_bits {
485 template <typename Graph>
486 class CountBiNodeConnectedComponentsVisitor : public DfsVisitor<Graph> {
488 typedef typename Graph::Node Node;
489 typedef typename Graph::Edge Edge;
490 typedef typename Graph::UEdge UEdge;
492 CountBiNodeConnectedComponentsVisitor(const Graph& graph, int &compNum)
493 : _graph(graph), _compNum(compNum),
494 _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
496 void start(const Node& node) {
497 _predMap.set(node, INVALID);
500 void reach(const Node& node) {
501 _numMap.set(node, _num);
502 _retMap.set(node, _num);
506 void discover(const Edge& edge) {
507 _predMap.set(_graph.target(edge), _graph.source(edge));
510 void examine(const Edge& edge) {
511 if (_graph.source(edge) == _graph.target(edge) &&
512 _graph.direction(edge)) {
516 if (_predMap[_graph.source(edge)] == _graph.target(edge)) {
519 if (_retMap[_graph.source(edge)] > _numMap[_graph.target(edge)]) {
520 _retMap.set(_graph.source(edge), _numMap[_graph.target(edge)]);
524 void backtrack(const Edge& edge) {
525 if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
526 _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
528 if (_numMap[_graph.source(edge)] <= _retMap[_graph.target(edge)]) {
537 typename Graph::template NodeMap<int> _numMap;
538 typename Graph::template NodeMap<int> _retMap;
539 typename Graph::template NodeMap<Node> _predMap;
543 template <typename Graph, typename EdgeMap>
544 class BiNodeConnectedComponentsVisitor : public DfsVisitor<Graph> {
546 typedef typename Graph::Node Node;
547 typedef typename Graph::Edge Edge;
548 typedef typename Graph::UEdge UEdge;
550 BiNodeConnectedComponentsVisitor(const Graph& graph,
551 EdgeMap& compMap, int &compNum)
552 : _graph(graph), _compMap(compMap), _compNum(compNum),
553 _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
555 void start(const Node& node) {
556 _predMap.set(node, INVALID);
559 void reach(const Node& node) {
560 _numMap.set(node, _num);
561 _retMap.set(node, _num);
565 void discover(const Edge& edge) {
566 Node target = _graph.target(edge);
567 _predMap.set(target, edge);
568 _edgeStack.push(edge);
571 void examine(const Edge& edge) {
572 Node source = _graph.source(edge);
573 Node target = _graph.target(edge);
574 if (source == target && _graph.direction(edge)) {
575 _compMap.set(edge, _compNum);
579 if (_numMap[target] < _numMap[source]) {
580 if (_predMap[source] != _graph.oppositeEdge(edge)) {
581 _edgeStack.push(edge);
584 if (_predMap[source] != INVALID &&
585 target == _graph.source(_predMap[source])) {
588 if (_retMap[source] > _numMap[target]) {
589 _retMap.set(source, _numMap[target]);
593 void backtrack(const Edge& edge) {
594 Node source = _graph.source(edge);
595 Node target = _graph.target(edge);
596 if (_retMap[source] > _retMap[target]) {
597 _retMap.set(source, _retMap[target]);
599 if (_numMap[source] <= _retMap[target]) {
600 while (_edgeStack.top() != edge) {
601 _compMap.set(_edgeStack.top(), _compNum);
604 _compMap.set(edge, _compNum);
615 typename Graph::template NodeMap<int> _numMap;
616 typename Graph::template NodeMap<int> _retMap;
617 typename Graph::template NodeMap<Edge> _predMap;
618 std::stack<UEdge> _edgeStack;
623 template <typename Graph, typename NodeMap>
624 class BiNodeConnectedCutNodesVisitor : public DfsVisitor<Graph> {
626 typedef typename Graph::Node Node;
627 typedef typename Graph::Edge Edge;
628 typedef typename Graph::UEdge UEdge;
630 BiNodeConnectedCutNodesVisitor(const Graph& graph, NodeMap& cutMap,
632 : _graph(graph), _cutMap(cutMap), _cutNum(cutNum),
633 _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
635 void start(const Node& node) {
636 _predMap.set(node, INVALID);
640 void reach(const Node& node) {
641 _numMap.set(node, _num);
642 _retMap.set(node, _num);
646 void discover(const Edge& edge) {
647 _predMap.set(_graph.target(edge), _graph.source(edge));
650 void examine(const Edge& edge) {
651 if (_graph.source(edge) == _graph.target(edge) &&
652 _graph.direction(edge)) {
653 if (!_cutMap[_graph.source(edge)]) {
654 _cutMap.set(_graph.source(edge), true);
659 if (_predMap[_graph.source(edge)] == _graph.target(edge)) return;
660 if (_retMap[_graph.source(edge)] > _numMap[_graph.target(edge)]) {
661 _retMap.set(_graph.source(edge), _numMap[_graph.target(edge)]);
665 void backtrack(const Edge& edge) {
666 if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
667 _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
669 if (_numMap[_graph.source(edge)] <= _retMap[_graph.target(edge)]) {
670 if (_predMap[_graph.source(edge)] != INVALID) {
671 if (!_cutMap[_graph.source(edge)]) {
672 _cutMap.set(_graph.source(edge), true);
675 } else if (rootCut) {
676 if (!_cutMap[_graph.source(edge)]) {
677 _cutMap.set(_graph.source(edge), true);
691 typename Graph::template NodeMap<int> _numMap;
692 typename Graph::template NodeMap<int> _retMap;
693 typename Graph::template NodeMap<Node> _predMap;
694 std::stack<UEdge> _edgeStack;
701 template <typename UGraph>
702 int countBiNodeConnectedComponents(const UGraph& graph);
704 /// \ingroup topology
706 /// \brief Checks the graph is bi-node-connected.
708 /// This function checks that the undirected graph is bi-node-connected
709 /// graph. The graph is bi-node-connected if any two undirected edge is
712 /// \param graph The graph.
713 /// \return %True when the graph bi-node-connected.
714 /// \todo Make it faster.
715 template <typename UGraph>
716 bool biNodeConnected(const UGraph& graph) {
717 return countBiNodeConnectedComponents(graph) == 1;
720 /// \ingroup topology
722 /// \brief Count the biconnected components.
724 /// This function finds the bi-node-connected components in an undirected
725 /// graph. The biconnected components are the classes of an equivalence
726 /// relation on the undirected edges. Two undirected edge is in relationship
727 /// when they are on same circle.
729 /// \param graph The graph.
730 /// \return The number of components.
731 template <typename UGraph>
732 int countBiNodeConnectedComponents(const UGraph& graph) {
733 checkConcept<concept::UGraph, UGraph>();
734 typedef typename UGraph::NodeIt NodeIt;
736 using namespace _topology_bits;
738 typedef CountBiNodeConnectedComponentsVisitor<UGraph> Visitor;
741 Visitor visitor(graph, compNum);
743 DfsVisit<UGraph, Visitor> dfs(graph, visitor);
746 for (NodeIt it(graph); it != INVALID; ++it) {
747 if (!dfs.reached(it)) {
755 /// \ingroup topology
757 /// \brief Find the bi-node-connected components.
759 /// This function finds the bi-node-connected components in an undirected
760 /// graph. The bi-node-connected components are the classes of an equivalence
761 /// relation on the undirected edges. Two undirected edge are in relationship
762 /// when they are on same circle.
764 /// \image html node_biconnected_components.png
765 /// \image latex node_biconnected_components.eps "bi-node-connected components" width=\textwidth
767 /// \param graph The graph.
768 /// \retval compMap A writable uedge map. The values will be set from 0
769 /// to the number of the biconnected components minus one. Each values
770 /// of the map will be set exactly once, the values of a certain component
771 /// will be set continuously.
772 /// \return The number of components.
774 template <typename UGraph, typename UEdgeMap>
775 int biNodeConnectedComponents(const UGraph& graph,
777 checkConcept<concept::UGraph, UGraph>();
778 typedef typename UGraph::NodeIt NodeIt;
779 typedef typename UGraph::UEdge UEdge;
780 checkConcept<concept::WriteMap<UEdge, int>, UEdgeMap>();
782 using namespace _topology_bits;
784 typedef BiNodeConnectedComponentsVisitor<UGraph, UEdgeMap> Visitor;
787 Visitor visitor(graph, compMap, compNum);
789 DfsVisit<UGraph, Visitor> dfs(graph, visitor);
792 for (NodeIt it(graph); it != INVALID; ++it) {
793 if (!dfs.reached(it)) {
801 /// \ingroup topology
803 /// \brief Find the bi-node-connected cut nodes.
805 /// This function finds the bi-node-connected cut nodes in an undirected
806 /// graph. The bi-node-connected components are the classes of an equivalence
807 /// relation on the undirected edges. Two undirected edges are in
808 /// relationship when they are on same circle. The biconnected components
809 /// are separted by nodes which are the cut nodes of the components.
811 /// \param graph The graph.
812 /// \retval cutMap A writable edge map. The values will be set true when
813 /// the node separate two or more components.
814 /// \return The number of the cut nodes.
815 template <typename UGraph, typename NodeMap>
816 int biNodeConnectedCutNodes(const UGraph& graph, NodeMap& cutMap) {
817 checkConcept<concept::UGraph, UGraph>();
818 typedef typename UGraph::Node Node;
819 typedef typename UGraph::NodeIt NodeIt;
820 checkConcept<concept::WriteMap<Node, bool>, NodeMap>();
822 using namespace _topology_bits;
824 typedef BiNodeConnectedCutNodesVisitor<UGraph, NodeMap> Visitor;
827 Visitor visitor(graph, cutMap, cutNum);
829 DfsVisit<UGraph, Visitor> dfs(graph, visitor);
832 for (NodeIt it(graph); it != INVALID; ++it) {
833 if (!dfs.reached(it)) {
841 namespace _topology_bits {
843 template <typename Graph>
844 class CountBiEdgeConnectedComponentsVisitor : public DfsVisitor<Graph> {
846 typedef typename Graph::Node Node;
847 typedef typename Graph::Edge Edge;
848 typedef typename Graph::UEdge UEdge;
850 CountBiEdgeConnectedComponentsVisitor(const Graph& graph, int &compNum)
851 : _graph(graph), _compNum(compNum),
852 _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
854 void start(const Node& node) {
855 _predMap.set(node, INVALID);
858 void reach(const Node& node) {
859 _numMap.set(node, _num);
860 _retMap.set(node, _num);
864 void leave(const Node& node) {
865 if (_numMap[node] <= _retMap[node]) {
870 void discover(const Edge& edge) {
871 _predMap.set(_graph.target(edge), edge);
874 void examine(const Edge& edge) {
875 if (_predMap[_graph.source(edge)] == _graph.oppositeEdge(edge)) {
878 if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
879 _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
883 void backtrack(const Edge& edge) {
884 if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
885 _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
893 typename Graph::template NodeMap<int> _numMap;
894 typename Graph::template NodeMap<int> _retMap;
895 typename Graph::template NodeMap<Edge> _predMap;
899 template <typename Graph, typename NodeMap>
900 class BiEdgeConnectedComponentsVisitor : public DfsVisitor<Graph> {
902 typedef typename Graph::Node Node;
903 typedef typename Graph::Edge Edge;
904 typedef typename Graph::UEdge UEdge;
906 BiEdgeConnectedComponentsVisitor(const Graph& graph,
907 NodeMap& compMap, int &compNum)
908 : _graph(graph), _compMap(compMap), _compNum(compNum),
909 _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
911 void start(const Node& node) {
912 _predMap.set(node, INVALID);
915 void reach(const Node& node) {
916 _numMap.set(node, _num);
917 _retMap.set(node, _num);
918 _nodeStack.push(node);
922 void leave(const Node& node) {
923 if (_numMap[node] <= _retMap[node]) {
924 while (_nodeStack.top() != node) {
925 _compMap.set(_nodeStack.top(), _compNum);
928 _compMap.set(node, _compNum);
934 void discover(const Edge& edge) {
935 _predMap.set(_graph.target(edge), edge);
938 void examine(const Edge& edge) {
939 if (_predMap[_graph.source(edge)] == _graph.oppositeEdge(edge)) {
942 if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
943 _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
947 void backtrack(const Edge& edge) {
948 if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
949 _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
958 typename Graph::template NodeMap<int> _numMap;
959 typename Graph::template NodeMap<int> _retMap;
960 typename Graph::template NodeMap<Edge> _predMap;
961 std::stack<Node> _nodeStack;
966 template <typename Graph, typename EdgeMap>
967 class BiEdgeConnectedCutEdgesVisitor : public DfsVisitor<Graph> {
969 typedef typename Graph::Node Node;
970 typedef typename Graph::Edge Edge;
971 typedef typename Graph::UEdge UEdge;
973 BiEdgeConnectedCutEdgesVisitor(const Graph& graph,
974 EdgeMap& cutMap, int &cutNum)
975 : _graph(graph), _cutMap(cutMap), _cutNum(cutNum),
976 _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
978 void start(const Node& node) {
979 _predMap[node] = INVALID;
982 void reach(const Node& node) {
983 _numMap.set(node, _num);
984 _retMap.set(node, _num);
988 void leave(const Node& node) {
989 if (_numMap[node] <= _retMap[node]) {
990 if (_predMap[node] != INVALID) {
991 _cutMap.set(_predMap[node], true);
997 void discover(const Edge& edge) {
998 _predMap.set(_graph.target(edge), edge);
1001 void examine(const Edge& edge) {
1002 if (_predMap[_graph.source(edge)] == _graph.oppositeEdge(edge)) {
1005 if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
1006 _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
1010 void backtrack(const Edge& edge) {
1011 if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
1012 _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
1017 const Graph& _graph;
1021 typename Graph::template NodeMap<int> _numMap;
1022 typename Graph::template NodeMap<int> _retMap;
1023 typename Graph::template NodeMap<Edge> _predMap;
1028 template <typename UGraph>
1029 int countbiEdgeConnectedComponents(const UGraph& graph);
1031 /// \ingroup topology
1033 /// \brief Checks that the graph is bi-edge-connected.
1035 /// This function checks that the graph is bi-edge-connected. The undirected
1036 /// graph is bi-edge-connected when any two nodes are connected with two
1037 /// edge-disjoint paths.
1039 /// \param graph The undirected graph.
1040 /// \return The number of components.
1041 /// \todo Make it faster.
1042 template <typename UGraph>
1043 bool biEdgeConnected(const UGraph& graph) {
1044 return countBiEdgeConnectedComponents(graph) == 1;
1047 /// \ingroup topology
1049 /// \brief Count the bi-edge-connected components.
1051 /// This function count the bi-edge-connected components in an undirected
1052 /// graph. The bi-edge-connected components are the classes of an equivalence
1053 /// relation on the nodes. Two nodes are in relationship when they are
1054 /// connected with at least two edge-disjoint paths.
1056 /// \param graph The undirected graph.
1057 /// \return The number of components.
1058 template <typename UGraph>
1059 int countBiEdgeConnectedComponents(const UGraph& graph) {
1060 checkConcept<concept::UGraph, UGraph>();
1061 typedef typename UGraph::NodeIt NodeIt;
1063 using namespace _topology_bits;
1065 typedef CountBiEdgeConnectedComponentsVisitor<UGraph> Visitor;
1068 Visitor visitor(graph, compNum);
1070 DfsVisit<UGraph, Visitor> dfs(graph, visitor);
1073 for (NodeIt it(graph); it != INVALID; ++it) {
1074 if (!dfs.reached(it)) {
1082 /// \ingroup topology
1084 /// \brief Find the bi-edge-connected components.
1086 /// This function finds the bi-edge-connected components in an undirected
1087 /// graph. The bi-edge-connected components are the classes of an equivalence
1088 /// relation on the nodes. Two nodes are in relationship when they are
1089 /// connected at least two edge-disjoint paths.
1091 /// \image html edge_biconnected_components.png
1092 /// \image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth
1094 /// \param graph The graph.
1095 /// \retval compMap A writable node map. The values will be set from 0 to
1096 /// the number of the biconnected components minus one. Each values
1097 /// of the map will be set exactly once, the values of a certain component
1098 /// will be set continuously.
1099 /// \return The number of components.
1101 template <typename UGraph, typename NodeMap>
1102 int biEdgeConnectedComponents(const UGraph& graph, NodeMap& compMap) {
1103 checkConcept<concept::UGraph, UGraph>();
1104 typedef typename UGraph::NodeIt NodeIt;
1105 typedef typename UGraph::Node Node;
1106 checkConcept<concept::WriteMap<Node, int>, NodeMap>();
1108 using namespace _topology_bits;
1110 typedef BiEdgeConnectedComponentsVisitor<UGraph, NodeMap> Visitor;
1113 Visitor visitor(graph, compMap, compNum);
1115 DfsVisit<UGraph, Visitor> dfs(graph, visitor);
1118 for (NodeIt it(graph); it != INVALID; ++it) {
1119 if (!dfs.reached(it)) {
1127 /// \ingroup topology
1129 /// \brief Find the bi-edge-connected cut edges.
1131 /// This function finds the bi-edge-connected components in an undirected
1132 /// graph. The bi-edge-connected components are the classes of an equivalence
1133 /// relation on the nodes. Two nodes are in relationship when they are
1134 /// connected with at least two edge-disjoint paths. The bi-edge-connected
1135 /// components are separted by edges which are the cut edges of the
1138 /// \param graph The graph.
1139 /// \retval cutMap A writable node map. The values will be set true when the
1140 /// edge is a cut edge.
1141 /// \return The number of cut edges.
1142 template <typename UGraph, typename UEdgeMap>
1143 int biEdgeConnectedCutEdges(const UGraph& graph, UEdgeMap& cutMap) {
1144 checkConcept<concept::UGraph, UGraph>();
1145 typedef typename UGraph::NodeIt NodeIt;
1146 typedef typename UGraph::UEdge UEdge;
1147 checkConcept<concept::WriteMap<UEdge, bool>, UEdgeMap>();
1149 using namespace _topology_bits;
1151 typedef BiEdgeConnectedCutEdgesVisitor<UGraph, UEdgeMap> Visitor;
1154 Visitor visitor(graph, cutMap, cutNum);
1156 DfsVisit<UGraph, Visitor> dfs(graph, visitor);
1159 for (NodeIt it(graph); it != INVALID; ++it) {
1160 if (!dfs.reached(it)) {
1169 namespace _topology_bits {
1171 template <typename Graph, typename IntNodeMap>
1172 class TopologicalSortVisitor : public DfsVisitor<Graph> {
1174 typedef typename Graph::Node Node;
1175 typedef typename Graph::Edge edge;
1177 TopologicalSortVisitor(IntNodeMap& order, int num)
1178 : _order(order), _num(num) {}
1180 void leave(const Node& node) {
1181 _order.set(node, --_num);
1191 /// \ingroup topology
1193 /// \brief Sort the nodes of a DAG into topolgical order.
1195 /// Sort the nodes of a DAG into topolgical order.
1197 /// \param graph The graph. It should be directed and acyclic.
1198 /// \retval order A writable node map. The values will be set from 0 to
1199 /// the number of the nodes in the graph minus one. Each values of the map
1200 /// will be set exactly once, the values will be set descending order.
1202 /// \see checkedTopologicalSort
1204 template <typename Graph, typename NodeMap>
1205 void topologicalSort(const Graph& graph, NodeMap& order) {
1206 using namespace _topology_bits;
1208 checkConcept<concept::Graph, Graph>();
1209 checkConcept<concept::WriteMap<typename Graph::Node, int>, NodeMap>();
1211 typedef typename Graph::Node Node;
1212 typedef typename Graph::NodeIt NodeIt;
1213 typedef typename Graph::Edge Edge;
1215 TopologicalSortVisitor<Graph, NodeMap>
1216 visitor(order, countNodes(graph));
1218 DfsVisit<Graph, TopologicalSortVisitor<Graph, NodeMap> >
1219 dfs(graph, visitor);
1222 for (NodeIt it(graph); it != INVALID; ++it) {
1223 if (!dfs.reached(it)) {
1230 /// \ingroup topology
1232 /// \brief Sort the nodes of a DAG into topolgical order.
1234 /// Sort the nodes of a DAG into topolgical order. It also checks
1235 /// that the given graph is DAG.
1237 /// \param graph The graph. It should be directed and acyclic.
1238 /// \retval order A readable - writable node map. The values will be set
1239 /// from 0 to the number of the nodes in the graph minus one. Each values
1240 /// of the map will be set exactly once, the values will be set descending
1242 /// \return %False when the graph is not DAG.
1244 /// \see topologicalSort
1246 template <typename Graph, typename NodeMap>
1247 bool checkedTopologicalSort(const Graph& graph, NodeMap& order) {
1248 using namespace _topology_bits;
1250 checkConcept<concept::Graph, Graph>();
1251 checkConcept<concept::ReadWriteMap<typename Graph::Node, int>, NodeMap>();
1253 typedef typename Graph::Node Node;
1254 typedef typename Graph::NodeIt NodeIt;
1255 typedef typename Graph::Edge Edge;
1257 order = constMap<Node, int, -1>();
1259 TopologicalSortVisitor<Graph, NodeMap>
1260 visitor(order, countNodes(graph));
1262 DfsVisit<Graph, TopologicalSortVisitor<Graph, NodeMap> >
1263 dfs(graph, visitor);
1266 for (NodeIt it(graph); it != INVALID; ++it) {
1267 if (!dfs.reached(it)) {
1269 while (!dfs.emptyQueue()) {
1270 Edge edge = dfs.nextEdge();
1271 Node target = graph.target(edge);
1272 if (dfs.reached(target) && order[target] == -1) {
1275 dfs.processNextEdge();
1282 /// \ingroup topology
1284 /// \brief Check that the given directed graph is a DAG.
1286 /// Check that the given directed graph is a DAG. The DAG is
1287 /// an Directed Acyclic Graph.
1288 /// \return %False when the graph is not DAG.
1290 template <typename Graph>
1291 bool dag(const Graph& graph) {
1293 checkConcept<concept::Graph, Graph>();
1295 typedef typename Graph::Node Node;
1296 typedef typename Graph::NodeIt NodeIt;
1297 typedef typename Graph::Edge Edge;
1299 typedef typename Graph::template NodeMap<bool> ProcessedMap;
1301 typename Dfs<Graph>::template DefProcessedMap<ProcessedMap>::
1304 ProcessedMap processed(graph);
1305 dfs.processedMap(processed);
1308 for (NodeIt it(graph); it != INVALID; ++it) {
1309 if (!dfs.reached(it)) {
1311 while (!dfs.emptyQueue()) {
1312 Edge edge = dfs.nextEdge();
1313 Node target = graph.target(edge);
1314 if (dfs.reached(target) && !processed[target]) {
1317 dfs.processNextEdge();
1324 /// \ingroup topology
1326 /// \brief Check that the given undirected graph is acyclic.
1328 /// Check that the given undirected graph acyclic.
1329 /// \param graph The undirected graph.
1330 /// \return %True when there is no circle in the graph.
1332 template <typename UGraph>
1333 bool acyclic(const UGraph& graph) {
1334 checkConcept<concept::UGraph, UGraph>();
1335 typedef typename UGraph::Node Node;
1336 typedef typename UGraph::NodeIt NodeIt;
1337 typedef typename UGraph::Edge Edge;
1338 Dfs<UGraph> dfs(graph);
1340 for (NodeIt it(graph); it != INVALID; ++it) {
1341 if (!dfs.reached(it)) {
1343 while (!dfs.emptyQueue()) {
1344 Edge edge = dfs.nextEdge();
1345 Node source = graph.source(edge);
1346 Node target = graph.target(edge);
1347 if (dfs.reached(target) &&
1348 dfs.predEdge(source) != graph.oppositeEdge(edge)) {
1351 dfs.processNextEdge();
1358 /// \ingroup topology
1360 /// \brief Check that the given undirected graph is tree.
1362 /// Check that the given undirected graph is tree.
1363 /// \param graph The undirected graph.
1364 /// \return %True when the graph is acyclic and connected.
1365 template <typename UGraph>
1366 bool tree(const UGraph& graph) {
1367 checkConcept<concept::UGraph, UGraph>();
1368 typedef typename UGraph::Node Node;
1369 typedef typename UGraph::NodeIt NodeIt;
1370 typedef typename UGraph::Edge Edge;
1371 Dfs<UGraph> dfs(graph);
1373 dfs.addSource(NodeIt(graph));
1374 while (!dfs.emptyQueue()) {
1375 Edge edge = dfs.nextEdge();
1376 Node source = graph.source(edge);
1377 Node target = graph.target(edge);
1378 if (dfs.reached(target) &&
1379 dfs.predEdge(source) != graph.oppositeEdge(edge)) {
1382 dfs.processNextEdge();
1384 for (NodeIt it(graph); it != INVALID; ++it) {
1385 if (!dfs.reached(it)) {
1392 /// \ingroup topology
1394 /// \brief Check if the given undirected graph is bipartite or not
1396 /// The function checks if the given undirected \c graph graph is bipartite
1397 /// or not. The \ref Bfs algorithm is used to calculate the result.
1398 /// \param graph The undirected graph.
1399 /// \return %True if \c graph is bipartite, %false otherwise.
1400 /// \sa bipartitePartitions
1402 /// \author Balazs Attila Mihaly
1403 template<typename UGraph>
1404 inline bool bipartite(const UGraph &graph){
1405 checkConcept<concept::UGraph, UGraph>();
1407 typedef typename UGraph::NodeIt NodeIt;
1408 typedef typename UGraph::EdgeIt EdgeIt;
1410 Bfs<UGraph> bfs(graph);
1412 for(NodeIt i(graph);i!=INVALID;++i){
1413 if(!bfs.reached(i)){
1417 for(EdgeIt i(graph);i!=INVALID;++i){
1418 if(bfs.dist(graph.source(i))==bfs.dist(graph.target(i)))return false;
1423 /// \ingroup topology
1425 /// \brief Check if the given undirected graph is bipartite or not
1427 /// The function checks if the given undirected graph is bipartite
1428 /// or not. The \ref Bfs algorithm is used to calculate the result.
1429 /// During the execution, the \c partMap will be set as the two
1430 /// partitions of the graph.
1431 /// \param graph The undirected graph.
1432 /// \retval partMap A writable bool map of nodes. It will be set as the
1433 /// two partitions of the graph.
1434 /// \return %True if \c graph is bipartite, %false otherwise.
1436 /// \author Balazs Attila Mihaly
1438 /// \image html bipartite_partitions.png
1439 /// \image latex bipartite_partitions.eps "Bipartite partititions" width=\textwidth
1440 template<typename UGraph, typename NodeMap>
1441 inline bool bipartitePartitions(const UGraph &graph, NodeMap &partMap){
1442 checkConcept<concept::UGraph, UGraph>();
1444 typedef typename UGraph::Node Node;
1445 typedef typename UGraph::NodeIt NodeIt;
1446 typedef typename UGraph::EdgeIt EdgeIt;
1448 Bfs<UGraph> bfs(graph);
1450 for(NodeIt i(graph);i!=INVALID;++i){
1451 if(!bfs.reached(i)){
1453 for(Node j=bfs.processNextNode();!bfs.emptyQueue();
1454 j=bfs.processNextNode()){
1455 partMap.set(j,bfs.dist(j)%2==0);
1459 for(EdgeIt i(graph);i!=INVALID;++i){
1460 if(bfs.dist(graph.source(i)) == bfs.dist(graph.target(i)))return false;
1467 #endif //LEMON_TOPOLOGY_H