Changeset 1909:2d806130e700 in lemon-0.x for lemon/topology.h
- Timestamp:
- 01/26/06 16:42:13 (18 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2484
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/topology.h
r1875 r1909 25 25 26 26 #include <lemon/concept/graph.h> 27 #include <lemon/concept/u ndir_graph.h>27 #include <lemon/concept/ugraph.h> 28 28 #include <lemon/concept_check.h> 29 29 … … 50 50 /// \return %True when there is path between any two nodes in the graph. 51 51 /// \note By definition, the empty graph is connected. 52 template <typename U ndirGraph>53 bool connected(const U ndirGraph& graph) {54 checkConcept<concept::U ndirGraph, UndirGraph>();55 typedef typename U ndirGraph::NodeIt NodeIt;52 template <typename UGraph> 53 bool connected(const UGraph& graph) { 54 checkConcept<concept::UGraph, UGraph>(); 55 typedef typename UGraph::NodeIt NodeIt; 56 56 if (NodeIt(graph) == INVALID) return true; 57 Dfs<U ndirGraph> dfs(graph);57 Dfs<UGraph> dfs(graph); 58 58 dfs.run(NodeIt(graph)); 59 59 for (NodeIt it(graph); it != INVALID; ++it) { … … 75 75 /// \note By definition, the empty graph consists 76 76 /// of zero connected components. 77 template <typename U ndirGraph>78 int countConnectedComponents(const U ndirGraph &graph) {79 checkConcept<concept::U ndirGraph, UndirGraph>();80 typedef typename U ndirGraph::Node Node;81 typedef typename U ndirGraph::Edge Edge;77 template <typename UGraph> 78 int countConnectedComponents(const UGraph &graph) { 79 checkConcept<concept::UGraph, UGraph>(); 80 typedef typename UGraph::Node Node; 81 typedef typename UGraph::Edge Edge; 82 82 83 83 typedef NullMap<Node, Edge> PredMap; … … 85 85 86 86 int compNum = 0; 87 typename Bfs<U ndirGraph>::87 typename Bfs<UGraph>:: 88 88 template DefPredMap<PredMap>:: 89 89 template DefDistMap<DistMap>:: … … 97 97 98 98 bfs.init(); 99 for(typename U ndirGraph::NodeIt n(graph); n != INVALID; ++n) {99 for(typename UGraph::NodeIt n(graph); n != INVALID; ++n) { 100 100 if (!bfs.reached(n)) { 101 101 bfs.addSource(n); … … 123 123 /// \return The number of components 124 124 /// 125 template <class U ndirGraph, class NodeMap>126 int connectedComponents(const U ndirGraph &graph, NodeMap &compMap) {127 checkConcept<concept::U ndirGraph, UndirGraph>();128 typedef typename U ndirGraph::Node Node;129 typedef typename U ndirGraph::Edge Edge;125 template <class UGraph, class NodeMap> 126 int connectedComponents(const UGraph &graph, NodeMap &compMap) { 127 checkConcept<concept::UGraph, UGraph>(); 128 typedef typename UGraph::Node Node; 129 typedef typename UGraph::Edge Edge; 130 130 checkConcept<concept::WriteMap<Node, int>, NodeMap>(); 131 131 … … 134 134 135 135 int compNum = 0; 136 typename Bfs<U ndirGraph>::136 typename Bfs<UGraph>:: 137 137 template DefPredMap<PredMap>:: 138 138 template DefDistMap<DistMap>:: … … 146 146 147 147 bfs.init(); 148 for(typename U ndirGraph::NodeIt n(graph); n != INVALID; ++n) {148 for(typename UGraph::NodeIt n(graph); n != INVALID; ++n) { 149 149 if(!bfs.reached(n)) { 150 150 bfs.addSource(n); … … 485 485 typedef typename Graph::Node Node; 486 486 typedef typename Graph::Edge Edge; 487 typedef typename Graph::U ndirEdge UndirEdge;487 typedef typename Graph::UEdge UEdge; 488 488 489 489 CountBiNodeConnectedComponentsVisitor(const Graph& graph, int &compNum) … … 543 543 typedef typename Graph::Node Node; 544 544 typedef typename Graph::Edge Edge; 545 typedef typename Graph::U ndirEdge UndirEdge;545 typedef typename Graph::UEdge UEdge; 546 546 547 547 BiNodeConnectedComponentsVisitor(const Graph& graph, … … 613 613 typename Graph::template NodeMap<int> _retMap; 614 614 typename Graph::template NodeMap<Edge> _predMap; 615 std::stack<U ndirEdge> _edgeStack;615 std::stack<UEdge> _edgeStack; 616 616 int _num; 617 617 }; … … 623 623 typedef typename Graph::Node Node; 624 624 typedef typename Graph::Edge Edge; 625 typedef typename Graph::U ndirEdge UndirEdge;625 typedef typename Graph::UEdge UEdge; 626 626 627 627 BiNodeConnectedCutNodesVisitor(const Graph& graph, NodeMap& cutMap, … … 689 689 typename Graph::template NodeMap<int> _retMap; 690 690 typename Graph::template NodeMap<Node> _predMap; 691 std::stack<U ndirEdge> _edgeStack;691 std::stack<UEdge> _edgeStack; 692 692 int _num; 693 693 bool rootCut; … … 696 696 } 697 697 698 template <typename U ndirGraph>699 int countBiNodeConnectedComponents(const U ndirGraph& graph);698 template <typename UGraph> 699 int countBiNodeConnectedComponents(const UGraph& graph); 700 700 701 701 /// \ingroup topology … … 710 710 /// \return %True when the graph bi-node-connected. 711 711 /// \todo Make it faster. 712 template <typename U ndirGraph>713 bool biNodeConnected(const U ndirGraph& graph) {712 template <typename UGraph> 713 bool biNodeConnected(const UGraph& graph) { 714 714 return countBiNodeConnectedComponents(graph) == 1; 715 715 } … … 726 726 /// \param graph The graph. 727 727 /// \return The number of components. 728 template <typename U ndirGraph>729 int countBiNodeConnectedComponents(const U ndirGraph& graph) {730 checkConcept<concept::U ndirGraph, UndirGraph>();731 typedef typename U ndirGraph::NodeIt NodeIt;728 template <typename UGraph> 729 int countBiNodeConnectedComponents(const UGraph& graph) { 730 checkConcept<concept::UGraph, UGraph>(); 731 typedef typename UGraph::NodeIt NodeIt; 732 732 733 733 using namespace _topology_bits; 734 734 735 typedef CountBiNodeConnectedComponentsVisitor<U ndirGraph> Visitor;735 typedef CountBiNodeConnectedComponentsVisitor<UGraph> Visitor; 736 736 737 737 int compNum = 0; 738 738 Visitor visitor(graph, compNum); 739 739 740 DfsVisit<U ndirGraph, Visitor> dfs(graph, visitor);740 DfsVisit<UGraph, Visitor> dfs(graph, visitor); 741 741 dfs.init(); 742 742 … … 763 763 /// 764 764 /// \param graph The graph. 765 /// \retval compMap A writable u ndiredge map. The values will be set from 0765 /// \retval compMap A writable uedge map. The values will be set from 0 766 766 /// to the number of the biconnected components minus one. Each values 767 767 /// of the map will be set exactly once, the values of a certain component … … 769 769 /// \return The number of components. 770 770 /// 771 template <typename U ndirGraph, typename UndirEdgeMap>772 int biNodeConnectedComponents(const U ndirGraph& graph,773 U ndirEdgeMap& compMap) {774 checkConcept<concept::U ndirGraph, UndirGraph>();775 typedef typename U ndirGraph::NodeIt NodeIt;776 typedef typename U ndirGraph::UndirEdge UndirEdge;777 checkConcept<concept::WriteMap<U ndirEdge, int>, UndirEdgeMap>();771 template <typename UGraph, typename UEdgeMap> 772 int biNodeConnectedComponents(const UGraph& graph, 773 UEdgeMap& compMap) { 774 checkConcept<concept::UGraph, UGraph>(); 775 typedef typename UGraph::NodeIt NodeIt; 776 typedef typename UGraph::UEdge UEdge; 777 checkConcept<concept::WriteMap<UEdge, int>, UEdgeMap>(); 778 778 779 779 using namespace _topology_bits; 780 780 781 typedef BiNodeConnectedComponentsVisitor<U ndirGraph, UndirEdgeMap> Visitor;781 typedef BiNodeConnectedComponentsVisitor<UGraph, UEdgeMap> Visitor; 782 782 783 783 int compNum = 0; 784 784 Visitor visitor(graph, compMap, compNum); 785 785 786 DfsVisit<U ndirGraph, Visitor> dfs(graph, visitor);786 DfsVisit<UGraph, Visitor> dfs(graph, visitor); 787 787 dfs.init(); 788 788 … … 810 810 /// the node separate two or more components. 811 811 /// \return The number of the cut nodes. 812 template <typename U ndirGraph, typename NodeMap>813 int biNodeConnectedCutNodes(const U ndirGraph& graph, NodeMap& cutMap) {814 checkConcept<concept::U ndirGraph, UndirGraph>();815 typedef typename U ndirGraph::Node Node;816 typedef typename U ndirGraph::NodeIt NodeIt;812 template <typename UGraph, typename NodeMap> 813 int biNodeConnectedCutNodes(const UGraph& graph, NodeMap& cutMap) { 814 checkConcept<concept::UGraph, UGraph>(); 815 typedef typename UGraph::Node Node; 816 typedef typename UGraph::NodeIt NodeIt; 817 817 checkConcept<concept::WriteMap<Node, bool>, NodeMap>(); 818 818 819 819 using namespace _topology_bits; 820 820 821 typedef BiNodeConnectedCutNodesVisitor<U ndirGraph, NodeMap> Visitor;821 typedef BiNodeConnectedCutNodesVisitor<UGraph, NodeMap> Visitor; 822 822 823 823 int cutNum = 0; 824 824 Visitor visitor(graph, cutMap, cutNum); 825 825 826 DfsVisit<U ndirGraph, Visitor> dfs(graph, visitor);826 DfsVisit<UGraph, Visitor> dfs(graph, visitor); 827 827 dfs.init(); 828 828 … … 843 843 typedef typename Graph::Node Node; 844 844 typedef typename Graph::Edge Edge; 845 typedef typename Graph::U ndirEdge UndirEdge;845 typedef typename Graph::UEdge UEdge; 846 846 847 847 CountBiEdgeConnectedComponentsVisitor(const Graph& graph, int &compNum) … … 899 899 typedef typename Graph::Node Node; 900 900 typedef typename Graph::Edge Edge; 901 typedef typename Graph::U ndirEdge UndirEdge;901 typedef typename Graph::UEdge UEdge; 902 902 903 903 BiEdgeConnectedComponentsVisitor(const Graph& graph, … … 966 966 typedef typename Graph::Node Node; 967 967 typedef typename Graph::Edge Edge; 968 typedef typename Graph::U ndirEdge UndirEdge;968 typedef typename Graph::UEdge UEdge; 969 969 970 970 BiEdgeConnectedCutEdgesVisitor(const Graph& graph, … … 1023 1023 } 1024 1024 1025 template <typename U ndirGraph>1026 int countbiEdgeConnectedComponents(const U ndirGraph& graph);1025 template <typename UGraph> 1026 int countbiEdgeConnectedComponents(const UGraph& graph); 1027 1027 1028 1028 /// \ingroup topology … … 1037 1037 /// \return The number of components. 1038 1038 /// \todo Make it faster. 1039 template <typename U ndirGraph>1040 bool biEdgeConnected(const U ndirGraph& graph) {1039 template <typename UGraph> 1040 bool biEdgeConnected(const UGraph& graph) { 1041 1041 return countBiEdgeConnectedComponents(graph) == 1; 1042 1042 } … … 1053 1053 /// \param graph The undirected graph. 1054 1054 /// \return The number of components. 1055 template <typename U ndirGraph>1056 int countBiEdgeConnectedComponents(const U ndirGraph& graph) {1057 checkConcept<concept::U ndirGraph, UndirGraph>();1058 typedef typename U ndirGraph::NodeIt NodeIt;1055 template <typename UGraph> 1056 int countBiEdgeConnectedComponents(const UGraph& graph) { 1057 checkConcept<concept::UGraph, UGraph>(); 1058 typedef typename UGraph::NodeIt NodeIt; 1059 1059 1060 1060 using namespace _topology_bits; 1061 1061 1062 typedef CountBiEdgeConnectedComponentsVisitor<U ndirGraph> Visitor;1062 typedef CountBiEdgeConnectedComponentsVisitor<UGraph> Visitor; 1063 1063 1064 1064 int compNum = 0; 1065 1065 Visitor visitor(graph, compNum); 1066 1066 1067 DfsVisit<U ndirGraph, Visitor> dfs(graph, visitor);1067 DfsVisit<UGraph, Visitor> dfs(graph, visitor); 1068 1068 dfs.init(); 1069 1069 … … 1096 1096 /// \return The number of components. 1097 1097 /// 1098 template <typename U ndirGraph, typename NodeMap>1099 int biEdgeConnectedComponents(const U ndirGraph& graph, NodeMap& compMap) {1100 checkConcept<concept::U ndirGraph, UndirGraph>();1101 typedef typename U ndirGraph::NodeIt NodeIt;1102 typedef typename U ndirGraph::Node Node;1098 template <typename UGraph, typename NodeMap> 1099 int biEdgeConnectedComponents(const UGraph& graph, NodeMap& compMap) { 1100 checkConcept<concept::UGraph, UGraph>(); 1101 typedef typename UGraph::NodeIt NodeIt; 1102 typedef typename UGraph::Node Node; 1103 1103 checkConcept<concept::WriteMap<Node, int>, NodeMap>(); 1104 1104 1105 1105 using namespace _topology_bits; 1106 1106 1107 typedef BiEdgeConnectedComponentsVisitor<U ndirGraph, NodeMap> Visitor;1107 typedef BiEdgeConnectedComponentsVisitor<UGraph, NodeMap> Visitor; 1108 1108 1109 1109 int compNum = 0; 1110 1110 Visitor visitor(graph, compMap, compNum); 1111 1111 1112 DfsVisit<U ndirGraph, Visitor> dfs(graph, visitor);1112 DfsVisit<UGraph, Visitor> dfs(graph, visitor); 1113 1113 dfs.init(); 1114 1114 … … 1137 1137 /// edge is a cut edge. 1138 1138 /// \return The number of cut edges. 1139 template <typename U ndirGraph, typename UndirEdgeMap>1140 int biEdgeConnectedCutEdges(const U ndirGraph& graph, UndirEdgeMap& cutMap) {1141 checkConcept<concept::U ndirGraph, UndirGraph>();1142 typedef typename U ndirGraph::NodeIt NodeIt;1143 typedef typename U ndirGraph::UndirEdge UndirEdge;1144 checkConcept<concept::WriteMap<U ndirEdge, bool>, UndirEdgeMap>();1139 template <typename UGraph, typename UEdgeMap> 1140 int biEdgeConnectedCutEdges(const UGraph& graph, UEdgeMap& cutMap) { 1141 checkConcept<concept::UGraph, UGraph>(); 1142 typedef typename UGraph::NodeIt NodeIt; 1143 typedef typename UGraph::UEdge UEdge; 1144 checkConcept<concept::WriteMap<UEdge, bool>, UEdgeMap>(); 1145 1145 1146 1146 using namespace _topology_bits; 1147 1147 1148 typedef BiEdgeConnectedCutEdgesVisitor<U ndirGraph, UndirEdgeMap> Visitor;1148 typedef BiEdgeConnectedCutEdgesVisitor<UGraph, UEdgeMap> Visitor; 1149 1149 1150 1150 int cutNum = 0; 1151 1151 Visitor visitor(graph, cutMap, cutNum); 1152 1152 1153 DfsVisit<U ndirGraph, Visitor> dfs(graph, visitor);1153 DfsVisit<UGraph, Visitor> dfs(graph, visitor); 1154 1154 dfs.init(); 1155 1155 … … 1327 1327 /// \return %True when there is no circle in the graph. 1328 1328 /// \see dag 1329 template <typename U ndirGraph>1330 bool acyclic(const U ndirGraph& graph) {1331 checkConcept<concept::U ndirGraph, UndirGraph>();1332 typedef typename U ndirGraph::Node Node;1333 typedef typename U ndirGraph::NodeIt NodeIt;1334 typedef typename U ndirGraph::Edge Edge;1335 Dfs<U ndirGraph> dfs(graph);1329 template <typename UGraph> 1330 bool acyclic(const UGraph& graph) { 1331 checkConcept<concept::UGraph, UGraph>(); 1332 typedef typename UGraph::Node Node; 1333 typedef typename UGraph::NodeIt NodeIt; 1334 typedef typename UGraph::Edge Edge; 1335 Dfs<UGraph> dfs(graph); 1336 1336 dfs.init(); 1337 1337 for (NodeIt it(graph); it != INVALID; ++it) { … … 1360 1360 /// \param graph The undirected graph. 1361 1361 /// \return %True when the graph is acyclic and connected. 1362 template <typename U ndirGraph>1363 bool tree(const U ndirGraph& graph) {1364 checkConcept<concept::U ndirGraph, UndirGraph>();1365 typedef typename U ndirGraph::Node Node;1366 typedef typename U ndirGraph::NodeIt NodeIt;1367 typedef typename U ndirGraph::Edge Edge;1368 Dfs<U ndirGraph> dfs(graph);1362 template <typename UGraph> 1363 bool tree(const UGraph& graph) { 1364 checkConcept<concept::UGraph, UGraph>(); 1365 typedef typename UGraph::Node Node; 1366 typedef typename UGraph::NodeIt NodeIt; 1367 typedef typename UGraph::Edge Edge; 1368 Dfs<UGraph> dfs(graph); 1369 1369 dfs.init(); 1370 1370 dfs.addSource(NodeIt(graph)); … … 1398 1398 /// 1399 1399 /// \author Balazs Attila Mihaly 1400 template<typename U ndirGraph>1401 inline bool bipartite(const U ndirGraph &graph){1402 checkConcept<concept::U ndirGraph, UndirGraph>();1403 1404 typedef typename U ndirGraph::NodeIt NodeIt;1405 typedef typename U ndirGraph::EdgeIt EdgeIt;1406 1407 Bfs<U ndirGraph> bfs(graph);1400 template<typename UGraph> 1401 inline bool bipartite(const UGraph &graph){ 1402 checkConcept<concept::UGraph, UGraph>(); 1403 1404 typedef typename UGraph::NodeIt NodeIt; 1405 typedef typename UGraph::EdgeIt EdgeIt; 1406 1407 Bfs<UGraph> bfs(graph); 1408 1408 bfs.init(); 1409 1409 for(NodeIt i(graph);i!=INVALID;++i){ … … 1435 1435 /// \image html bipartite_partitions.png 1436 1436 /// \image latex bipartite_partitions.eps "Bipartite partititions" width=\textwidth 1437 template<typename U ndirGraph, typename NodeMap>1438 inline bool bipartitePartitions(const U ndirGraph &graph, NodeMap &partMap){1439 checkConcept<concept::U ndirGraph, UndirGraph>();1440 1441 typedef typename U ndirGraph::Node Node;1442 typedef typename U ndirGraph::NodeIt NodeIt;1443 typedef typename U ndirGraph::EdgeIt EdgeIt;1437 template<typename UGraph, typename NodeMap> 1438 inline bool bipartitePartitions(const UGraph &graph, NodeMap &partMap){ 1439 checkConcept<concept::UGraph, UGraph>(); 1440 1441 typedef typename UGraph::Node Node; 1442 typedef typename UGraph::NodeIt NodeIt; 1443 typedef typename UGraph::EdgeIt EdgeIt; 1444 1444 1445 Bfs<U ndirGraph> bfs(graph);1445 Bfs<UGraph> bfs(graph); 1446 1446 bfs.init(); 1447 1447 for(NodeIt i(graph);i!=INVALID;++i){
Note: See TracChangeset
for help on using the changeset viewer.