Reformatting: too long code lines.
2 * lemon/topology.h - Part of LEMON, a generic C++ optimization library
4 * Copyright (C) 2006 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5 * (Egervary Research Group on Combinatorial Optimization, EGRES).
7 * Permission to use, modify and distribute this software is granted
8 * provided that this copyright notice appears in all copies. For
9 * precise terms see the accompanying LICENSE file.
11 * This software is provided "AS IS" with no warranty of any kind,
12 * express or implied, and with no claim as to its suitability for any
17 #ifndef LEMON_TOPOLOGY_H
18 #define LEMON_TOPOLOGY_H
20 #include <lemon/dfs.h>
21 #include <lemon/bfs.h>
22 #include <lemon/graph_utils.h>
23 #include <lemon/graph_adaptor.h>
24 #include <lemon/maps.h>
26 #include <lemon/concept/graph.h>
27 #include <lemon/concept/undir_graph.h>
28 #include <lemon/concept_check.h>
30 #include <lemon/bin_heap.h>
31 #include <lemon/linear_heap.h>
38 /// \brief Topology related algorithms
40 /// Topology related algorithms
46 /// \brief Check that the given undirected graph is connected.
48 /// Check that the given undirected graph connected.
49 /// \param graph The undirected graph.
50 /// \return %True when there is path between any two nodes in the graph.
51 /// \note By definition, the empty graph is connected.
52 template <typename UndirGraph>
53 bool connected(const UndirGraph& graph) {
54 checkConcept<concept::UndirGraph, UndirGraph>();
55 typedef typename UndirGraph::NodeIt NodeIt;
56 if (NodeIt(graph) == INVALID) return true;
57 Dfs<UndirGraph> dfs(graph);
58 dfs.run(NodeIt(graph));
59 for (NodeIt it(graph); it != INVALID; ++it) {
60 if (!dfs.reached(it)) {
69 /// \brief Count the number of connected components of an undirected graph
71 /// Count the number of connected components of an undirected graph
73 /// \param graph The graph. It should be undirected.
74 /// \return The number of components
75 /// \note By definition, the empty graph consists
76 /// of zero connected components.
77 template <typename UndirGraph>
78 int countConnectedComponents(const UndirGraph &graph) {
79 checkConcept<concept::UndirGraph, UndirGraph>();
80 typedef typename UndirGraph::Node Node;
81 typedef typename UndirGraph::Edge Edge;
83 typedef NullMap<Node, Edge> PredMap;
84 typedef NullMap<Node, int> DistMap;
87 typename Bfs<UndirGraph>::
88 template DefPredMap<PredMap>::
89 template DefDistMap<DistMap>::
99 for(typename UndirGraph::NodeIt n(graph); n != INVALID; ++n) {
100 if (!bfs.reached(n)) {
109 /// \ingroup topology
111 /// \brief Find the connected components of an undirected graph
113 /// Find the connected components of an undirected graph.
115 /// \image html connected_components.png
116 /// \image latex connected_components.eps "Connected components" width=\textwidth
118 /// \param graph The graph. It should be undirected.
119 /// \retval compMap A writable node map. The values will be set from 0 to
120 /// the number of the connected components minus one. Each values of the map
121 /// will be set exactly once, the values of a certain component will be
122 /// set continuously.
123 /// \return The number of components
125 template <class UndirGraph, class NodeMap>
126 int connectedComponents(const UndirGraph &graph, NodeMap &compMap) {
127 checkConcept<concept::UndirGraph, UndirGraph>();
128 typedef typename UndirGraph::Node Node;
129 typedef typename UndirGraph::Edge Edge;
130 checkConcept<concept::WriteMap<Node, int>, NodeMap>();
132 typedef NullMap<Node, Edge> PredMap;
133 typedef NullMap<Node, int> DistMap;
136 typename Bfs<UndirGraph>::
137 template DefPredMap<PredMap>::
138 template DefDistMap<DistMap>::
142 bfs.predMap(predMap);
145 bfs.distMap(distMap);
148 for(typename UndirGraph::NodeIt n(graph); n != INVALID; ++n) {
149 if(!bfs.reached(n)) {
151 while (!bfs.emptyQueue()) {
152 compMap.set(bfs.nextNode(), compNum);
153 bfs.processNextNode();
161 namespace _topology_bits {
163 template <typename Graph, typename Iterator >
164 struct LeaveOrderVisitor : public DfsVisitor<Graph> {
166 typedef typename Graph::Node Node;
167 LeaveOrderVisitor(Iterator it) : _it(it) {}
169 void leave(const Node& node) {
177 template <typename Graph, typename Map>
178 struct FillMapVisitor : public DfsVisitor<Graph> {
180 typedef typename Graph::Node Node;
181 typedef typename Map::Value Value;
183 FillMapVisitor(Map& map, Value& value)
184 : _map(map), _value(value) {}
186 void reach(const Node& node) {
187 _map.set(node, _value);
194 template <typename Graph, typename EdgeMap>
195 struct StronglyConnectedCutEdgesVisitor : public DfsVisitor<Graph> {
197 typedef typename Graph::Node Node;
198 typedef typename Graph::Edge Edge;
200 StronglyConnectedCutEdgesVisitor(const Graph& graph, EdgeMap& cutMap,
202 : _graph(graph), _cutMap(cutMap), _cutNum(cutNum),
203 _compMap(graph), _num(0) {
206 void stop(const Node&) {
210 void reach(const Node& node) {
211 _compMap.set(node, _num);
214 void examine(const Edge& edge) {
215 if (_compMap[_graph.source(edge)] != _compMap[_graph.target(edge)]) {
216 _cutMap.set(edge, true);
225 typename Graph::template NodeMap<int> _compMap;
232 /// \ingroup topology
234 /// \brief Check that the given directed graph is strongly connected.
236 /// Check that the given directed graph is strongly connected. The
237 /// graph is strongly connected when any two nodes of the graph are
238 /// connected with directed paths in both direction.
239 /// \return %False when the graph is not strongly connected.
242 /// \note By definition, the empty graph is strongly connected.
243 template <typename Graph>
244 bool stronglyConnected(const Graph& graph) {
245 checkConcept<concept::StaticGraph, Graph>();
246 if (NodeIt(graph) == INVALID) return true;
248 typedef typename Graph::Node Node;
249 typedef typename Graph::NodeIt NodeIt;
251 using namespace _topology_bits;
253 typedef DfsVisitor<Graph> Visitor;
256 DfsVisit<Graph, Visitor> dfs(graph, visitor);
258 dfs.addSource(NodeIt(graph));
261 for (NodeIt it(graph); it != INVALID; ++it) {
262 if (!dfs.reached(it)) {
267 typedef RevGraphAdaptor<const Graph> RGraph;
268 RGraph rgraph(graph);
270 typedef DfsVisitor<Graph> RVisitor;
273 DfsVisit<RGraph, RVisitor> rdfs(rgraph, rvisitor);
275 rdfs.addSource(NodeIt(graph));
278 for (NodeIt it(graph); it != INVALID; ++it) {
279 if (!rdfs.reached(it)) {
287 /// \ingroup topology
289 /// \brief Count the strongly connected components of a directed graph
291 /// Count the strongly connected components of a directed graph.
292 /// The strongly connected components are the classes of an equivalence
293 /// relation on the nodes of the graph. Two nodes are connected with
294 /// directed paths in both direction.
296 /// \param graph The graph.
297 /// \return The number of components
298 /// \note By definition, the empty graph has zero
299 /// strongly connected components.
300 template <typename Graph>
301 int countStronglyConnectedComponents(const Graph& graph) {
302 checkConcept<concept::StaticGraph, Graph>();
304 using namespace _topology_bits;
306 typedef typename Graph::Node Node;
307 typedef typename Graph::Edge Edge;
308 typedef typename Graph::NodeIt NodeIt;
309 typedef typename Graph::EdgeIt EdgeIt;
311 typedef std::vector<Node> Container;
312 typedef typename Container::iterator Iterator;
314 Container nodes(countNodes(graph));
315 typedef LeaveOrderVisitor<Graph, Iterator> Visitor;
316 Visitor visitor(nodes.begin());
318 DfsVisit<Graph, Visitor> dfs(graph, visitor);
320 for (NodeIt it(graph); it != INVALID; ++it) {
321 if (!dfs.reached(it)) {
327 typedef typename Container::reverse_iterator RIterator;
328 typedef RevGraphAdaptor<const Graph> RGraph;
330 RGraph rgraph(graph);
332 typedef DfsVisitor<Graph> RVisitor;
335 DfsVisit<RGraph, RVisitor> rdfs(rgraph, rvisitor);
340 for (RIterator it = nodes.rbegin(); it != nodes.rend(); ++it) {
341 if (!rdfs.reached(*it)) {
350 /// \ingroup topology
352 /// \brief Find the strongly connected components of a directed graph
354 /// Find the strongly connected components of a directed graph.
355 /// The strongly connected components are the classes of an equivalence
356 /// relation on the nodes of the graph. Two nodes are in relationship
357 /// when there are directed paths between them in both direction.
359 /// \image html strongly_connected_components.png
360 /// \image latex strongly_connected_components.eps "Strongly connected components" width=\textwidth
362 /// \param graph The graph.
363 /// \retval compMap A writable node map. The values will be set from 0 to
364 /// the number of the strongly connected components minus one. Each values
365 /// of the map will be set exactly once, the values of a certain component
366 /// will be set continuously.
367 /// \return The number of components
369 template <typename Graph, typename NodeMap>
370 int stronglyConnectedComponents(const Graph& graph, NodeMap& compMap) {
371 checkConcept<concept::StaticGraph, Graph>();
372 typedef typename Graph::Node Node;
373 typedef typename Graph::NodeIt NodeIt;
374 checkConcept<concept::WriteMap<Node, int>, NodeMap>();
376 using namespace _topology_bits;
378 typedef std::vector<Node> Container;
379 typedef typename Container::iterator Iterator;
381 Container nodes(countNodes(graph));
382 typedef LeaveOrderVisitor<Graph, Iterator> Visitor;
383 Visitor visitor(nodes.begin());
385 DfsVisit<Graph, Visitor> dfs(graph, visitor);
387 for (NodeIt it(graph); it != INVALID; ++it) {
388 if (!dfs.reached(it)) {
394 typedef typename Container::reverse_iterator RIterator;
395 typedef RevGraphAdaptor<const Graph> RGraph;
397 RGraph rgraph(graph);
401 typedef FillMapVisitor<RGraph, NodeMap> RVisitor;
402 RVisitor rvisitor(compMap, compNum);
404 DfsVisit<RGraph, RVisitor> rdfs(rgraph, rvisitor);
407 for (RIterator it = nodes.rbegin(); it != nodes.rend(); ++it) {
408 if (!rdfs.reached(*it)) {
417 /// \ingroup topology
419 /// \brief Find the cut edges of the strongly connected components.
421 /// Find the cut edges of the strongly connected components.
422 /// The strongly connected components are the classes of an equivalence
423 /// relation on the nodes of the graph. Two nodes are in relationship
424 /// when there are directed paths between them in both direction.
425 /// The strongly connected components are separated by the cut edges.
427 /// \param graph The graph.
428 /// \retval cutMap A writable node map. The values will be set true when the
429 /// edge is a cut edge.
431 /// \return The number of cut edges
432 template <typename Graph, typename EdgeMap>
433 int stronglyConnectedCutEdges(const Graph& graph, EdgeMap& cutMap) {
434 checkConcept<concept::StaticGraph, Graph>();
435 typedef typename Graph::Node Node;
436 typedef typename Graph::Edge Edge;
437 typedef typename Graph::NodeIt NodeIt;
438 checkConcept<concept::WriteMap<Edge, bool>, EdgeMap>();
440 using namespace _topology_bits;
442 typedef std::vector<Node> Container;
443 typedef typename Container::iterator Iterator;
445 Container nodes(countNodes(graph));
446 typedef LeaveOrderVisitor<Graph, Iterator> Visitor;
447 Visitor visitor(nodes.begin());
449 DfsVisit<Graph, Visitor> dfs(graph, visitor);
451 for (NodeIt it(graph); it != INVALID; ++it) {
452 if (!dfs.reached(it)) {
458 typedef typename Container::reverse_iterator RIterator;
459 typedef RevGraphAdaptor<const Graph> RGraph;
461 RGraph rgraph(graph);
465 typedef StronglyConnectedCutEdgesVisitor<RGraph, EdgeMap> RVisitor;
466 RVisitor rvisitor(rgraph, cutMap, cutNum);
468 DfsVisit<RGraph, RVisitor> rdfs(rgraph, rvisitor);
471 for (RIterator it = nodes.rbegin(); it != nodes.rend(); ++it) {
472 if (!rdfs.reached(*it)) {
480 namespace _topology_bits {
482 template <typename Graph>
483 class CountBiNodeConnectedComponentsVisitor : public DfsVisitor<Graph> {
485 typedef typename Graph::Node Node;
486 typedef typename Graph::Edge Edge;
487 typedef typename Graph::UndirEdge UndirEdge;
489 CountBiNodeConnectedComponentsVisitor(const Graph& graph, int &compNum)
490 : _graph(graph), _compNum(compNum),
491 _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
493 void start(const Node& node) {
494 _predMap.set(node, INVALID);
497 void reach(const Node& node) {
498 _numMap.set(node, _num);
499 _retMap.set(node, _num);
503 void discover(const Edge& edge) {
504 _predMap.set(_graph.target(edge), _graph.source(edge));
507 void examine(const Edge& edge) {
508 if (_graph.source(edge) == _graph.target(edge) &&
509 _graph.direction(edge)) {
513 if (_predMap[_graph.source(edge)] == _graph.target(edge)) {
516 if (_retMap[_graph.source(edge)] > _numMap[_graph.target(edge)]) {
517 _retMap.set(_graph.source(edge), _numMap[_graph.target(edge)]);
521 void backtrack(const Edge& edge) {
522 if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
523 _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
525 if (_numMap[_graph.source(edge)] <= _retMap[_graph.target(edge)]) {
534 typename Graph::template NodeMap<int> _numMap;
535 typename Graph::template NodeMap<int> _retMap;
536 typename Graph::template NodeMap<Node> _predMap;
540 template <typename Graph, typename EdgeMap>
541 class BiNodeConnectedComponentsVisitor : public DfsVisitor<Graph> {
543 typedef typename Graph::Node Node;
544 typedef typename Graph::Edge Edge;
545 typedef typename Graph::UndirEdge UndirEdge;
547 BiNodeConnectedComponentsVisitor(const Graph& graph,
548 EdgeMap& compMap, int &compNum)
549 : _graph(graph), _compMap(compMap), _compNum(compNum),
550 _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
552 void start(const Node& node) {
553 _predMap.set(node, INVALID);
556 void reach(const Node& node) {
557 _numMap.set(node, _num);
558 _retMap.set(node, _num);
562 void discover(const Edge& edge) {
563 Node target = _graph.target(edge);
564 _predMap.set(target, edge);
565 _edgeStack.push(edge);
568 void examine(const Edge& edge) {
569 Node source = _graph.source(edge);
570 Node target = _graph.target(edge);
571 if (source == target && _graph.direction(edge)) {
572 _compMap.set(edge, _compNum);
576 if (_numMap[target] < _numMap[source]) {
577 if (_predMap[source] != _graph.oppositeEdge(edge)) {
578 _edgeStack.push(edge);
581 if (_predMap[source] != INVALID &&
582 target == _graph.source(_predMap[source])) {
585 if (_retMap[source] > _numMap[target]) {
586 _retMap.set(source, _numMap[target]);
590 void backtrack(const Edge& edge) {
591 Node source = _graph.source(edge);
592 Node target = _graph.target(edge);
593 if (_retMap[source] > _retMap[target]) {
594 _retMap.set(source, _retMap[target]);
596 if (_numMap[source] <= _retMap[target]) {
597 while (_edgeStack.top() != edge) {
598 _compMap.set(_edgeStack.top(), _compNum);
601 _compMap.set(edge, _compNum);
612 typename Graph::template NodeMap<int> _numMap;
613 typename Graph::template NodeMap<int> _retMap;
614 typename Graph::template NodeMap<Edge> _predMap;
615 std::stack<UndirEdge> _edgeStack;
620 template <typename Graph, typename NodeMap>
621 class BiNodeConnectedCutNodesVisitor : public DfsVisitor<Graph> {
623 typedef typename Graph::Node Node;
624 typedef typename Graph::Edge Edge;
625 typedef typename Graph::UndirEdge UndirEdge;
627 BiNodeConnectedCutNodesVisitor(const Graph& graph, NodeMap& cutMap,
629 : _graph(graph), _cutMap(cutMap), _cutNum(cutNum),
630 _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
632 void start(const Node& node) {
633 _predMap.set(node, INVALID);
637 void reach(const Node& node) {
638 _numMap.set(node, _num);
639 _retMap.set(node, _num);
643 void discover(const Edge& edge) {
644 _predMap.set(_graph.target(edge), _graph.source(edge));
647 void examine(const Edge& edge) {
648 if (_graph.source(edge) == _graph.target(edge) &&
649 _graph.direction(edge)) {
650 if (!_cutMap[_graph.source(edge)]) {
651 _cutMap.set(_graph.source(edge), true);
656 if (_predMap[_graph.source(edge)] == _graph.target(edge)) return;
657 if (_retMap[_graph.source(edge)] > _numMap[_graph.target(edge)]) {
658 _retMap.set(_graph.source(edge), _numMap[_graph.target(edge)]);
662 void backtrack(const Edge& edge) {
663 if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
664 _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
666 if (_numMap[_graph.source(edge)] <= _retMap[_graph.target(edge)]) {
667 if (_predMap[_graph.source(edge)] != INVALID) {
668 if (!_cutMap[_graph.source(edge)]) {
669 _cutMap.set(_graph.source(edge), true);
672 } else if (rootCut) {
673 if (!_cutMap[_graph.source(edge)]) {
674 _cutMap.set(_graph.source(edge), true);
688 typename Graph::template NodeMap<int> _numMap;
689 typename Graph::template NodeMap<int> _retMap;
690 typename Graph::template NodeMap<Node> _predMap;
691 std::stack<UndirEdge> _edgeStack;
698 template <typename UndirGraph>
699 int countBiNodeConnectedComponents(const UndirGraph& graph);
701 /// \ingroup topology
703 /// \brief Checks the graph is bi-node-connected.
705 /// This function checks that the undirected graph is bi-node-connected
706 /// graph. The graph is bi-node-connected if any two undirected edge is
709 /// \param graph The graph.
710 /// \return %True when the graph bi-node-connected.
711 /// \todo Make it faster.
712 template <typename UndirGraph>
713 bool biNodeConnected(const UndirGraph& graph) {
714 return countBiNodeConnectedComponents(graph) == 1;
717 /// \ingroup topology
719 /// \brief Count the biconnected components.
721 /// This function finds the bi-node-connected components in an undirected
722 /// graph. The biconnected components are the classes of an equivalence
723 /// relation on the undirected edges. Two undirected edge is in relationship
724 /// when they are on same circle.
726 /// \param graph The graph.
727 /// \return The number of components.
728 template <typename UndirGraph>
729 int countBiNodeConnectedComponents(const UndirGraph& graph) {
730 checkConcept<concept::UndirGraph, UndirGraph>();
731 typedef typename UndirGraph::NodeIt NodeIt;
733 using namespace _topology_bits;
735 typedef CountBiNodeConnectedComponentsVisitor<UndirGraph> Visitor;
738 Visitor visitor(graph, compNum);
740 DfsVisit<UndirGraph, Visitor> dfs(graph, visitor);
743 for (NodeIt it(graph); it != INVALID; ++it) {
744 if (!dfs.reached(it)) {
752 /// \ingroup topology
754 /// \brief Find the bi-node-connected components.
756 /// This function finds the bi-node-connected components in an undirected
757 /// graph. The bi-node-connected components are the classes of an equivalence
758 /// relation on the undirected edges. Two undirected edge are in relationship
759 /// when they are on same circle.
761 /// \image html node_biconnected_components.png
762 /// \image latex node_biconnected_components.eps "bi-node-connected components" width=\textwidth
764 /// \param graph The graph.
765 /// \retval compMap A writable undir edge map. The values will be set from 0
766 /// to the number of the biconnected components minus one. Each values
767 /// of the map will be set exactly once, the values of a certain component
768 /// will be set continuously.
769 /// \return The number of components.
771 template <typename UndirGraph, typename UndirEdgeMap>
772 int biNodeConnectedComponents(const UndirGraph& graph,
773 UndirEdgeMap& compMap) {
774 checkConcept<concept::UndirGraph, UndirGraph>();
775 typedef typename UndirGraph::NodeIt NodeIt;
776 typedef typename UndirGraph::UndirEdge UndirEdge;
777 checkConcept<concept::WriteMap<UndirEdge, int>, UndirEdgeMap>();
779 using namespace _topology_bits;
781 typedef BiNodeConnectedComponentsVisitor<UndirGraph, UndirEdgeMap> Visitor;
784 Visitor visitor(graph, compMap, compNum);
786 DfsVisit<UndirGraph, Visitor> dfs(graph, visitor);
789 for (NodeIt it(graph); it != INVALID; ++it) {
790 if (!dfs.reached(it)) {
798 /// \ingroup topology
800 /// \brief Find the bi-node-connected cut nodes.
802 /// This function finds the bi-node-connected cut nodes in an undirected
803 /// graph. The bi-node-connected components are the classes of an equivalence
804 /// relation on the undirected edges. Two undirected edges are in
805 /// relationship when they are on same circle. The biconnected components
806 /// are separted by nodes which are the cut nodes of the components.
808 /// \param graph The graph.
809 /// \retval cutMap A writable edge map. The values will be set true when
810 /// the node separate two or more components.
811 /// \return The number of the cut nodes.
812 template <typename UndirGraph, typename NodeMap>
813 int biNodeConnectedCutNodes(const UndirGraph& graph, NodeMap& cutMap) {
814 checkConcept<concept::UndirGraph, UndirGraph>();
815 typedef typename UndirGraph::Node Node;
816 typedef typename UndirGraph::NodeIt NodeIt;
817 checkConcept<concept::WriteMap<Node, bool>, NodeMap>();
819 using namespace _topology_bits;
821 typedef BiNodeConnectedCutNodesVisitor<UndirGraph, NodeMap> Visitor;
824 Visitor visitor(graph, cutMap, cutNum);
826 DfsVisit<UndirGraph, Visitor> dfs(graph, visitor);
829 for (NodeIt it(graph); it != INVALID; ++it) {
830 if (!dfs.reached(it)) {
838 namespace _topology_bits {
840 template <typename Graph>
841 class CountBiEdgeConnectedComponentsVisitor : public DfsVisitor<Graph> {
843 typedef typename Graph::Node Node;
844 typedef typename Graph::Edge Edge;
845 typedef typename Graph::UndirEdge UndirEdge;
847 CountBiEdgeConnectedComponentsVisitor(const Graph& graph, int &compNum)
848 : _graph(graph), _compNum(compNum),
849 _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
851 void start(const Node& node) {
852 _predMap.set(node, INVALID);
855 void reach(const Node& node) {
856 _numMap.set(node, _num);
857 _retMap.set(node, _num);
861 void leave(const Node& node) {
862 if (_numMap[node] <= _retMap[node]) {
867 void discover(const Edge& edge) {
868 _predMap.set(_graph.target(edge), edge);
871 void examine(const Edge& edge) {
872 if (_predMap[_graph.source(edge)] == _graph.oppositeEdge(edge)) {
875 if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
876 _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
880 void backtrack(const Edge& edge) {
881 if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
882 _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
890 typename Graph::template NodeMap<int> _numMap;
891 typename Graph::template NodeMap<int> _retMap;
892 typename Graph::template NodeMap<Edge> _predMap;
896 template <typename Graph, typename NodeMap>
897 class BiEdgeConnectedComponentsVisitor : public DfsVisitor<Graph> {
899 typedef typename Graph::Node Node;
900 typedef typename Graph::Edge Edge;
901 typedef typename Graph::UndirEdge UndirEdge;
903 BiEdgeConnectedComponentsVisitor(const Graph& graph,
904 NodeMap& compMap, int &compNum)
905 : _graph(graph), _compMap(compMap), _compNum(compNum),
906 _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
908 void start(const Node& node) {
909 _predMap.set(node, INVALID);
912 void reach(const Node& node) {
913 _numMap.set(node, _num);
914 _retMap.set(node, _num);
915 _nodeStack.push(node);
919 void leave(const Node& node) {
920 if (_numMap[node] <= _retMap[node]) {
921 while (_nodeStack.top() != node) {
922 _compMap.set(_nodeStack.top(), _compNum);
925 _compMap.set(node, _compNum);
931 void discover(const Edge& edge) {
932 _predMap.set(_graph.target(edge), edge);
935 void examine(const Edge& edge) {
936 if (_predMap[_graph.source(edge)] == _graph.oppositeEdge(edge)) {
939 if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
940 _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
944 void backtrack(const Edge& edge) {
945 if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
946 _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
955 typename Graph::template NodeMap<int> _numMap;
956 typename Graph::template NodeMap<int> _retMap;
957 typename Graph::template NodeMap<Edge> _predMap;
958 std::stack<Node> _nodeStack;
963 template <typename Graph, typename EdgeMap>
964 class BiEdgeConnectedCutEdgesVisitor : public DfsVisitor<Graph> {
966 typedef typename Graph::Node Node;
967 typedef typename Graph::Edge Edge;
968 typedef typename Graph::UndirEdge UndirEdge;
970 BiEdgeConnectedCutEdgesVisitor(const Graph& graph,
971 EdgeMap& cutMap, int &cutNum)
972 : _graph(graph), _cutMap(cutMap), _cutNum(cutNum),
973 _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
975 void start(const Node& node) {
976 _predMap[node] = INVALID;
979 void reach(const Node& node) {
980 _numMap.set(node, _num);
981 _retMap.set(node, _num);
985 void leave(const Node& node) {
986 if (_numMap[node] <= _retMap[node]) {
987 if (_predMap[node] != INVALID) {
988 _cutMap.set(_predMap[node], true);
994 void discover(const Edge& edge) {
995 _predMap.set(_graph.target(edge), edge);
998 void examine(const Edge& edge) {
999 if (_predMap[_graph.source(edge)] == _graph.oppositeEdge(edge)) {
1002 if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
1003 _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
1007 void backtrack(const Edge& edge) {
1008 if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
1009 _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
1014 const Graph& _graph;
1018 typename Graph::template NodeMap<int> _numMap;
1019 typename Graph::template NodeMap<int> _retMap;
1020 typename Graph::template NodeMap<Edge> _predMap;
1025 template <typename UndirGraph>
1026 int countbiEdgeConnectedComponents(const UndirGraph& graph);
1028 /// \ingroup topology
1030 /// \brief Checks that the graph is bi-edge-connected.
1032 /// This function checks that the graph is bi-edge-connected. The undirected
1033 /// graph is bi-edge-connected when any two nodes are connected with two
1034 /// edge-disjoint paths.
1036 /// \param graph The undirected graph.
1037 /// \return The number of components.
1038 /// \todo Make it faster.
1039 template <typename UndirGraph>
1040 bool biEdgeConnected(const UndirGraph& graph) {
1041 return countBiEdgeConnectedComponents(graph) == 1;
1044 /// \ingroup topology
1046 /// \brief Count the bi-edge-connected components.
1048 /// This function count the bi-edge-connected components in an undirected
1049 /// graph. The bi-edge-connected components are the classes of an equivalence
1050 /// relation on the nodes. Two nodes are in relationship when they are
1051 /// connected with at least two edge-disjoint paths.
1053 /// \param graph The undirected graph.
1054 /// \return The number of components.
1055 template <typename UndirGraph>
1056 int countBiEdgeConnectedComponents(const UndirGraph& graph) {
1057 checkConcept<concept::UndirGraph, UndirGraph>();
1058 typedef typename UndirGraph::NodeIt NodeIt;
1060 using namespace _topology_bits;
1062 typedef CountBiEdgeConnectedComponentsVisitor<UndirGraph> Visitor;
1065 Visitor visitor(graph, compNum);
1067 DfsVisit<UndirGraph, Visitor> dfs(graph, visitor);
1070 for (NodeIt it(graph); it != INVALID; ++it) {
1071 if (!dfs.reached(it)) {
1079 /// \ingroup topology
1081 /// \brief Find the bi-edge-connected components.
1083 /// This function finds the bi-edge-connected components in an undirected
1084 /// graph. The bi-edge-connected components are the classes of an equivalence
1085 /// relation on the nodes. Two nodes are in relationship when they are
1086 /// connected at least two edge-disjoint paths.
1088 /// \image html edge_biconnected_components.png
1089 /// \image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth
1091 /// \param graph The graph.
1092 /// \retval compMap A writable node map. The values will be set from 0 to
1093 /// the number of the biconnected components minus one. Each values
1094 /// of the map will be set exactly once, the values of a certain component
1095 /// will be set continuously.
1096 /// \return The number of components.
1098 template <typename UndirGraph, typename NodeMap>
1099 int biEdgeConnectedComponents(const UndirGraph& graph, NodeMap& compMap) {
1100 checkConcept<concept::UndirGraph, UndirGraph>();
1101 typedef typename UndirGraph::NodeIt NodeIt;
1102 typedef typename UndirGraph::Node Node;
1103 checkConcept<concept::WriteMap<Node, int>, NodeMap>();
1105 using namespace _topology_bits;
1107 typedef BiEdgeConnectedComponentsVisitor<UndirGraph, NodeMap> Visitor;
1110 Visitor visitor(graph, compMap, compNum);
1112 DfsVisit<UndirGraph, Visitor> dfs(graph, visitor);
1115 for (NodeIt it(graph); it != INVALID; ++it) {
1116 if (!dfs.reached(it)) {
1124 /// \ingroup topology
1126 /// \brief Find the bi-edge-connected cut edges.
1128 /// This function finds the bi-edge-connected components in an undirected
1129 /// graph. The bi-edge-connected components are the classes of an equivalence
1130 /// relation on the nodes. Two nodes are in relationship when they are
1131 /// connected with at least two edge-disjoint paths. The bi-edge-connected
1132 /// components are separted by edges which are the cut edges of the
1135 /// \param graph The graph.
1136 /// \retval cutMap A writable node map. The values will be set true when the
1137 /// edge is a cut edge.
1138 /// \return The number of cut edges.
1139 template <typename UndirGraph, typename UndirEdgeMap>
1140 int biEdgeConnectedCutEdges(const UndirGraph& graph, UndirEdgeMap& cutMap) {
1141 checkConcept<concept::UndirGraph, UndirGraph>();
1142 typedef typename UndirGraph::NodeIt NodeIt;
1143 typedef typename UndirGraph::UndirEdge UndirEdge;
1144 checkConcept<concept::WriteMap<UndirEdge, bool>, UndirEdgeMap>();
1146 using namespace _topology_bits;
1148 typedef BiEdgeConnectedCutEdgesVisitor<UndirGraph, UndirEdgeMap> Visitor;
1151 Visitor visitor(graph, cutMap, cutNum);
1153 DfsVisit<UndirGraph, Visitor> dfs(graph, visitor);
1156 for (NodeIt it(graph); it != INVALID; ++it) {
1157 if (!dfs.reached(it)) {
1166 namespace _topology_bits {
1168 template <typename Graph, typename IntNodeMap>
1169 class TopologicalSortVisitor : public DfsVisitor<Graph> {
1171 typedef typename Graph::Node Node;
1172 typedef typename Graph::Edge edge;
1174 TopologicalSortVisitor(IntNodeMap& order, int num)
1175 : _order(order), _num(num) {}
1177 void leave(const Node& node) {
1178 _order.set(node, --_num);
1188 /// \ingroup topology
1190 /// \brief Sort the nodes of a DAG into topolgical order.
1192 /// Sort the nodes of a DAG into topolgical order.
1194 /// \param graph The graph. It should be directed and acyclic.
1195 /// \retval order A writable node map. The values will be set from 0 to
1196 /// the number of the nodes in the graph minus one. Each values of the map
1197 /// will be set exactly once, the values will be set descending order.
1199 /// \see checkedTopologicalSort
1201 template <typename Graph, typename NodeMap>
1202 void topologicalSort(const Graph& graph, NodeMap& order) {
1203 using namespace _topology_bits;
1205 checkConcept<concept::StaticGraph, Graph>();
1206 checkConcept<concept::WriteMap<typename Graph::Node, int>, NodeMap>();
1208 typedef typename Graph::Node Node;
1209 typedef typename Graph::NodeIt NodeIt;
1210 typedef typename Graph::Edge Edge;
1212 TopologicalSortVisitor<Graph, NodeMap>
1213 visitor(order, countNodes(graph));
1215 DfsVisit<Graph, TopologicalSortVisitor<Graph, NodeMap> >
1216 dfs(graph, visitor);
1219 for (NodeIt it(graph); it != INVALID; ++it) {
1220 if (!dfs.reached(it)) {
1227 /// \ingroup topology
1229 /// \brief Sort the nodes of a DAG into topolgical order.
1231 /// Sort the nodes of a DAG into topolgical order. It also checks
1232 /// that the given graph is DAG.
1234 /// \param graph The graph. It should be directed and acyclic.
1235 /// \retval order A readable - writable node map. The values will be set
1236 /// from 0 to the number of the nodes in the graph minus one. Each values
1237 /// of the map will be set exactly once, the values will be set descending
1239 /// \return %False when the graph is not DAG.
1241 /// \see topologicalSort
1243 template <typename Graph, typename NodeMap>
1244 bool checkedTopologicalSort(const Graph& graph, NodeMap& order) {
1245 using namespace _topology_bits;
1247 checkConcept<concept::StaticGraph, Graph>();
1248 checkConcept<concept::ReadWriteMap<typename Graph::Node, int>, NodeMap>();
1250 typedef typename Graph::Node Node;
1251 typedef typename Graph::NodeIt NodeIt;
1252 typedef typename Graph::Edge Edge;
1254 order = constMap<Node, int, -1>();
1256 TopologicalSortVisitor<Graph, NodeMap>
1257 visitor(order, countNodes(graph));
1259 DfsVisit<Graph, TopologicalSortVisitor<Graph, NodeMap> >
1260 dfs(graph, visitor);
1263 for (NodeIt it(graph); it != INVALID; ++it) {
1264 if (!dfs.reached(it)) {
1266 while (!dfs.emptyQueue()) {
1267 Edge edge = dfs.nextEdge();
1268 Node target = graph.target(edge);
1269 if (dfs.reached(target) && order[target] == -1) {
1272 dfs.processNextEdge();
1279 /// \ingroup topology
1281 /// \brief Check that the given directed graph is a DAG.
1283 /// Check that the given directed graph is a DAG. The DAG is
1284 /// an Directed Acyclic Graph.
1285 /// \return %False when the graph is not DAG.
1287 template <typename Graph>
1288 bool dag(const Graph& graph) {
1290 checkConcept<concept::StaticGraph, Graph>();
1292 typedef typename Graph::Node Node;
1293 typedef typename Graph::NodeIt NodeIt;
1294 typedef typename Graph::Edge Edge;
1296 typedef typename Graph::template NodeMap<bool> ProcessedMap;
1298 typename Dfs<Graph>::template DefProcessedMap<ProcessedMap>::
1301 ProcessedMap processed(graph);
1302 dfs.processedMap(processed);
1305 for (NodeIt it(graph); it != INVALID; ++it) {
1306 if (!dfs.reached(it)) {
1308 while (!dfs.emptyQueue()) {
1309 Edge edge = dfs.nextEdge();
1310 Node target = graph.target(edge);
1311 if (dfs.reached(target) && !processed[target]) {
1314 dfs.processNextEdge();
1321 /// \ingroup topology
1323 /// \brief Check that the given undirected graph is acyclic.
1325 /// Check that the given undirected graph acyclic.
1326 /// \param graph The undirected graph.
1327 /// \return %True when there is no circle in the graph.
1329 template <typename UndirGraph>
1330 bool acyclic(const UndirGraph& graph) {
1331 checkConcept<concept::UndirGraph, UndirGraph>();
1332 typedef typename UndirGraph::Node Node;
1333 typedef typename UndirGraph::NodeIt NodeIt;
1334 typedef typename UndirGraph::Edge Edge;
1335 Dfs<UndirGraph> dfs(graph);
1337 for (NodeIt it(graph); it != INVALID; ++it) {
1338 if (!dfs.reached(it)) {
1340 while (!dfs.emptyQueue()) {
1341 Edge edge = dfs.nextEdge();
1342 Node source = graph.source(edge);
1343 Node target = graph.target(edge);
1344 if (dfs.reached(target) &&
1345 dfs.predEdge(source) != graph.oppositeEdge(edge)) {
1348 dfs.processNextEdge();
1355 /// \ingroup topology
1357 /// \brief Check that the given undirected graph is tree.
1359 /// Check that the given undirected graph is tree.
1360 /// \param graph The undirected graph.
1361 /// \return %True when the graph is acyclic and connected.
1362 template <typename UndirGraph>
1363 bool tree(const UndirGraph& graph) {
1364 checkConcept<concept::UndirGraph, UndirGraph>();
1365 typedef typename UndirGraph::Node Node;
1366 typedef typename UndirGraph::NodeIt NodeIt;
1367 typedef typename UndirGraph::Edge Edge;
1368 Dfs<UndirGraph> dfs(graph);
1370 dfs.addSource(NodeIt(graph));
1371 while (!dfs.emptyQueue()) {
1372 Edge edge = dfs.nextEdge();
1373 Node source = graph.source(edge);
1374 Node target = graph.target(edge);
1375 if (dfs.reached(target) &&
1376 dfs.predEdge(source) != graph.oppositeEdge(edge)) {
1379 dfs.processNextEdge();
1381 for (NodeIt it(graph); it != INVALID; ++it) {
1382 if (!dfs.reached(it)) {
1389 /// \ingroup topology
1391 /// \brief Check if the given undirected graph is bipartite or not
1393 /// The function checks if the given undirected \c graph graph is bipartite
1394 /// or not. The \ref Bfs algorithm is used to calculate the result.
1395 /// \param graph The undirected graph.
1396 /// \return %True if \c graph is bipartite, %false otherwise.
1397 /// \sa bipartitePartitions
1399 /// \author Balazs Attila Mihaly
1400 template<typename UndirGraph>
1401 inline bool bipartite(const UndirGraph &graph){
1402 checkConcept<concept::UndirGraph, UndirGraph>();
1404 typedef typename UndirGraph::NodeIt NodeIt;
1405 typedef typename UndirGraph::EdgeIt EdgeIt;
1407 Bfs<UndirGraph> bfs(graph);
1409 for(NodeIt i(graph);i!=INVALID;++i){
1410 if(!bfs.reached(i)){
1414 for(EdgeIt i(graph);i!=INVALID;++i){
1415 if(bfs.dist(graph.source(i))==bfs.dist(graph.target(i)))return false;
1420 /// \ingroup topology
1422 /// \brief Check if the given undirected graph is bipartite or not
1424 /// The function checks if the given undirected graph is bipartite
1425 /// or not. The \ref Bfs algorithm is used to calculate the result.
1426 /// During the execution, the \c partMap will be set as the two
1427 /// partitions of the graph.
1428 /// \param graph The undirected graph.
1429 /// \retval partMap A writable bool map of nodes. It will be set as the
1430 /// two partitions of the graph.
1431 /// \return %True if \c graph is bipartite, %false otherwise.
1433 /// \author Balazs Attila Mihaly
1435 /// \image html bipartite_partitions.png
1436 /// \image latex bipartite_partitions.eps "Bipartite partititions" width=\textwidth
1437 template<typename UndirGraph, typename NodeMap>
1438 inline bool bipartitePartitions(const UndirGraph &graph, NodeMap &partMap){
1439 checkConcept<concept::UndirGraph, UndirGraph>();
1441 typedef typename UndirGraph::Node Node;
1442 typedef typename UndirGraph::NodeIt NodeIt;
1443 typedef typename UndirGraph::EdgeIt EdgeIt;
1445 Bfs<UndirGraph> bfs(graph);
1447 for(NodeIt i(graph);i!=INVALID;++i){
1448 if(!bfs.reached(i)){
1450 for(Node j=bfs.processNextNode();!bfs.emptyQueue();
1451 j=bfs.processNextNode()){
1452 partMap.set(j,bfs.dist(j)%2==0);
1456 for(EdgeIt i(graph);i!=INVALID;++i){
1457 if(bfs.dist(graph.source(i)) == bfs.dist(graph.target(i)))return false;
1464 #endif //LEMON_TOPOLOGY_H