1 /* -*- C++ -*- |
1 /* -*- mode: C++; indent-tabs-mode: nil; -*- |
2 * |
2 * |
3 * This file is a part of LEMON, a generic C++ optimization library |
3 * This file is a part of LEMON, a generic C++ optimization library. |
4 * |
4 * |
5 * Copyright (C) 2003-2008 |
5 * Copyright (C) 2003-2008 |
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
7 * (Egervary Research Group on Combinatorial Optimization, EGRES). |
7 * (Egervary Research Group on Combinatorial Optimization, EGRES). |
8 * |
8 * |
71 Node v1=G.addNode(); |
71 Node v1=G.addNode(); |
72 Node v2=G.addNode(); |
72 Node v2=G.addNode(); |
73 Node v3=G.addNode(); |
73 Node v3=G.addNode(); |
74 Node v4=G.addNode(); |
74 Node v4=G.addNode(); |
75 Node t=G.addNode(); |
75 Node t=G.addNode(); |
76 |
76 |
77 Edge e1 = G.addEdge(s, v1); |
77 Edge e1 = G.addEdge(s, v1); |
78 Edge e2 = G.addEdge(s, v2); |
78 Edge e2 = G.addEdge(s, v2); |
79 Edge e3 = G.addEdge(v1, v2); |
79 Edge e3 = G.addEdge(v1, v2); |
80 Edge e4 = G.addEdge(v2, v1); |
80 Edge e4 = G.addEdge(v2, v1); |
81 Edge e5 = G.addEdge(v1, v3); |
81 Edge e5 = G.addEdge(v1, v3); |
88 typedef ListGraph::EdgeMap<int> ECostMap; |
88 typedef ListGraph::EdgeMap<int> ECostMap; |
89 typedef ListGraph::EdgeMap<bool> EBoolMap; |
89 typedef ListGraph::EdgeMap<bool> EBoolMap; |
90 |
90 |
91 ECostMap edge_cost_map(G, 2); |
91 ECostMap edge_cost_map(G, 2); |
92 EBoolMap tree_map(G); |
92 EBoolMap tree_map(G); |
93 |
93 |
94 |
94 |
95 //Test with const map. |
95 //Test with const map. |
96 check(kruskal(G, ConstMap<ListGraph::Edge,int>(2), tree_map)==10, |
96 check(kruskal(G, ConstMap<ListGraph::Edge,int>(2), tree_map)==10, |
97 "Total cost should be 10"); |
97 "Total cost should be 10"); |
98 //Test with an edge map (filled with uniform costs). |
98 //Test with an edge map (filled with uniform costs). |
99 check(kruskal(G, edge_cost_map, tree_map)==10, |
99 check(kruskal(G, edge_cost_map, tree_map)==10, |
100 "Total cost should be 10"); |
100 "Total cost should be 10"); |
101 |
101 |
102 edge_cost_map.set(e1, -10); |
102 edge_cost_map.set(e1, -10); |
103 edge_cost_map.set(e2, -9); |
103 edge_cost_map.set(e2, -9); |
104 edge_cost_map.set(e3, -8); |
104 edge_cost_map.set(e3, -8); |
105 edge_cost_map.set(e4, -7); |
105 edge_cost_map.set(e4, -7); |
112 |
112 |
113 vector<Edge> tree_edge_vec(5); |
113 vector<Edge> tree_edge_vec(5); |
114 |
114 |
115 //Test with a edge map and inserter. |
115 //Test with a edge map and inserter. |
116 check(kruskal(G, edge_cost_map, |
116 check(kruskal(G, edge_cost_map, |
117 tree_edge_vec.begin()) |
117 tree_edge_vec.begin()) |
118 ==-31, |
118 ==-31, |
119 "Total cost should be -31."); |
119 "Total cost should be -31."); |
120 |
120 |
121 tree_edge_vec.clear(); |
121 tree_edge_vec.clear(); |
122 |
122 |
123 check(kruskal(G, edge_cost_map, |
123 check(kruskal(G, edge_cost_map, |
124 back_inserter(tree_edge_vec)) |
124 back_inserter(tree_edge_vec)) |
125 ==-31, |
125 ==-31, |
126 "Total cost should be -31."); |
126 "Total cost should be -31."); |
127 |
127 |
128 // tree_edge_vec.clear(); |
128 // tree_edge_vec.clear(); |
129 |
129 |
130 // //The above test could also be coded like this: |
130 // //The above test could also be coded like this: |
131 // check(kruskal(G, |
131 // check(kruskal(G, |
132 // makeKruskalMapInput(G, edge_cost_map), |
132 // makeKruskalMapInput(G, edge_cost_map), |
133 // makeKruskalSequenceOutput(back_inserter(tree_edge_vec))) |
133 // makeKruskalSequenceOutput(back_inserter(tree_edge_vec))) |
134 // ==-31, |
134 // ==-31, |
135 // "Total cost should be -31."); |
135 // "Total cost should be -31."); |
136 |
136 |
137 check(tree_edge_vec.size()==5,"The tree should have 5 edges."); |
137 check(tree_edge_vec.size()==5,"The tree should have 5 edges."); |
138 |
138 |
139 check(tree_edge_vec[0]==e1 && |
139 check(tree_edge_vec[0]==e1 && |
140 tree_edge_vec[1]==e2 && |
140 tree_edge_vec[1]==e2 && |
141 tree_edge_vec[2]==e5 && |
141 tree_edge_vec[2]==e5 && |
142 tree_edge_vec[3]==e7 && |
142 tree_edge_vec[3]==e7 && |
143 tree_edge_vec[4]==e9, |
143 tree_edge_vec[4]==e9, |
144 "Wrong tree."); |
144 "Wrong tree."); |
145 |
145 |
146 return 0; |
146 return 0; |
147 } |
147 } |