NewMapWin has become Dialog instead of Window. Therefore it is created dynamically, when there is need for it, instead of keeping one instance in memory. This solution is slower, but more correct than before.
2 * lemon/topology.h - Part of LEMON, a generic C++ optimization library
4 * Copyright (C) 2005 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