Consider the CPXMIP_OPTIMAL_TOL status as OPTIMAL too.
3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2007
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/concepts/graph.h>
29 #include <lemon/concepts/ugraph.h>
30 #include <lemon/concept_check.h>
32 #include <lemon/bin_heap.h>
33 #include <lemon/bucket_heap.h>
38 /// \ingroup graph_prop
40 /// \brief Topology related algorithms
42 /// Topology related algorithms
46 /// \ingroup graph_prop
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<concepts::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)) {
69 /// \ingroup graph_prop
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<concepts::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 graph_prop
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<concepts::UGraph, UGraph>();
130 typedef typename UGraph::Node Node;
131 typedef typename UGraph::Edge Edge;
132 checkConcept<concepts::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 graph_prop
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<concepts::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 graph_prop
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
296 /// equivalence relation on the nodes of the graph. Two nodes are in
297 /// the same class if they are connected with directed paths in both
300 /// \param graph The graph.
301 /// \return The number of components
302 /// \note By definition, the empty graph has zero
303 /// strongly connected components.
304 template <typename Graph>
305 int countStronglyConnectedComponents(const Graph& graph) {
306 checkConcept<concepts::Graph, Graph>();
308 using namespace _topology_bits;
310 typedef typename Graph::Node Node;
311 typedef typename Graph::Edge Edge;
312 typedef typename Graph::NodeIt NodeIt;
313 typedef typename Graph::EdgeIt EdgeIt;
315 typedef std::vector<Node> Container;
316 typedef typename Container::iterator Iterator;
318 Container nodes(countNodes(graph));
319 typedef LeaveOrderVisitor<Graph, Iterator> Visitor;
320 Visitor visitor(nodes.begin());
322 DfsVisit<Graph, Visitor> dfs(graph, visitor);
324 for (NodeIt it(graph); it != INVALID; ++it) {
325 if (!dfs.reached(it)) {
331 typedef typename Container::reverse_iterator RIterator;
332 typedef RevGraphAdaptor<const Graph> RGraph;
334 RGraph rgraph(graph);
336 typedef DfsVisitor<Graph> RVisitor;
339 DfsVisit<RGraph, RVisitor> rdfs(rgraph, rvisitor);
344 for (RIterator it = nodes.rbegin(); it != nodes.rend(); ++it) {
345 if (!rdfs.reached(*it)) {
354 /// \ingroup graph_prop
356 /// \brief Find the strongly connected components of a directed graph
358 /// Find the strongly connected components of a directed graph. The
359 /// strongly connected components are the classes of an equivalence
360 /// relation on the nodes of the graph. Two nodes are in
361 /// relationship when there are directed paths between them in both
362 /// direction. In addition, the numbering of components will satisfy
363 /// that there is no edge going from a higher numbered component to
366 /// \image html strongly_connected_components.png
367 /// \image latex strongly_connected_components.eps "Strongly connected components" width=\textwidth
369 /// \param graph The graph.
370 /// \retval compMap A writable node map. The values will be set from 0 to
371 /// the number of the strongly connected components minus one. Each value
372 /// of the map will be set exactly once, the values of a certain component
373 /// will be set continuously.
374 /// \return The number of components
376 template <typename Graph, typename NodeMap>
377 int stronglyConnectedComponents(const Graph& graph, NodeMap& compMap) {
378 checkConcept<concepts::Graph, Graph>();
379 typedef typename Graph::Node Node;
380 typedef typename Graph::NodeIt NodeIt;
381 checkConcept<concepts::WriteMap<Node, int>, NodeMap>();
383 using namespace _topology_bits;
385 typedef std::vector<Node> Container;
386 typedef typename Container::iterator Iterator;
388 Container nodes(countNodes(graph));
389 typedef LeaveOrderVisitor<Graph, Iterator> Visitor;
390 Visitor visitor(nodes.begin());
392 DfsVisit<Graph, Visitor> dfs(graph, visitor);
394 for (NodeIt it(graph); it != INVALID; ++it) {
395 if (!dfs.reached(it)) {
401 typedef typename Container::reverse_iterator RIterator;
402 typedef RevGraphAdaptor<const Graph> RGraph;
404 RGraph rgraph(graph);
408 typedef FillMapVisitor<RGraph, NodeMap> RVisitor;
409 RVisitor rvisitor(compMap, compNum);
411 DfsVisit<RGraph, RVisitor> rdfs(rgraph, rvisitor);
414 for (RIterator it = nodes.rbegin(); it != nodes.rend(); ++it) {
415 if (!rdfs.reached(*it)) {
424 /// \ingroup graph_prop
426 /// \brief Find the cut edges of the strongly connected components.
428 /// Find the cut edges of the strongly connected components.
429 /// The strongly connected components are the classes of an equivalence
430 /// relation on the nodes of the graph. Two nodes are in relationship
431 /// when there are directed paths between them in both direction.
432 /// The strongly connected components are separated by the cut edges.
434 /// \param graph The graph.
435 /// \retval cutMap A writable node map. The values will be set true when the
436 /// edge is a cut edge.
438 /// \return The number of cut edges
439 template <typename Graph, typename EdgeMap>
440 int stronglyConnectedCutEdges(const Graph& graph, EdgeMap& cutMap) {
441 checkConcept<concepts::Graph, Graph>();
442 typedef typename Graph::Node Node;
443 typedef typename Graph::Edge Edge;
444 typedef typename Graph::NodeIt NodeIt;
445 checkConcept<concepts::WriteMap<Edge, bool>, EdgeMap>();
447 using namespace _topology_bits;
449 typedef std::vector<Node> Container;
450 typedef typename Container::iterator Iterator;
452 Container nodes(countNodes(graph));
453 typedef LeaveOrderVisitor<Graph, Iterator> Visitor;
454 Visitor visitor(nodes.begin());
456 DfsVisit<Graph, Visitor> dfs(graph, visitor);
458 for (NodeIt it(graph); it != INVALID; ++it) {
459 if (!dfs.reached(it)) {
465 typedef typename Container::reverse_iterator RIterator;
466 typedef RevGraphAdaptor<const Graph> RGraph;
468 RGraph rgraph(graph);
472 typedef StronglyConnectedCutEdgesVisitor<RGraph, EdgeMap> RVisitor;
473 RVisitor rvisitor(rgraph, cutMap, cutNum);
475 DfsVisit<RGraph, RVisitor> rdfs(rgraph, rvisitor);
478 for (RIterator it = nodes.rbegin(); it != nodes.rend(); ++it) {
479 if (!rdfs.reached(*it)) {
487 namespace _topology_bits {
489 template <typename Graph>
490 class CountBiNodeConnectedComponentsVisitor : public DfsVisitor<Graph> {
492 typedef typename Graph::Node Node;
493 typedef typename Graph::Edge Edge;
494 typedef typename Graph::UEdge UEdge;
496 CountBiNodeConnectedComponentsVisitor(const Graph& graph, int &compNum)
497 : _graph(graph), _compNum(compNum),
498 _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
500 void start(const Node& node) {
501 _predMap.set(node, INVALID);
504 void reach(const Node& node) {
505 _numMap.set(node, _num);
506 _retMap.set(node, _num);
510 void discover(const Edge& edge) {
511 _predMap.set(_graph.target(edge), _graph.source(edge));
514 void examine(const Edge& edge) {
515 if (_graph.source(edge) == _graph.target(edge) &&
516 _graph.direction(edge)) {
520 if (_predMap[_graph.source(edge)] == _graph.target(edge)) {
523 if (_retMap[_graph.source(edge)] > _numMap[_graph.target(edge)]) {
524 _retMap.set(_graph.source(edge), _numMap[_graph.target(edge)]);
528 void backtrack(const Edge& edge) {
529 if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
530 _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
532 if (_numMap[_graph.source(edge)] <= _retMap[_graph.target(edge)]) {
541 typename Graph::template NodeMap<int> _numMap;
542 typename Graph::template NodeMap<int> _retMap;
543 typename Graph::template NodeMap<Node> _predMap;
547 template <typename Graph, typename EdgeMap>
548 class BiNodeConnectedComponentsVisitor : public DfsVisitor<Graph> {
550 typedef typename Graph::Node Node;
551 typedef typename Graph::Edge Edge;
552 typedef typename Graph::UEdge UEdge;
554 BiNodeConnectedComponentsVisitor(const Graph& graph,
555 EdgeMap& compMap, int &compNum)
556 : _graph(graph), _compMap(compMap), _compNum(compNum),
557 _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
559 void start(const Node& node) {
560 _predMap.set(node, INVALID);
563 void reach(const Node& node) {
564 _numMap.set(node, _num);
565 _retMap.set(node, _num);
569 void discover(const Edge& edge) {
570 Node target = _graph.target(edge);
571 _predMap.set(target, edge);
572 _edgeStack.push(edge);
575 void examine(const Edge& edge) {
576 Node source = _graph.source(edge);
577 Node target = _graph.target(edge);
578 if (source == target && _graph.direction(edge)) {
579 _compMap.set(edge, _compNum);
583 if (_numMap[target] < _numMap[source]) {
584 if (_predMap[source] != _graph.oppositeEdge(edge)) {
585 _edgeStack.push(edge);
588 if (_predMap[source] != INVALID &&
589 target == _graph.source(_predMap[source])) {
592 if (_retMap[source] > _numMap[target]) {
593 _retMap.set(source, _numMap[target]);
597 void backtrack(const Edge& edge) {
598 Node source = _graph.source(edge);
599 Node target = _graph.target(edge);
600 if (_retMap[source] > _retMap[target]) {
601 _retMap.set(source, _retMap[target]);
603 if (_numMap[source] <= _retMap[target]) {
604 while (_edgeStack.top() != edge) {
605 _compMap.set(_edgeStack.top(), _compNum);
608 _compMap.set(edge, _compNum);
619 typename Graph::template NodeMap<int> _numMap;
620 typename Graph::template NodeMap<int> _retMap;
621 typename Graph::template NodeMap<Edge> _predMap;
622 std::stack<UEdge> _edgeStack;
627 template <typename Graph, typename NodeMap>
628 class BiNodeConnectedCutNodesVisitor : public DfsVisitor<Graph> {
630 typedef typename Graph::Node Node;
631 typedef typename Graph::Edge Edge;
632 typedef typename Graph::UEdge UEdge;
634 BiNodeConnectedCutNodesVisitor(const Graph& graph, NodeMap& cutMap,
636 : _graph(graph), _cutMap(cutMap), _cutNum(cutNum),
637 _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
639 void start(const Node& node) {
640 _predMap.set(node, INVALID);
644 void reach(const Node& node) {
645 _numMap.set(node, _num);
646 _retMap.set(node, _num);
650 void discover(const Edge& edge) {
651 _predMap.set(_graph.target(edge), _graph.source(edge));
654 void examine(const Edge& edge) {
655 if (_graph.source(edge) == _graph.target(edge) &&
656 _graph.direction(edge)) {
657 if (!_cutMap[_graph.source(edge)]) {
658 _cutMap.set(_graph.source(edge), true);
663 if (_predMap[_graph.source(edge)] == _graph.target(edge)) return;
664 if (_retMap[_graph.source(edge)] > _numMap[_graph.target(edge)]) {
665 _retMap.set(_graph.source(edge), _numMap[_graph.target(edge)]);
669 void backtrack(const Edge& edge) {
670 if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
671 _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
673 if (_numMap[_graph.source(edge)] <= _retMap[_graph.target(edge)]) {
674 if (_predMap[_graph.source(edge)] != INVALID) {
675 if (!_cutMap[_graph.source(edge)]) {
676 _cutMap.set(_graph.source(edge), true);
679 } else if (rootCut) {
680 if (!_cutMap[_graph.source(edge)]) {
681 _cutMap.set(_graph.source(edge), true);
695 typename Graph::template NodeMap<int> _numMap;
696 typename Graph::template NodeMap<int> _retMap;
697 typename Graph::template NodeMap<Node> _predMap;
698 std::stack<UEdge> _edgeStack;
705 template <typename UGraph>
706 int countBiNodeConnectedComponents(const UGraph& graph);
708 /// \ingroup graph_prop
710 /// \brief Checks the graph is bi-node-connected.
712 /// This function checks that the undirected graph is bi-node-connected
713 /// graph. The graph is bi-node-connected if any two undirected edge is
716 /// \param graph The graph.
717 /// \return %True when the graph bi-node-connected.
718 /// \todo Make it faster.
719 template <typename UGraph>
720 bool biNodeConnected(const UGraph& graph) {
721 return countBiNodeConnectedComponents(graph) == 1;
724 /// \ingroup graph_prop
726 /// \brief Count the biconnected components.
728 /// This function finds the bi-node-connected components in an undirected
729 /// graph. The biconnected components are the classes of an equivalence
730 /// relation on the undirected edges. Two undirected edge is in relationship
731 /// when they are on same circle.
733 /// \param graph The graph.
734 /// \return The number of components.
735 template <typename UGraph>
736 int countBiNodeConnectedComponents(const UGraph& graph) {
737 checkConcept<concepts::UGraph, UGraph>();
738 typedef typename UGraph::NodeIt NodeIt;
740 using namespace _topology_bits;
742 typedef CountBiNodeConnectedComponentsVisitor<UGraph> Visitor;
745 Visitor visitor(graph, compNum);
747 DfsVisit<UGraph, Visitor> dfs(graph, visitor);
750 for (NodeIt it(graph); it != INVALID; ++it) {
751 if (!dfs.reached(it)) {
759 /// \ingroup graph_prop
761 /// \brief Find the bi-node-connected components.
763 /// This function finds the bi-node-connected components in an undirected
764 /// graph. The bi-node-connected components are the classes of an equivalence
765 /// relation on the undirected edges. Two undirected edge are in relationship
766 /// when they are on same circle.
768 /// \image html node_biconnected_components.png
769 /// \image latex node_biconnected_components.eps "bi-node-connected components" width=\textwidth
771 /// \param graph The graph.
772 /// \retval compMap A writable uedge map. The values will be set from 0
773 /// to the number of the biconnected components minus one. Each values
774 /// of the map will be set exactly once, the values of a certain component
775 /// will be set continuously.
776 /// \return The number of components.
778 template <typename UGraph, typename UEdgeMap>
779 int biNodeConnectedComponents(const UGraph& graph,
781 checkConcept<concepts::UGraph, UGraph>();
782 typedef typename UGraph::NodeIt NodeIt;
783 typedef typename UGraph::UEdge UEdge;
784 checkConcept<concepts::WriteMap<UEdge, int>, UEdgeMap>();
786 using namespace _topology_bits;
788 typedef BiNodeConnectedComponentsVisitor<UGraph, UEdgeMap> Visitor;
791 Visitor visitor(graph, compMap, compNum);
793 DfsVisit<UGraph, Visitor> dfs(graph, visitor);
796 for (NodeIt it(graph); it != INVALID; ++it) {
797 if (!dfs.reached(it)) {
805 /// \ingroup graph_prop
807 /// \brief Find the bi-node-connected cut nodes.
809 /// This function finds the bi-node-connected cut nodes in an undirected
810 /// graph. The bi-node-connected components are the classes of an equivalence
811 /// relation on the undirected edges. Two undirected edges are in
812 /// relationship when they are on same circle. The biconnected components
813 /// are separted by nodes which are the cut nodes of the components.
815 /// \param graph The graph.
816 /// \retval cutMap A writable edge map. The values will be set true when
817 /// the node separate two or more components.
818 /// \return The number of the cut nodes.
819 template <typename UGraph, typename NodeMap>
820 int biNodeConnectedCutNodes(const UGraph& graph, NodeMap& cutMap) {
821 checkConcept<concepts::UGraph, UGraph>();
822 typedef typename UGraph::Node Node;
823 typedef typename UGraph::NodeIt NodeIt;
824 checkConcept<concepts::WriteMap<Node, bool>, NodeMap>();
826 using namespace _topology_bits;
828 typedef BiNodeConnectedCutNodesVisitor<UGraph, NodeMap> Visitor;
831 Visitor visitor(graph, cutMap, cutNum);
833 DfsVisit<UGraph, Visitor> dfs(graph, visitor);
836 for (NodeIt it(graph); it != INVALID; ++it) {
837 if (!dfs.reached(it)) {
845 namespace _topology_bits {
847 template <typename Graph>
848 class CountBiEdgeConnectedComponentsVisitor : public DfsVisitor<Graph> {
850 typedef typename Graph::Node Node;
851 typedef typename Graph::Edge Edge;
852 typedef typename Graph::UEdge UEdge;
854 CountBiEdgeConnectedComponentsVisitor(const Graph& graph, int &compNum)
855 : _graph(graph), _compNum(compNum),
856 _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
858 void start(const Node& node) {
859 _predMap.set(node, INVALID);
862 void reach(const Node& node) {
863 _numMap.set(node, _num);
864 _retMap.set(node, _num);
868 void leave(const Node& node) {
869 if (_numMap[node] <= _retMap[node]) {
874 void discover(const Edge& edge) {
875 _predMap.set(_graph.target(edge), edge);
878 void examine(const Edge& edge) {
879 if (_predMap[_graph.source(edge)] == _graph.oppositeEdge(edge)) {
882 if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
883 _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
887 void backtrack(const Edge& edge) {
888 if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
889 _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
897 typename Graph::template NodeMap<int> _numMap;
898 typename Graph::template NodeMap<int> _retMap;
899 typename Graph::template NodeMap<Edge> _predMap;
903 template <typename Graph, typename NodeMap>
904 class BiEdgeConnectedComponentsVisitor : public DfsVisitor<Graph> {
906 typedef typename Graph::Node Node;
907 typedef typename Graph::Edge Edge;
908 typedef typename Graph::UEdge UEdge;
910 BiEdgeConnectedComponentsVisitor(const Graph& graph,
911 NodeMap& compMap, int &compNum)
912 : _graph(graph), _compMap(compMap), _compNum(compNum),
913 _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
915 void start(const Node& node) {
916 _predMap.set(node, INVALID);
919 void reach(const Node& node) {
920 _numMap.set(node, _num);
921 _retMap.set(node, _num);
922 _nodeStack.push(node);
926 void leave(const Node& node) {
927 if (_numMap[node] <= _retMap[node]) {
928 while (_nodeStack.top() != node) {
929 _compMap.set(_nodeStack.top(), _compNum);
932 _compMap.set(node, _compNum);
938 void discover(const Edge& edge) {
939 _predMap.set(_graph.target(edge), edge);
942 void examine(const Edge& edge) {
943 if (_predMap[_graph.source(edge)] == _graph.oppositeEdge(edge)) {
946 if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
947 _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
951 void backtrack(const Edge& edge) {
952 if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
953 _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
962 typename Graph::template NodeMap<int> _numMap;
963 typename Graph::template NodeMap<int> _retMap;
964 typename Graph::template NodeMap<Edge> _predMap;
965 std::stack<Node> _nodeStack;
970 template <typename Graph, typename EdgeMap>
971 class BiEdgeConnectedCutEdgesVisitor : public DfsVisitor<Graph> {
973 typedef typename Graph::Node Node;
974 typedef typename Graph::Edge Edge;
975 typedef typename Graph::UEdge UEdge;
977 BiEdgeConnectedCutEdgesVisitor(const Graph& graph,
978 EdgeMap& cutMap, int &cutNum)
979 : _graph(graph), _cutMap(cutMap), _cutNum(cutNum),
980 _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
982 void start(const Node& node) {
983 _predMap[node] = INVALID;
986 void reach(const Node& node) {
987 _numMap.set(node, _num);
988 _retMap.set(node, _num);
992 void leave(const Node& node) {
993 if (_numMap[node] <= _retMap[node]) {
994 if (_predMap[node] != INVALID) {
995 _cutMap.set(_predMap[node], true);
1001 void discover(const Edge& edge) {
1002 _predMap.set(_graph.target(edge), edge);
1005 void examine(const Edge& edge) {
1006 if (_predMap[_graph.source(edge)] == _graph.oppositeEdge(edge)) {
1009 if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
1010 _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
1014 void backtrack(const Edge& edge) {
1015 if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
1016 _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
1021 const Graph& _graph;
1025 typename Graph::template NodeMap<int> _numMap;
1026 typename Graph::template NodeMap<int> _retMap;
1027 typename Graph::template NodeMap<Edge> _predMap;
1032 template <typename UGraph>
1033 int countBiEdgeConnectedComponents(const UGraph& graph);
1035 /// \ingroup graph_prop
1037 /// \brief Checks that the graph is bi-edge-connected.
1039 /// This function checks that the graph is bi-edge-connected. The undirected
1040 /// graph is bi-edge-connected when any two nodes are connected with two
1041 /// edge-disjoint paths.
1043 /// \param graph The undirected graph.
1044 /// \return The number of components.
1045 /// \todo Make it faster.
1046 template <typename UGraph>
1047 bool biEdgeConnected(const UGraph& graph) {
1048 return countBiEdgeConnectedComponents(graph) == 1;
1051 /// \ingroup graph_prop
1053 /// \brief Count the bi-edge-connected components.
1055 /// This function count the bi-edge-connected components in an undirected
1056 /// graph. The bi-edge-connected components are the classes of an equivalence
1057 /// relation on the nodes. Two nodes are in relationship when they are
1058 /// connected with at least two edge-disjoint paths.
1060 /// \param graph The undirected graph.
1061 /// \return The number of components.
1062 template <typename UGraph>
1063 int countBiEdgeConnectedComponents(const UGraph& graph) {
1064 checkConcept<concepts::UGraph, UGraph>();
1065 typedef typename UGraph::NodeIt NodeIt;
1067 using namespace _topology_bits;
1069 typedef CountBiEdgeConnectedComponentsVisitor<UGraph> Visitor;
1072 Visitor visitor(graph, compNum);
1074 DfsVisit<UGraph, Visitor> dfs(graph, visitor);
1077 for (NodeIt it(graph); it != INVALID; ++it) {
1078 if (!dfs.reached(it)) {
1086 /// \ingroup graph_prop
1088 /// \brief Find the bi-edge-connected components.
1090 /// This function finds the bi-edge-connected components in an undirected
1091 /// graph. The bi-edge-connected components are the classes of an equivalence
1092 /// relation on the nodes. Two nodes are in relationship when they are
1093 /// connected at least two edge-disjoint paths.
1095 /// \image html edge_biconnected_components.png
1096 /// \image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth
1098 /// \param graph The graph.
1099 /// \retval compMap A writable node map. The values will be set from 0 to
1100 /// the number of the biconnected components minus one. Each values
1101 /// of the map will be set exactly once, the values of a certain component
1102 /// will be set continuously.
1103 /// \return The number of components.
1105 template <typename UGraph, typename NodeMap>
1106 int biEdgeConnectedComponents(const UGraph& graph, NodeMap& compMap) {
1107 checkConcept<concepts::UGraph, UGraph>();
1108 typedef typename UGraph::NodeIt NodeIt;
1109 typedef typename UGraph::Node Node;
1110 checkConcept<concepts::WriteMap<Node, int>, NodeMap>();
1112 using namespace _topology_bits;
1114 typedef BiEdgeConnectedComponentsVisitor<UGraph, NodeMap> Visitor;
1117 Visitor visitor(graph, compMap, compNum);
1119 DfsVisit<UGraph, Visitor> dfs(graph, visitor);
1122 for (NodeIt it(graph); it != INVALID; ++it) {
1123 if (!dfs.reached(it)) {
1131 /// \ingroup graph_prop
1133 /// \brief Find the bi-edge-connected cut edges.
1135 /// This function finds the bi-edge-connected components in an undirected
1136 /// graph. The bi-edge-connected components are the classes of an equivalence
1137 /// relation on the nodes. Two nodes are in relationship when they are
1138 /// connected with at least two edge-disjoint paths. The bi-edge-connected
1139 /// components are separted by edges which are the cut edges of the
1142 /// \param graph The graph.
1143 /// \retval cutMap A writable node map. The values will be set true when the
1144 /// edge is a cut edge.
1145 /// \return The number of cut edges.
1146 template <typename UGraph, typename UEdgeMap>
1147 int biEdgeConnectedCutEdges(const UGraph& graph, UEdgeMap& cutMap) {
1148 checkConcept<concepts::UGraph, UGraph>();
1149 typedef typename UGraph::NodeIt NodeIt;
1150 typedef typename UGraph::UEdge UEdge;
1151 checkConcept<concepts::WriteMap<UEdge, bool>, UEdgeMap>();
1153 using namespace _topology_bits;
1155 typedef BiEdgeConnectedCutEdgesVisitor<UGraph, UEdgeMap> Visitor;
1158 Visitor visitor(graph, cutMap, cutNum);
1160 DfsVisit<UGraph, Visitor> dfs(graph, visitor);
1163 for (NodeIt it(graph); it != INVALID; ++it) {
1164 if (!dfs.reached(it)) {
1173 namespace _topology_bits {
1175 template <typename Graph, typename IntNodeMap>
1176 class TopologicalSortVisitor : public DfsVisitor<Graph> {
1178 typedef typename Graph::Node Node;
1179 typedef typename Graph::Edge edge;
1181 TopologicalSortVisitor(IntNodeMap& order, int num)
1182 : _order(order), _num(num) {}
1184 void leave(const Node& node) {
1185 _order.set(node, --_num);
1195 /// \ingroup graph_prop
1197 /// \brief Sort the nodes of a DAG into topolgical order.
1199 /// Sort the nodes of a DAG into topolgical order.
1201 /// \param graph The graph. It should be directed and acyclic.
1202 /// \retval order A writable node map. The values will be set from 0 to
1203 /// the number of the nodes in the graph minus one. Each values of the map
1204 /// will be set exactly once, the values will be set descending order.
1206 /// \see checkedTopologicalSort
1208 template <typename Graph, typename NodeMap>
1209 void topologicalSort(const Graph& graph, NodeMap& order) {
1210 using namespace _topology_bits;
1212 checkConcept<concepts::Graph, Graph>();
1213 checkConcept<concepts::WriteMap<typename Graph::Node, int>, NodeMap>();
1215 typedef typename Graph::Node Node;
1216 typedef typename Graph::NodeIt NodeIt;
1217 typedef typename Graph::Edge Edge;
1219 TopologicalSortVisitor<Graph, NodeMap>
1220 visitor(order, countNodes(graph));
1222 DfsVisit<Graph, TopologicalSortVisitor<Graph, NodeMap> >
1223 dfs(graph, visitor);
1226 for (NodeIt it(graph); it != INVALID; ++it) {
1227 if (!dfs.reached(it)) {
1234 /// \ingroup graph_prop
1236 /// \brief Sort the nodes of a DAG into topolgical order.
1238 /// Sort the nodes of a DAG into topolgical order. It also checks
1239 /// that the given graph is DAG.
1241 /// \param graph The graph. It should be directed and acyclic.
1242 /// \retval order A readable - writable node map. The values will be set
1243 /// from 0 to the number of the nodes in the graph minus one. Each values
1244 /// of the map will be set exactly once, the values will be set descending
1246 /// \return %False when the graph is not DAG.
1248 /// \see topologicalSort
1250 template <typename Graph, typename NodeMap>
1251 bool checkedTopologicalSort(const Graph& graph, NodeMap& order) {
1252 using namespace _topology_bits;
1254 checkConcept<concepts::Graph, Graph>();
1255 checkConcept<concepts::ReadWriteMap<typename Graph::Node, int>, NodeMap>();
1257 typedef typename Graph::Node Node;
1258 typedef typename Graph::NodeIt NodeIt;
1259 typedef typename Graph::Edge Edge;
1261 order = constMap<Node, int, -1>();
1263 TopologicalSortVisitor<Graph, NodeMap>
1264 visitor(order, countNodes(graph));
1266 DfsVisit<Graph, TopologicalSortVisitor<Graph, NodeMap> >
1267 dfs(graph, visitor);
1270 for (NodeIt it(graph); it != INVALID; ++it) {
1271 if (!dfs.reached(it)) {
1273 while (!dfs.emptyQueue()) {
1274 Edge edge = dfs.nextEdge();
1275 Node target = graph.target(edge);
1276 if (dfs.reached(target) && order[target] == -1) {
1279 dfs.processNextEdge();
1286 /// \ingroup graph_prop
1288 /// \brief Check that the given directed graph is a DAG.
1290 /// Check that the given directed graph is a DAG. The DAG is
1291 /// an Directed Acyclic Graph.
1292 /// \return %False when the graph is not DAG.
1294 template <typename Graph>
1295 bool dag(const Graph& graph) {
1297 checkConcept<concepts::Graph, Graph>();
1299 typedef typename Graph::Node Node;
1300 typedef typename Graph::NodeIt NodeIt;
1301 typedef typename Graph::Edge Edge;
1303 typedef typename Graph::template NodeMap<bool> ProcessedMap;
1305 typename Dfs<Graph>::template DefProcessedMap<ProcessedMap>::
1308 ProcessedMap processed(graph);
1309 dfs.processedMap(processed);
1312 for (NodeIt it(graph); it != INVALID; ++it) {
1313 if (!dfs.reached(it)) {
1315 while (!dfs.emptyQueue()) {
1316 Edge edge = dfs.nextEdge();
1317 Node target = graph.target(edge);
1318 if (dfs.reached(target) && !processed[target]) {
1321 dfs.processNextEdge();
1328 /// \ingroup graph_prop
1330 /// \brief Check that the given undirected graph is acyclic.
1332 /// Check that the given undirected graph acyclic.
1333 /// \param graph The undirected graph.
1334 /// \return %True when there is no circle in the graph.
1336 template <typename UGraph>
1337 bool acyclic(const UGraph& graph) {
1338 checkConcept<concepts::UGraph, UGraph>();
1339 typedef typename UGraph::Node Node;
1340 typedef typename UGraph::NodeIt NodeIt;
1341 typedef typename UGraph::Edge Edge;
1342 Dfs<UGraph> dfs(graph);
1344 for (NodeIt it(graph); it != INVALID; ++it) {
1345 if (!dfs.reached(it)) {
1347 while (!dfs.emptyQueue()) {
1348 Edge edge = dfs.nextEdge();
1349 Node source = graph.source(edge);
1350 Node target = graph.target(edge);
1351 if (dfs.reached(target) &&
1352 dfs.predEdge(source) != graph.oppositeEdge(edge)) {
1355 dfs.processNextEdge();
1362 /// \ingroup graph_prop
1364 /// \brief Check that the given undirected graph is tree.
1366 /// Check that the given undirected graph is tree.
1367 /// \param graph The undirected graph.
1368 /// \return %True when the graph is acyclic and connected.
1369 template <typename UGraph>
1370 bool tree(const UGraph& graph) {
1371 checkConcept<concepts::UGraph, UGraph>();
1372 typedef typename UGraph::Node Node;
1373 typedef typename UGraph::NodeIt NodeIt;
1374 typedef typename UGraph::Edge Edge;
1375 Dfs<UGraph> dfs(graph);
1377 dfs.addSource(NodeIt(graph));
1378 while (!dfs.emptyQueue()) {
1379 Edge edge = dfs.nextEdge();
1380 Node source = graph.source(edge);
1381 Node target = graph.target(edge);
1382 if (dfs.reached(target) &&
1383 dfs.predEdge(source) != graph.oppositeEdge(edge)) {
1386 dfs.processNextEdge();
1388 for (NodeIt it(graph); it != INVALID; ++it) {
1389 if (!dfs.reached(it)) {
1396 namespace _topology_bits {
1398 template <typename Graph>
1399 class BipartiteVisitor : public BfsVisitor<Graph> {
1401 typedef typename Graph::Edge Edge;
1402 typedef typename Graph::Node Node;
1404 BipartiteVisitor(const Graph& graph, bool& bipartite)
1405 : _graph(graph), _part(graph), _bipartite(bipartite) {}
1407 void start(const Node& node) {
1410 void discover(const Edge& edge) {
1411 _part.set(_graph.target(edge), !_part[_graph.source(edge)]);
1413 void examine(const Edge& edge) {
1414 _bipartite = _bipartite &&
1415 _part[_graph.target(edge)] != _part[_graph.source(edge)];
1420 const Graph& _graph;
1421 typename Graph::template NodeMap<bool> _part;
1425 template <typename Graph, typename PartMap>
1426 class BipartitePartitionsVisitor : public BfsVisitor<Graph> {
1428 typedef typename Graph::Edge Edge;
1429 typedef typename Graph::Node Node;
1431 BipartitePartitionsVisitor(const Graph& graph,
1432 PartMap& part, bool& bipartite)
1433 : _graph(graph), _part(part), _bipartite(bipartite) {}
1435 void start(const Node& node) {
1436 _part.set(node, true);
1438 void discover(const Edge& edge) {
1439 _part.set(_graph.target(edge), !_part[_graph.source(edge)]);
1441 void examine(const Edge& edge) {
1442 _bipartite = _bipartite &&
1443 _part[_graph.target(edge)] != _part[_graph.source(edge)];
1448 const Graph& _graph;
1454 /// \ingroup graph_prop
1456 /// \brief Check if the given undirected graph is bipartite or not
1458 /// The function checks if the given undirected \c graph graph is bipartite
1459 /// or not. The \ref Bfs algorithm is used to calculate the result.
1460 /// \param graph The undirected graph.
1461 /// \return %True if \c graph is bipartite, %false otherwise.
1462 /// \sa bipartitePartitions
1464 /// \author Balazs Attila Mihaly
1465 template<typename UGraph>
1466 inline bool bipartite(const UGraph &graph){
1467 using namespace _topology_bits;
1469 checkConcept<concepts::UGraph, UGraph>();
1471 typedef typename UGraph::NodeIt NodeIt;
1472 typedef typename UGraph::EdgeIt EdgeIt;
1474 bool bipartite = true;
1476 BipartiteVisitor<UGraph>
1477 visitor(graph, bipartite);
1478 BfsVisit<UGraph, BipartiteVisitor<UGraph> >
1479 bfs(graph, visitor);
1481 for(NodeIt it(graph); it != INVALID; ++it) {
1482 if(!bfs.reached(it)){
1484 while (!bfs.emptyQueue()) {
1485 bfs.processNextNode();
1486 if (!bipartite) return false;
1493 /// \ingroup graph_prop
1495 /// \brief Check if the given undirected graph is bipartite or not
1497 /// The function checks if the given undirected graph is bipartite
1498 /// or not. The \ref Bfs algorithm is used to calculate the result.
1499 /// During the execution, the \c partMap will be set as the two
1500 /// partitions of the graph.
1501 /// \param graph The undirected graph.
1502 /// \retval partMap A writable bool map of nodes. It will be set as the
1503 /// two partitions of the graph.
1504 /// \return %True if \c graph is bipartite, %false otherwise.
1506 /// \author Balazs Attila Mihaly
1508 /// \image html bipartite_partitions.png
1509 /// \image latex bipartite_partitions.eps "Bipartite partititions" width=\textwidth
1510 template<typename UGraph, typename NodeMap>
1511 inline bool bipartitePartitions(const UGraph &graph, NodeMap &partMap){
1512 using namespace _topology_bits;
1514 checkConcept<concepts::UGraph, UGraph>();
1516 typedef typename UGraph::Node Node;
1517 typedef typename UGraph::NodeIt NodeIt;
1518 typedef typename UGraph::EdgeIt EdgeIt;
1520 bool bipartite = true;
1522 BipartitePartitionsVisitor<UGraph, NodeMap>
1523 visitor(graph, partMap, bipartite);
1524 BfsVisit<UGraph, BipartitePartitionsVisitor<UGraph, NodeMap> >
1525 bfs(graph, visitor);
1527 for(NodeIt it(graph); it != INVALID; ++it) {
1528 if(!bfs.reached(it)){
1530 while (!bfs.emptyQueue()) {
1531 bfs.processNextNode();
1532 if (!bipartite) return false;
1539 /// \brief Returns true when there is not loop edge in the graph.
1541 /// Returns true when there is not loop edge in the graph.
1542 template <typename Graph>
1543 bool loopFree(const Graph& graph) {
1544 for (typename Graph::EdgeIt it(graph); it != INVALID; ++it) {
1545 if (graph.source(it) == graph.target(it)) return false;
1550 /// \brief Returns true when there is not parallel edges in the graph.
1552 /// Returns true when there is not parallel edges in the graph.
1553 template <typename Graph>
1554 bool parallelFree(const Graph& graph) {
1555 typename Graph::template NodeMap<bool> reached(graph, false);
1556 for (typename Graph::NodeIt n(graph); n != INVALID; ++n) {
1557 for (typename Graph::OutEdgeIt e(graph, n); e != INVALID; ++e) {
1558 if (reached[graph.target(e)]) return false;
1559 reached.set(graph.target(e), true);
1561 for (typename Graph::OutEdgeIt e(graph, n); e != INVALID; ++e) {
1562 reached.set(graph.target(e), false);
1568 /// \brief Returns true when there is not loop edge and parallel
1569 /// edges in the graph.
1571 /// Returns true when there is not loop edge and parallel edges in
1573 template <typename Graph>
1574 bool simpleGraph(const Graph& graph) {
1575 typename Graph::template NodeMap<bool> reached(graph, false);
1576 for (typename Graph::NodeIt n(graph); n != INVALID; ++n) {
1577 reached.set(n, true);
1578 for (typename Graph::OutEdgeIt e(graph, n); e != INVALID; ++e) {
1579 if (reached[graph.target(e)]) return false;
1580 reached.set(graph.target(e), true);
1582 for (typename Graph::OutEdgeIt e(graph, n); e != INVALID; ++e) {
1583 reached.set(graph.target(e), false);
1585 reached.set(n, false);
1592 #endif //LEMON_TOPOLOGY_H