22 #include <lemon/graph_utils.h> |
22 #include <lemon/graph_utils.h> |
23 #include <lemon/graph_adaptor.h> |
23 #include <lemon/graph_adaptor.h> |
24 #include <lemon/maps.h> |
24 #include <lemon/maps.h> |
25 |
25 |
26 #include <lemon/concept/graph.h> |
26 #include <lemon/concept/graph.h> |
27 #include <lemon/concept/undir_graph.h> |
27 #include <lemon/concept/ugraph.h> |
28 #include <lemon/concept_check.h> |
28 #include <lemon/concept_check.h> |
29 |
29 |
30 #include <lemon/bin_heap.h> |
30 #include <lemon/bin_heap.h> |
31 #include <lemon/linear_heap.h> |
31 #include <lemon/linear_heap.h> |
32 |
32 |
47 /// |
47 /// |
48 /// Check that the given undirected graph connected. |
48 /// Check that the given undirected graph connected. |
49 /// \param graph The undirected graph. |
49 /// \param graph The undirected graph. |
50 /// \return %True when there is path between any two nodes in the graph. |
50 /// \return %True when there is path between any two nodes in the graph. |
51 /// \note By definition, the empty graph is connected. |
51 /// \note By definition, the empty graph is connected. |
52 template <typename UndirGraph> |
52 template <typename UGraph> |
53 bool connected(const UndirGraph& graph) { |
53 bool connected(const UGraph& graph) { |
54 checkConcept<concept::UndirGraph, UndirGraph>(); |
54 checkConcept<concept::UGraph, UGraph>(); |
55 typedef typename UndirGraph::NodeIt NodeIt; |
55 typedef typename UGraph::NodeIt NodeIt; |
56 if (NodeIt(graph) == INVALID) return true; |
56 if (NodeIt(graph) == INVALID) return true; |
57 Dfs<UndirGraph> dfs(graph); |
57 Dfs<UGraph> dfs(graph); |
58 dfs.run(NodeIt(graph)); |
58 dfs.run(NodeIt(graph)); |
59 for (NodeIt it(graph); it != INVALID; ++it) { |
59 for (NodeIt it(graph); it != INVALID; ++it) { |
60 if (!dfs.reached(it)) { |
60 if (!dfs.reached(it)) { |
61 return false; |
61 return false; |
62 } |
62 } |
72 /// |
72 /// |
73 /// \param graph The graph. It should be undirected. |
73 /// \param graph The graph. It should be undirected. |
74 /// \return The number of components |
74 /// \return The number of components |
75 /// \note By definition, the empty graph consists |
75 /// \note By definition, the empty graph consists |
76 /// of zero connected components. |
76 /// of zero connected components. |
77 template <typename UndirGraph> |
77 template <typename UGraph> |
78 int countConnectedComponents(const UndirGraph &graph) { |
78 int countConnectedComponents(const UGraph &graph) { |
79 checkConcept<concept::UndirGraph, UndirGraph>(); |
79 checkConcept<concept::UGraph, UGraph>(); |
80 typedef typename UndirGraph::Node Node; |
80 typedef typename UGraph::Node Node; |
81 typedef typename UndirGraph::Edge Edge; |
81 typedef typename UGraph::Edge Edge; |
82 |
82 |
83 typedef NullMap<Node, Edge> PredMap; |
83 typedef NullMap<Node, Edge> PredMap; |
84 typedef NullMap<Node, int> DistMap; |
84 typedef NullMap<Node, int> DistMap; |
85 |
85 |
86 int compNum = 0; |
86 int compNum = 0; |
87 typename Bfs<UndirGraph>:: |
87 typename Bfs<UGraph>:: |
88 template DefPredMap<PredMap>:: |
88 template DefPredMap<PredMap>:: |
89 template DefDistMap<DistMap>:: |
89 template DefDistMap<DistMap>:: |
90 Create bfs(graph); |
90 Create bfs(graph); |
91 |
91 |
92 PredMap predMap; |
92 PredMap predMap; |
120 /// the number of the connected components minus one. Each values of the map |
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 |
121 /// will be set exactly once, the values of a certain component will be |
122 /// set continuously. |
122 /// set continuously. |
123 /// \return The number of components |
123 /// \return The number of components |
124 /// |
124 /// |
125 template <class UndirGraph, class NodeMap> |
125 template <class UGraph, class NodeMap> |
126 int connectedComponents(const UndirGraph &graph, NodeMap &compMap) { |
126 int connectedComponents(const UGraph &graph, NodeMap &compMap) { |
127 checkConcept<concept::UndirGraph, UndirGraph>(); |
127 checkConcept<concept::UGraph, UGraph>(); |
128 typedef typename UndirGraph::Node Node; |
128 typedef typename UGraph::Node Node; |
129 typedef typename UndirGraph::Edge Edge; |
129 typedef typename UGraph::Edge Edge; |
130 checkConcept<concept::WriteMap<Node, int>, NodeMap>(); |
130 checkConcept<concept::WriteMap<Node, int>, NodeMap>(); |
131 |
131 |
132 typedef NullMap<Node, Edge> PredMap; |
132 typedef NullMap<Node, Edge> PredMap; |
133 typedef NullMap<Node, int> DistMap; |
133 typedef NullMap<Node, int> DistMap; |
134 |
134 |
135 int compNum = 0; |
135 int compNum = 0; |
136 typename Bfs<UndirGraph>:: |
136 typename Bfs<UGraph>:: |
137 template DefPredMap<PredMap>:: |
137 template DefPredMap<PredMap>:: |
138 template DefDistMap<DistMap>:: |
138 template DefDistMap<DistMap>:: |
139 Create bfs(graph); |
139 Create bfs(graph); |
140 |
140 |
141 PredMap predMap; |
141 PredMap predMap; |
143 |
143 |
144 DistMap distMap; |
144 DistMap distMap; |
145 bfs.distMap(distMap); |
145 bfs.distMap(distMap); |
146 |
146 |
147 bfs.init(); |
147 bfs.init(); |
148 for(typename UndirGraph::NodeIt n(graph); n != INVALID; ++n) { |
148 for(typename UGraph::NodeIt n(graph); n != INVALID; ++n) { |
149 if(!bfs.reached(n)) { |
149 if(!bfs.reached(n)) { |
150 bfs.addSource(n); |
150 bfs.addSource(n); |
151 while (!bfs.emptyQueue()) { |
151 while (!bfs.emptyQueue()) { |
152 compMap.set(bfs.nextNode(), compNum); |
152 compMap.set(bfs.nextNode(), compNum); |
153 bfs.processNextNode(); |
153 bfs.processNextNode(); |
482 template <typename Graph> |
482 template <typename Graph> |
483 class CountBiNodeConnectedComponentsVisitor : public DfsVisitor<Graph> { |
483 class CountBiNodeConnectedComponentsVisitor : public DfsVisitor<Graph> { |
484 public: |
484 public: |
485 typedef typename Graph::Node Node; |
485 typedef typename Graph::Node Node; |
486 typedef typename Graph::Edge Edge; |
486 typedef typename Graph::Edge Edge; |
487 typedef typename Graph::UndirEdge UndirEdge; |
487 typedef typename Graph::UEdge UEdge; |
488 |
488 |
489 CountBiNodeConnectedComponentsVisitor(const Graph& graph, int &compNum) |
489 CountBiNodeConnectedComponentsVisitor(const Graph& graph, int &compNum) |
490 : _graph(graph), _compNum(compNum), |
490 : _graph(graph), _compNum(compNum), |
491 _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {} |
491 _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {} |
492 |
492 |
540 template <typename Graph, typename EdgeMap> |
540 template <typename Graph, typename EdgeMap> |
541 class BiNodeConnectedComponentsVisitor : public DfsVisitor<Graph> { |
541 class BiNodeConnectedComponentsVisitor : public DfsVisitor<Graph> { |
542 public: |
542 public: |
543 typedef typename Graph::Node Node; |
543 typedef typename Graph::Node Node; |
544 typedef typename Graph::Edge Edge; |
544 typedef typename Graph::Edge Edge; |
545 typedef typename Graph::UndirEdge UndirEdge; |
545 typedef typename Graph::UEdge UEdge; |
546 |
546 |
547 BiNodeConnectedComponentsVisitor(const Graph& graph, |
547 BiNodeConnectedComponentsVisitor(const Graph& graph, |
548 EdgeMap& compMap, int &compNum) |
548 EdgeMap& compMap, int &compNum) |
549 : _graph(graph), _compMap(compMap), _compNum(compNum), |
549 : _graph(graph), _compMap(compMap), _compNum(compNum), |
550 _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {} |
550 _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {} |
610 int& _compNum; |
610 int& _compNum; |
611 |
611 |
612 typename Graph::template NodeMap<int> _numMap; |
612 typename Graph::template NodeMap<int> _numMap; |
613 typename Graph::template NodeMap<int> _retMap; |
613 typename Graph::template NodeMap<int> _retMap; |
614 typename Graph::template NodeMap<Edge> _predMap; |
614 typename Graph::template NodeMap<Edge> _predMap; |
615 std::stack<UndirEdge> _edgeStack; |
615 std::stack<UEdge> _edgeStack; |
616 int _num; |
616 int _num; |
617 }; |
617 }; |
618 |
618 |
619 |
619 |
620 template <typename Graph, typename NodeMap> |
620 template <typename Graph, typename NodeMap> |
621 class BiNodeConnectedCutNodesVisitor : public DfsVisitor<Graph> { |
621 class BiNodeConnectedCutNodesVisitor : public DfsVisitor<Graph> { |
622 public: |
622 public: |
623 typedef typename Graph::Node Node; |
623 typedef typename Graph::Node Node; |
624 typedef typename Graph::Edge Edge; |
624 typedef typename Graph::Edge Edge; |
625 typedef typename Graph::UndirEdge UndirEdge; |
625 typedef typename Graph::UEdge UEdge; |
626 |
626 |
627 BiNodeConnectedCutNodesVisitor(const Graph& graph, NodeMap& cutMap, |
627 BiNodeConnectedCutNodesVisitor(const Graph& graph, NodeMap& cutMap, |
628 int& cutNum) |
628 int& cutNum) |
629 : _graph(graph), _cutMap(cutMap), _cutNum(cutNum), |
629 : _graph(graph), _cutMap(cutMap), _cutNum(cutNum), |
630 _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {} |
630 _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {} |
686 int& _cutNum; |
686 int& _cutNum; |
687 |
687 |
688 typename Graph::template NodeMap<int> _numMap; |
688 typename Graph::template NodeMap<int> _numMap; |
689 typename Graph::template NodeMap<int> _retMap; |
689 typename Graph::template NodeMap<int> _retMap; |
690 typename Graph::template NodeMap<Node> _predMap; |
690 typename Graph::template NodeMap<Node> _predMap; |
691 std::stack<UndirEdge> _edgeStack; |
691 std::stack<UEdge> _edgeStack; |
692 int _num; |
692 int _num; |
693 bool rootCut; |
693 bool rootCut; |
694 }; |
694 }; |
695 |
695 |
696 } |
696 } |
697 |
697 |
698 template <typename UndirGraph> |
698 template <typename UGraph> |
699 int countBiNodeConnectedComponents(const UndirGraph& graph); |
699 int countBiNodeConnectedComponents(const UGraph& graph); |
700 |
700 |
701 /// \ingroup topology |
701 /// \ingroup topology |
702 /// |
702 /// |
703 /// \brief Checks the graph is bi-node-connected. |
703 /// \brief Checks the graph is bi-node-connected. |
704 /// |
704 /// |
707 /// on same circle. |
707 /// on same circle. |
708 /// |
708 /// |
709 /// \param graph The graph. |
709 /// \param graph The graph. |
710 /// \return %True when the graph bi-node-connected. |
710 /// \return %True when the graph bi-node-connected. |
711 /// \todo Make it faster. |
711 /// \todo Make it faster. |
712 template <typename UndirGraph> |
712 template <typename UGraph> |
713 bool biNodeConnected(const UndirGraph& graph) { |
713 bool biNodeConnected(const UGraph& graph) { |
714 return countBiNodeConnectedComponents(graph) == 1; |
714 return countBiNodeConnectedComponents(graph) == 1; |
715 } |
715 } |
716 |
716 |
717 /// \ingroup topology |
717 /// \ingroup topology |
718 /// |
718 /// |
723 /// relation on the undirected edges. Two undirected edge is in relationship |
723 /// relation on the undirected edges. Two undirected edge is in relationship |
724 /// when they are on same circle. |
724 /// when they are on same circle. |
725 /// |
725 /// |
726 /// \param graph The graph. |
726 /// \param graph The graph. |
727 /// \return The number of components. |
727 /// \return The number of components. |
728 template <typename UndirGraph> |
728 template <typename UGraph> |
729 int countBiNodeConnectedComponents(const UndirGraph& graph) { |
729 int countBiNodeConnectedComponents(const UGraph& graph) { |
730 checkConcept<concept::UndirGraph, UndirGraph>(); |
730 checkConcept<concept::UGraph, UGraph>(); |
731 typedef typename UndirGraph::NodeIt NodeIt; |
731 typedef typename UGraph::NodeIt NodeIt; |
732 |
732 |
733 using namespace _topology_bits; |
733 using namespace _topology_bits; |
734 |
734 |
735 typedef CountBiNodeConnectedComponentsVisitor<UndirGraph> Visitor; |
735 typedef CountBiNodeConnectedComponentsVisitor<UGraph> Visitor; |
736 |
736 |
737 int compNum = 0; |
737 int compNum = 0; |
738 Visitor visitor(graph, compNum); |
738 Visitor visitor(graph, compNum); |
739 |
739 |
740 DfsVisit<UndirGraph, Visitor> dfs(graph, visitor); |
740 DfsVisit<UGraph, Visitor> dfs(graph, visitor); |
741 dfs.init(); |
741 dfs.init(); |
742 |
742 |
743 for (NodeIt it(graph); it != INVALID; ++it) { |
743 for (NodeIt it(graph); it != INVALID; ++it) { |
744 if (!dfs.reached(it)) { |
744 if (!dfs.reached(it)) { |
745 dfs.addSource(it); |
745 dfs.addSource(it); |
760 /// |
760 /// |
761 /// \image html node_biconnected_components.png |
761 /// \image html node_biconnected_components.png |
762 /// \image latex node_biconnected_components.eps "bi-node-connected components" width=\textwidth |
762 /// \image latex node_biconnected_components.eps "bi-node-connected components" width=\textwidth |
763 /// |
763 /// |
764 /// \param graph The graph. |
764 /// \param graph The graph. |
765 /// \retval compMap A writable undir edge map. The values will be set from 0 |
765 /// \retval compMap A writable uedge map. The values will be set from 0 |
766 /// to the number of the biconnected components minus one. Each values |
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 |
767 /// of the map will be set exactly once, the values of a certain component |
768 /// will be set continuously. |
768 /// will be set continuously. |
769 /// \return The number of components. |
769 /// \return The number of components. |
770 /// |
770 /// |
771 template <typename UndirGraph, typename UndirEdgeMap> |
771 template <typename UGraph, typename UEdgeMap> |
772 int biNodeConnectedComponents(const UndirGraph& graph, |
772 int biNodeConnectedComponents(const UGraph& graph, |
773 UndirEdgeMap& compMap) { |
773 UEdgeMap& compMap) { |
774 checkConcept<concept::UndirGraph, UndirGraph>(); |
774 checkConcept<concept::UGraph, UGraph>(); |
775 typedef typename UndirGraph::NodeIt NodeIt; |
775 typedef typename UGraph::NodeIt NodeIt; |
776 typedef typename UndirGraph::UndirEdge UndirEdge; |
776 typedef typename UGraph::UEdge UEdge; |
777 checkConcept<concept::WriteMap<UndirEdge, int>, UndirEdgeMap>(); |
777 checkConcept<concept::WriteMap<UEdge, int>, UEdgeMap>(); |
778 |
778 |
779 using namespace _topology_bits; |
779 using namespace _topology_bits; |
780 |
780 |
781 typedef BiNodeConnectedComponentsVisitor<UndirGraph, UndirEdgeMap> Visitor; |
781 typedef BiNodeConnectedComponentsVisitor<UGraph, UEdgeMap> Visitor; |
782 |
782 |
783 int compNum = 0; |
783 int compNum = 0; |
784 Visitor visitor(graph, compMap, compNum); |
784 Visitor visitor(graph, compMap, compNum); |
785 |
785 |
786 DfsVisit<UndirGraph, Visitor> dfs(graph, visitor); |
786 DfsVisit<UGraph, Visitor> dfs(graph, visitor); |
787 dfs.init(); |
787 dfs.init(); |
788 |
788 |
789 for (NodeIt it(graph); it != INVALID; ++it) { |
789 for (NodeIt it(graph); it != INVALID; ++it) { |
790 if (!dfs.reached(it)) { |
790 if (!dfs.reached(it)) { |
791 dfs.addSource(it); |
791 dfs.addSource(it); |
807 /// |
807 /// |
808 /// \param graph The graph. |
808 /// \param graph The graph. |
809 /// \retval cutMap A writable edge map. The values will be set true when |
809 /// \retval cutMap A writable edge map. The values will be set true when |
810 /// the node separate two or more components. |
810 /// the node separate two or more components. |
811 /// \return The number of the cut nodes. |
811 /// \return The number of the cut nodes. |
812 template <typename UndirGraph, typename NodeMap> |
812 template <typename UGraph, typename NodeMap> |
813 int biNodeConnectedCutNodes(const UndirGraph& graph, NodeMap& cutMap) { |
813 int biNodeConnectedCutNodes(const UGraph& graph, NodeMap& cutMap) { |
814 checkConcept<concept::UndirGraph, UndirGraph>(); |
814 checkConcept<concept::UGraph, UGraph>(); |
815 typedef typename UndirGraph::Node Node; |
815 typedef typename UGraph::Node Node; |
816 typedef typename UndirGraph::NodeIt NodeIt; |
816 typedef typename UGraph::NodeIt NodeIt; |
817 checkConcept<concept::WriteMap<Node, bool>, NodeMap>(); |
817 checkConcept<concept::WriteMap<Node, bool>, NodeMap>(); |
818 |
818 |
819 using namespace _topology_bits; |
819 using namespace _topology_bits; |
820 |
820 |
821 typedef BiNodeConnectedCutNodesVisitor<UndirGraph, NodeMap> Visitor; |
821 typedef BiNodeConnectedCutNodesVisitor<UGraph, NodeMap> Visitor; |
822 |
822 |
823 int cutNum = 0; |
823 int cutNum = 0; |
824 Visitor visitor(graph, cutMap, cutNum); |
824 Visitor visitor(graph, cutMap, cutNum); |
825 |
825 |
826 DfsVisit<UndirGraph, Visitor> dfs(graph, visitor); |
826 DfsVisit<UGraph, Visitor> dfs(graph, visitor); |
827 dfs.init(); |
827 dfs.init(); |
828 |
828 |
829 for (NodeIt it(graph); it != INVALID; ++it) { |
829 for (NodeIt it(graph); it != INVALID; ++it) { |
830 if (!dfs.reached(it)) { |
830 if (!dfs.reached(it)) { |
831 dfs.addSource(it); |
831 dfs.addSource(it); |
840 template <typename Graph> |
840 template <typename Graph> |
841 class CountBiEdgeConnectedComponentsVisitor : public DfsVisitor<Graph> { |
841 class CountBiEdgeConnectedComponentsVisitor : public DfsVisitor<Graph> { |
842 public: |
842 public: |
843 typedef typename Graph::Node Node; |
843 typedef typename Graph::Node Node; |
844 typedef typename Graph::Edge Edge; |
844 typedef typename Graph::Edge Edge; |
845 typedef typename Graph::UndirEdge UndirEdge; |
845 typedef typename Graph::UEdge UEdge; |
846 |
846 |
847 CountBiEdgeConnectedComponentsVisitor(const Graph& graph, int &compNum) |
847 CountBiEdgeConnectedComponentsVisitor(const Graph& graph, int &compNum) |
848 : _graph(graph), _compNum(compNum), |
848 : _graph(graph), _compNum(compNum), |
849 _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {} |
849 _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {} |
850 |
850 |
896 template <typename Graph, typename NodeMap> |
896 template <typename Graph, typename NodeMap> |
897 class BiEdgeConnectedComponentsVisitor : public DfsVisitor<Graph> { |
897 class BiEdgeConnectedComponentsVisitor : public DfsVisitor<Graph> { |
898 public: |
898 public: |
899 typedef typename Graph::Node Node; |
899 typedef typename Graph::Node Node; |
900 typedef typename Graph::Edge Edge; |
900 typedef typename Graph::Edge Edge; |
901 typedef typename Graph::UndirEdge UndirEdge; |
901 typedef typename Graph::UEdge UEdge; |
902 |
902 |
903 BiEdgeConnectedComponentsVisitor(const Graph& graph, |
903 BiEdgeConnectedComponentsVisitor(const Graph& graph, |
904 NodeMap& compMap, int &compNum) |
904 NodeMap& compMap, int &compNum) |
905 : _graph(graph), _compMap(compMap), _compNum(compNum), |
905 : _graph(graph), _compMap(compMap), _compNum(compNum), |
906 _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {} |
906 _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {} |
963 template <typename Graph, typename EdgeMap> |
963 template <typename Graph, typename EdgeMap> |
964 class BiEdgeConnectedCutEdgesVisitor : public DfsVisitor<Graph> { |
964 class BiEdgeConnectedCutEdgesVisitor : public DfsVisitor<Graph> { |
965 public: |
965 public: |
966 typedef typename Graph::Node Node; |
966 typedef typename Graph::Node Node; |
967 typedef typename Graph::Edge Edge; |
967 typedef typename Graph::Edge Edge; |
968 typedef typename Graph::UndirEdge UndirEdge; |
968 typedef typename Graph::UEdge UEdge; |
969 |
969 |
970 BiEdgeConnectedCutEdgesVisitor(const Graph& graph, |
970 BiEdgeConnectedCutEdgesVisitor(const Graph& graph, |
971 EdgeMap& cutMap, int &cutNum) |
971 EdgeMap& cutMap, int &cutNum) |
972 : _graph(graph), _cutMap(cutMap), _cutNum(cutNum), |
972 : _graph(graph), _cutMap(cutMap), _cutNum(cutNum), |
973 _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {} |
973 _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {} |
1034 /// edge-disjoint paths. |
1034 /// edge-disjoint paths. |
1035 /// |
1035 /// |
1036 /// \param graph The undirected graph. |
1036 /// \param graph The undirected graph. |
1037 /// \return The number of components. |
1037 /// \return The number of components. |
1038 /// \todo Make it faster. |
1038 /// \todo Make it faster. |
1039 template <typename UndirGraph> |
1039 template <typename UGraph> |
1040 bool biEdgeConnected(const UndirGraph& graph) { |
1040 bool biEdgeConnected(const UGraph& graph) { |
1041 return countBiEdgeConnectedComponents(graph) == 1; |
1041 return countBiEdgeConnectedComponents(graph) == 1; |
1042 } |
1042 } |
1043 |
1043 |
1044 /// \ingroup topology |
1044 /// \ingroup topology |
1045 /// |
1045 /// |
1050 /// relation on the nodes. Two nodes are in relationship when they are |
1050 /// relation on the nodes. Two nodes are in relationship when they are |
1051 /// connected with at least two edge-disjoint paths. |
1051 /// connected with at least two edge-disjoint paths. |
1052 /// |
1052 /// |
1053 /// \param graph The undirected graph. |
1053 /// \param graph The undirected graph. |
1054 /// \return The number of components. |
1054 /// \return The number of components. |
1055 template <typename UndirGraph> |
1055 template <typename UGraph> |
1056 int countBiEdgeConnectedComponents(const UndirGraph& graph) { |
1056 int countBiEdgeConnectedComponents(const UGraph& graph) { |
1057 checkConcept<concept::UndirGraph, UndirGraph>(); |
1057 checkConcept<concept::UGraph, UGraph>(); |
1058 typedef typename UndirGraph::NodeIt NodeIt; |
1058 typedef typename UGraph::NodeIt NodeIt; |
1059 |
1059 |
1060 using namespace _topology_bits; |
1060 using namespace _topology_bits; |
1061 |
1061 |
1062 typedef CountBiEdgeConnectedComponentsVisitor<UndirGraph> Visitor; |
1062 typedef CountBiEdgeConnectedComponentsVisitor<UGraph> Visitor; |
1063 |
1063 |
1064 int compNum = 0; |
1064 int compNum = 0; |
1065 Visitor visitor(graph, compNum); |
1065 Visitor visitor(graph, compNum); |
1066 |
1066 |
1067 DfsVisit<UndirGraph, Visitor> dfs(graph, visitor); |
1067 DfsVisit<UGraph, Visitor> dfs(graph, visitor); |
1068 dfs.init(); |
1068 dfs.init(); |
1069 |
1069 |
1070 for (NodeIt it(graph); it != INVALID; ++it) { |
1070 for (NodeIt it(graph); it != INVALID; ++it) { |
1071 if (!dfs.reached(it)) { |
1071 if (!dfs.reached(it)) { |
1072 dfs.addSource(it); |
1072 dfs.addSource(it); |
1093 /// the number of the biconnected components minus one. Each values |
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 |
1094 /// of the map will be set exactly once, the values of a certain component |
1095 /// will be set continuously. |
1095 /// will be set continuously. |
1096 /// \return The number of components. |
1096 /// \return The number of components. |
1097 /// |
1097 /// |
1098 template <typename UndirGraph, typename NodeMap> |
1098 template <typename UGraph, typename NodeMap> |
1099 int biEdgeConnectedComponents(const UndirGraph& graph, NodeMap& compMap) { |
1099 int biEdgeConnectedComponents(const UGraph& graph, NodeMap& compMap) { |
1100 checkConcept<concept::UndirGraph, UndirGraph>(); |
1100 checkConcept<concept::UGraph, UGraph>(); |
1101 typedef typename UndirGraph::NodeIt NodeIt; |
1101 typedef typename UGraph::NodeIt NodeIt; |
1102 typedef typename UndirGraph::Node Node; |
1102 typedef typename UGraph::Node Node; |
1103 checkConcept<concept::WriteMap<Node, int>, NodeMap>(); |
1103 checkConcept<concept::WriteMap<Node, int>, NodeMap>(); |
1104 |
1104 |
1105 using namespace _topology_bits; |
1105 using namespace _topology_bits; |
1106 |
1106 |
1107 typedef BiEdgeConnectedComponentsVisitor<UndirGraph, NodeMap> Visitor; |
1107 typedef BiEdgeConnectedComponentsVisitor<UGraph, NodeMap> Visitor; |
1108 |
1108 |
1109 int compNum = 0; |
1109 int compNum = 0; |
1110 Visitor visitor(graph, compMap, compNum); |
1110 Visitor visitor(graph, compMap, compNum); |
1111 |
1111 |
1112 DfsVisit<UndirGraph, Visitor> dfs(graph, visitor); |
1112 DfsVisit<UGraph, Visitor> dfs(graph, visitor); |
1113 dfs.init(); |
1113 dfs.init(); |
1114 |
1114 |
1115 for (NodeIt it(graph); it != INVALID; ++it) { |
1115 for (NodeIt it(graph); it != INVALID; ++it) { |
1116 if (!dfs.reached(it)) { |
1116 if (!dfs.reached(it)) { |
1117 dfs.addSource(it); |
1117 dfs.addSource(it); |
1134 /// |
1134 /// |
1135 /// \param graph The graph. |
1135 /// \param graph The graph. |
1136 /// \retval cutMap A writable node map. The values will be set true when the |
1136 /// \retval cutMap A writable node map. The values will be set true when the |
1137 /// edge is a cut edge. |
1137 /// edge is a cut edge. |
1138 /// \return The number of cut edges. |
1138 /// \return The number of cut edges. |
1139 template <typename UndirGraph, typename UndirEdgeMap> |
1139 template <typename UGraph, typename UEdgeMap> |
1140 int biEdgeConnectedCutEdges(const UndirGraph& graph, UndirEdgeMap& cutMap) { |
1140 int biEdgeConnectedCutEdges(const UGraph& graph, UEdgeMap& cutMap) { |
1141 checkConcept<concept::UndirGraph, UndirGraph>(); |
1141 checkConcept<concept::UGraph, UGraph>(); |
1142 typedef typename UndirGraph::NodeIt NodeIt; |
1142 typedef typename UGraph::NodeIt NodeIt; |
1143 typedef typename UndirGraph::UndirEdge UndirEdge; |
1143 typedef typename UGraph::UEdge UEdge; |
1144 checkConcept<concept::WriteMap<UndirEdge, bool>, UndirEdgeMap>(); |
1144 checkConcept<concept::WriteMap<UEdge, bool>, UEdgeMap>(); |
1145 |
1145 |
1146 using namespace _topology_bits; |
1146 using namespace _topology_bits; |
1147 |
1147 |
1148 typedef BiEdgeConnectedCutEdgesVisitor<UndirGraph, UndirEdgeMap> Visitor; |
1148 typedef BiEdgeConnectedCutEdgesVisitor<UGraph, UEdgeMap> Visitor; |
1149 |
1149 |
1150 int cutNum = 0; |
1150 int cutNum = 0; |
1151 Visitor visitor(graph, cutMap, cutNum); |
1151 Visitor visitor(graph, cutMap, cutNum); |
1152 |
1152 |
1153 DfsVisit<UndirGraph, Visitor> dfs(graph, visitor); |
1153 DfsVisit<UGraph, Visitor> dfs(graph, visitor); |
1154 dfs.init(); |
1154 dfs.init(); |
1155 |
1155 |
1156 for (NodeIt it(graph); it != INVALID; ++it) { |
1156 for (NodeIt it(graph); it != INVALID; ++it) { |
1157 if (!dfs.reached(it)) { |
1157 if (!dfs.reached(it)) { |
1158 dfs.addSource(it); |
1158 dfs.addSource(it); |
1324 /// |
1324 /// |
1325 /// Check that the given undirected graph acyclic. |
1325 /// Check that the given undirected graph acyclic. |
1326 /// \param graph The undirected graph. |
1326 /// \param graph The undirected graph. |
1327 /// \return %True when there is no circle in the graph. |
1327 /// \return %True when there is no circle in the graph. |
1328 /// \see dag |
1328 /// \see dag |
1329 template <typename UndirGraph> |
1329 template <typename UGraph> |
1330 bool acyclic(const UndirGraph& graph) { |
1330 bool acyclic(const UGraph& graph) { |
1331 checkConcept<concept::UndirGraph, UndirGraph>(); |
1331 checkConcept<concept::UGraph, UGraph>(); |
1332 typedef typename UndirGraph::Node Node; |
1332 typedef typename UGraph::Node Node; |
1333 typedef typename UndirGraph::NodeIt NodeIt; |
1333 typedef typename UGraph::NodeIt NodeIt; |
1334 typedef typename UndirGraph::Edge Edge; |
1334 typedef typename UGraph::Edge Edge; |
1335 Dfs<UndirGraph> dfs(graph); |
1335 Dfs<UGraph> dfs(graph); |
1336 dfs.init(); |
1336 dfs.init(); |
1337 for (NodeIt it(graph); it != INVALID; ++it) { |
1337 for (NodeIt it(graph); it != INVALID; ++it) { |
1338 if (!dfs.reached(it)) { |
1338 if (!dfs.reached(it)) { |
1339 dfs.addSource(it); |
1339 dfs.addSource(it); |
1340 while (!dfs.emptyQueue()) { |
1340 while (!dfs.emptyQueue()) { |
1357 /// \brief Check that the given undirected graph is tree. |
1357 /// \brief Check that the given undirected graph is tree. |
1358 /// |
1358 /// |
1359 /// Check that the given undirected graph is tree. |
1359 /// Check that the given undirected graph is tree. |
1360 /// \param graph The undirected graph. |
1360 /// \param graph The undirected graph. |
1361 /// \return %True when the graph is acyclic and connected. |
1361 /// \return %True when the graph is acyclic and connected. |
1362 template <typename UndirGraph> |
1362 template <typename UGraph> |
1363 bool tree(const UndirGraph& graph) { |
1363 bool tree(const UGraph& graph) { |
1364 checkConcept<concept::UndirGraph, UndirGraph>(); |
1364 checkConcept<concept::UGraph, UGraph>(); |
1365 typedef typename UndirGraph::Node Node; |
1365 typedef typename UGraph::Node Node; |
1366 typedef typename UndirGraph::NodeIt NodeIt; |
1366 typedef typename UGraph::NodeIt NodeIt; |
1367 typedef typename UndirGraph::Edge Edge; |
1367 typedef typename UGraph::Edge Edge; |
1368 Dfs<UndirGraph> dfs(graph); |
1368 Dfs<UGraph> dfs(graph); |
1369 dfs.init(); |
1369 dfs.init(); |
1370 dfs.addSource(NodeIt(graph)); |
1370 dfs.addSource(NodeIt(graph)); |
1371 while (!dfs.emptyQueue()) { |
1371 while (!dfs.emptyQueue()) { |
1372 Edge edge = dfs.nextEdge(); |
1372 Edge edge = dfs.nextEdge(); |
1373 Node source = graph.source(edge); |
1373 Node source = graph.source(edge); |
1395 /// \param graph The undirected graph. |
1395 /// \param graph The undirected graph. |
1396 /// \return %True if \c graph is bipartite, %false otherwise. |
1396 /// \return %True if \c graph is bipartite, %false otherwise. |
1397 /// \sa bipartitePartitions |
1397 /// \sa bipartitePartitions |
1398 /// |
1398 /// |
1399 /// \author Balazs Attila Mihaly |
1399 /// \author Balazs Attila Mihaly |
1400 template<typename UndirGraph> |
1400 template<typename UGraph> |
1401 inline bool bipartite(const UndirGraph &graph){ |
1401 inline bool bipartite(const UGraph &graph){ |
1402 checkConcept<concept::UndirGraph, UndirGraph>(); |
1402 checkConcept<concept::UGraph, UGraph>(); |
1403 |
1403 |
1404 typedef typename UndirGraph::NodeIt NodeIt; |
1404 typedef typename UGraph::NodeIt NodeIt; |
1405 typedef typename UndirGraph::EdgeIt EdgeIt; |
1405 typedef typename UGraph::EdgeIt EdgeIt; |
1406 |
1406 |
1407 Bfs<UndirGraph> bfs(graph); |
1407 Bfs<UGraph> bfs(graph); |
1408 bfs.init(); |
1408 bfs.init(); |
1409 for(NodeIt i(graph);i!=INVALID;++i){ |
1409 for(NodeIt i(graph);i!=INVALID;++i){ |
1410 if(!bfs.reached(i)){ |
1410 if(!bfs.reached(i)){ |
1411 bfs.run(i); |
1411 bfs.run(i); |
1412 } |
1412 } |
1432 /// |
1432 /// |
1433 /// \author Balazs Attila Mihaly |
1433 /// \author Balazs Attila Mihaly |
1434 /// |
1434 /// |
1435 /// \image html bipartite_partitions.png |
1435 /// \image html bipartite_partitions.png |
1436 /// \image latex bipartite_partitions.eps "Bipartite partititions" width=\textwidth |
1436 /// \image latex bipartite_partitions.eps "Bipartite partititions" width=\textwidth |
1437 template<typename UndirGraph, typename NodeMap> |
1437 template<typename UGraph, typename NodeMap> |
1438 inline bool bipartitePartitions(const UndirGraph &graph, NodeMap &partMap){ |
1438 inline bool bipartitePartitions(const UGraph &graph, NodeMap &partMap){ |
1439 checkConcept<concept::UndirGraph, UndirGraph>(); |
1439 checkConcept<concept::UGraph, UGraph>(); |
1440 |
1440 |
1441 typedef typename UndirGraph::Node Node; |
1441 typedef typename UGraph::Node Node; |
1442 typedef typename UndirGraph::NodeIt NodeIt; |
1442 typedef typename UGraph::NodeIt NodeIt; |
1443 typedef typename UndirGraph::EdgeIt EdgeIt; |
1443 typedef typename UGraph::EdgeIt EdgeIt; |
1444 |
1444 |
1445 Bfs<UndirGraph> bfs(graph); |
1445 Bfs<UGraph> bfs(graph); |
1446 bfs.init(); |
1446 bfs.init(); |
1447 for(NodeIt i(graph);i!=INVALID;++i){ |
1447 for(NodeIt i(graph);i!=INVALID;++i){ |
1448 if(!bfs.reached(i)){ |
1448 if(!bfs.reached(i)){ |
1449 bfs.addSource(i); |
1449 bfs.addSource(i); |
1450 for(Node j=bfs.processNextNode();!bfs.emptyQueue(); |
1450 for(Node j=bfs.processNextNode();!bfs.emptyQueue(); |