30 |
30 |
31 void checkCompileKruskal() |
31 void checkCompileKruskal() |
32 { |
32 { |
33 concept::WriteMap<concept::StaticGraph::Edge,bool> w; |
33 concept::WriteMap<concept::StaticGraph::Edge,bool> w; |
34 |
34 |
35 kruskalEdgeMap(concept::StaticGraph(), |
35 kruskal(concept::StaticGraph(), |
36 concept::ReadMap<concept::StaticGraph::Edge,int>(), |
36 concept::ReadMap<concept::StaticGraph::Edge,int>(), |
37 w); |
37 w); |
38 } |
38 } |
39 |
39 |
40 int main() { |
40 int main() { |
41 |
41 |
42 typedef ListGraph::Node Node; |
42 typedef ListGraph::Node Node; |
70 ECostMap edge_cost_map(G, 2); |
70 ECostMap edge_cost_map(G, 2); |
71 EBoolMap tree_map(G); |
71 EBoolMap tree_map(G); |
72 |
72 |
73 |
73 |
74 //Test with const map. |
74 //Test with const map. |
75 check(kruskalEdgeMap(G, ConstMap<ListGraph::Edge,int>(2), tree_map)==10, |
75 check(kruskal(G, ConstMap<ListGraph::Edge,int>(2), tree_map)==10, |
76 "Total cost should be 10"); |
76 "Total cost should be 10"); |
77 //Test with a edge map (filled with uniform costs). |
77 //Test with a edge map (filled with uniform costs). |
78 check(kruskalEdgeMap(G, edge_cost_map, tree_map)==10, |
78 check(kruskal(G, edge_cost_map, tree_map)==10, |
79 "Total cost should be 10"); |
79 "Total cost should be 10"); |
80 |
80 |
81 edge_cost_map.set(e1, -10); |
81 edge_cost_map.set(e1, -10); |
82 edge_cost_map.set(e2, -9); |
82 edge_cost_map.set(e2, -9); |
83 edge_cost_map.set(e3, -8); |
83 edge_cost_map.set(e3, -8); |
87 edge_cost_map.set(e7, -4); |
87 edge_cost_map.set(e7, -4); |
88 edge_cost_map.set(e8, -3); |
88 edge_cost_map.set(e8, -3); |
89 edge_cost_map.set(e9, -2); |
89 edge_cost_map.set(e9, -2); |
90 edge_cost_map.set(e10, -1); |
90 edge_cost_map.set(e10, -1); |
91 |
91 |
92 vector<Edge> tree_edge_vec; |
92 vector<Edge> tree_edge_vec(5); |
93 |
93 |
94 //Test with a edge map and inserter. |
94 //Test with a edge map and inserter. |
95 check(kruskalEdgeMap_IteratorOut(G, edge_cost_map, |
95 check(kruskal(G, edge_cost_map, |
96 back_inserter(tree_edge_vec)) |
96 tree_edge_vec.begin()) |
97 ==-31, |
97 ==-31, |
98 "Total cost should be -31."); |
98 "Total cost should be -31."); |
99 |
99 |
100 tree_edge_vec.clear(); |
100 tree_edge_vec.clear(); |
101 |
101 |
|
102 check(kruskal(G, edge_cost_map, |
|
103 back_inserter(tree_edge_vec)) |
|
104 ==-31, |
|
105 "Total cost should be -31."); |
|
106 |
|
107 tree_edge_vec.clear(); |
|
108 |
102 //The above test could also be coded like this: |
109 //The above test could also be coded like this: |
103 check(kruskal(G, |
110 check(kruskal(G, |
104 makeKruskalMapInput(G, edge_cost_map), |
111 makeKruskalMapInput(G, edge_cost_map), |
105 makeKruskalSequenceOutput(back_inserter(tree_edge_vec))) |
112 makeKruskalSequenceOutput(back_inserter(tree_edge_vec))) |
106 ==-31, |
113 ==-31, |