21 |
21 |
22 #include "test_tools.h" |
22 #include "test_tools.h" |
23 #include <lemon/maps.h> |
23 #include <lemon/maps.h> |
24 #include <lemon/kruskal.h> |
24 #include <lemon/kruskal.h> |
25 #include <lemon/list_graph.h> |
25 #include <lemon/list_graph.h> |
|
26 |
26 #include <lemon/concepts/maps.h> |
27 #include <lemon/concepts/maps.h> |
27 #include <lemon/concepts/graph.h> |
28 #include <lemon/concepts/graph.h> |
|
29 #include <lemon/concepts/ugraph.h> |
28 |
30 |
29 |
31 |
30 using namespace std; |
32 using namespace std; |
31 using namespace lemon; |
33 using namespace lemon; |
32 |
34 |
33 void checkCompileKruskal() |
35 void checkCompileKruskal() |
34 { |
36 { |
35 concepts::WriteMap<concepts::Graph::Edge,bool> w; |
37 concepts::WriteMap<concepts::Graph::Edge,bool> w; |
|
38 concepts::WriteMap<concepts::UGraph::UEdge,bool> uw; |
|
39 |
|
40 concepts::ReadMap<concepts::Graph::Edge,int> r; |
|
41 concepts::ReadMap<concepts::UGraph::UEdge,int> ur; |
36 |
42 |
37 concepts::Graph g; |
43 concepts::Graph g; |
38 kruskal(g, |
44 concepts::UGraph ug; |
39 concepts::ReadMap<concepts::Graph::Edge,int>(), |
45 |
40 w); |
46 kruskal(g, r, w); |
|
47 kruskal(ug, ur, uw); |
|
48 |
|
49 std::vector<std::pair<concepts::Graph::Edge, int> > rs; |
|
50 std::vector<std::pair<concepts::UGraph::UEdge, int> > urs; |
|
51 |
|
52 kruskal(g, rs, w); |
|
53 kruskal(ug, urs, uw); |
|
54 |
|
55 std::vector<concepts::Graph::Edge> ws; |
|
56 std::vector<concepts::UGraph::UEdge> uws; |
|
57 |
|
58 kruskal(g, r, ws.begin()); |
|
59 kruskal(ug, ur, uws.begin()); |
|
60 |
|
61 Kruskal<concepts::UGraph,concepts::ReadMap<concepts::UGraph::UEdge,int> > |
|
62 alg(ug, ur); |
|
63 |
|
64 alg.init(); |
|
65 alg.initPresorted(uws.begin(), uws.end()); |
|
66 alg.reinit(); |
|
67 |
|
68 alg.emptyQueue(); |
|
69 |
|
70 alg.nextEdge(); |
|
71 alg.processNextEdge(); |
|
72 alg.processEdge(concepts::UGraph::UEdge()); |
|
73 |
|
74 alg.run(); |
|
75 |
|
76 alg.treeMap(); |
|
77 alg.tree(concepts::UGraph::UEdge()); |
41 } |
78 } |
42 |
79 |
43 int main() { |
80 int main() { |
44 |
81 |
45 typedef ListGraph::Node Node; |
82 typedef ListUGraph::Node Node; |
46 typedef ListGraph::Edge Edge; |
83 typedef ListUGraph::UEdge UEdge; |
47 typedef ListGraph::NodeIt NodeIt; |
84 typedef ListUGraph::NodeIt NodeIt; |
48 typedef ListGraph::EdgeIt EdgeIt; |
85 typedef ListUGraph::EdgeIt EdgeIt; |
49 |
86 |
50 ListGraph G; |
87 ListUGraph G; |
51 |
88 |
52 Node s=G.addNode(); |
89 Node s=G.addNode(); |
53 Node v1=G.addNode(); |
90 Node v1=G.addNode(); |
54 Node v2=G.addNode(); |
91 Node v2=G.addNode(); |
55 Node v3=G.addNode(); |
92 Node v3=G.addNode(); |
56 Node v4=G.addNode(); |
93 Node v4=G.addNode(); |
57 Node t=G.addNode(); |
94 Node t=G.addNode(); |
58 |
95 |
59 Edge e1 = G.addEdge(s, v1); |
96 UEdge e1 = G.addEdge(s, v1); |
60 Edge e2 = G.addEdge(s, v2); |
97 UEdge e2 = G.addEdge(s, v2); |
61 Edge e3 = G.addEdge(v1, v2); |
98 UEdge e3 = G.addEdge(v1, v2); |
62 Edge e4 = G.addEdge(v2, v1); |
99 UEdge e4 = G.addEdge(v2, v1); |
63 Edge e5 = G.addEdge(v1, v3); |
100 UEdge e5 = G.addEdge(v1, v3); |
64 Edge e6 = G.addEdge(v3, v2); |
101 UEdge e6 = G.addEdge(v3, v2); |
65 Edge e7 = G.addEdge(v2, v4); |
102 UEdge e7 = G.addEdge(v2, v4); |
66 Edge e8 = G.addEdge(v4, v3); |
103 UEdge e8 = G.addEdge(v4, v3); |
67 Edge e9 = G.addEdge(v3, t); |
104 UEdge e9 = G.addEdge(v3, t); |
68 Edge e10 = G.addEdge(v4, t); |
105 UEdge e10 = G.addEdge(v4, t); |
69 |
106 |
70 typedef ListGraph::EdgeMap<int> ECostMap; |
107 typedef ListUGraph::UEdgeMap<int> ECostMap; |
71 typedef ListGraph::EdgeMap<bool> EBoolMap; |
108 typedef ListUGraph::UEdgeMap<bool> EBoolMap; |
72 |
109 |
73 ECostMap edge_cost_map(G, 2); |
110 ECostMap edge_cost_map(G, 2); |
74 EBoolMap tree_map(G); |
111 EBoolMap tree_map(G); |
75 |
112 |
76 |
113 |
77 //Test with const map. |
114 //Test with const map. |
78 check(kruskal(G, ConstMap<ListGraph::Edge,int>(2), tree_map)==10, |
115 check(kruskal(G, ConstMap<ListUGraph::UEdge,int>(2), tree_map)==10, |
79 "Total cost should be 10"); |
116 "Total cost should be 10"); |
80 //Test with a edge map (filled with uniform costs). |
117 //Test with a edge map (filled with uniform costs). |
81 check(kruskal(G, edge_cost_map, tree_map)==10, |
118 check(kruskal(G, edge_cost_map, tree_map)==10, |
82 "Total cost should be 10"); |
119 "Total cost should be 10"); |
83 |
120 |
105 check(kruskal(G, edge_cost_map, |
142 check(kruskal(G, edge_cost_map, |
106 back_inserter(tree_edge_vec)) |
143 back_inserter(tree_edge_vec)) |
107 ==-31, |
144 ==-31, |
108 "Total cost should be -31."); |
145 "Total cost should be -31."); |
109 |
146 |
110 tree_edge_vec.clear(); |
147 // tree_edge_vec.clear(); |
111 |
148 |
112 //The above test could also be coded like this: |
149 // //The above test could also be coded like this: |
113 check(kruskal(G, |
150 // check(kruskal(G, |
114 makeKruskalMapInput(G, edge_cost_map), |
151 // makeKruskalMapInput(G, edge_cost_map), |
115 makeKruskalSequenceOutput(back_inserter(tree_edge_vec))) |
152 // makeKruskalSequenceOutput(back_inserter(tree_edge_vec))) |
116 ==-31, |
153 // ==-31, |
117 "Total cost should be -31."); |
154 // "Total cost should be -31."); |
118 |
155 |
119 check(tree_edge_vec.size()==5,"The tree should have 5 edges."); |
156 check(tree_edge_vec.size()==5,"The tree should have 5 edges."); |
120 |
157 |
121 check(tree_edge_vec[0]==e1 && |
158 check(tree_edge_vec[0]==e1 && |
122 tree_edge_vec[1]==e2 && |
159 tree_edge_vec[1]==e2 && |
123 tree_edge_vec[2]==e5 && |
160 tree_edge_vec[2]==e5 && |
124 tree_edge_vec[3]==e7 && |
161 tree_edge_vec[3]==e7 && |
125 tree_edge_vec[4]==e9, |
162 tree_edge_vec[4]==e9, |
126 "Wrong tree."); |
163 "Wrong tree."); |
127 |
164 |
|
165 Kruskal<ListUGraph, ECostMap> ka(G, edge_cost_map); |
|
166 |
|
167 ka.run(); |
|
168 |
|
169 check(ka.tree(e1) && |
|
170 ka.tree(e2) && |
|
171 ka.tree(e5) && |
|
172 ka.tree(e7) && |
|
173 ka.tree(e9), |
|
174 "Wrong tree."); |
|
175 |
|
176 check(ka.treeValue() == -31, |
|
177 "Total cost should be -31."); |
|
178 |
128 return 0; |
179 return 0; |
129 } |
180 } |