|
alpar@810
|
1 |
#include <iostream>
|
|
alpar@810
|
2 |
#include <vector>
|
|
alpar@810
|
3 |
|
|
alpar@810
|
4 |
#include "test_tools.h"
|
|
alpar@810
|
5 |
#include <hugo/maps.h>
|
|
alpar@810
|
6 |
#include <hugo/kruskal.h>
|
|
alpar@810
|
7 |
#include <hugo/list_graph.h>
|
|
alpar@810
|
8 |
#include <hugo/skeletons/maps.h>
|
|
alpar@810
|
9 |
#include <hugo/skeletons/graph.h>
|
|
alpar@810
|
10 |
|
|
alpar@810
|
11 |
|
|
alpar@810
|
12 |
using namespace std;
|
|
alpar@810
|
13 |
using namespace hugo;
|
|
alpar@810
|
14 |
|
|
alpar@810
|
15 |
void checkCompileKruskal()
|
|
alpar@810
|
16 |
{
|
|
alpar@810
|
17 |
skeleton::WriteMap<skeleton::StaticGraphSkeleton::Edge,bool> w;
|
|
alpar@810
|
18 |
|
|
alpar@810
|
19 |
kruskalEdgeMap(skeleton::StaticGraphSkeleton(),
|
|
alpar@810
|
20 |
skeleton::ReadMap<skeleton::StaticGraphSkeleton::Edge,int>(),
|
|
alpar@810
|
21 |
w);
|
|
alpar@810
|
22 |
}
|
|
alpar@810
|
23 |
|
|
alpar@810
|
24 |
int main() {
|
|
alpar@810
|
25 |
|
|
alpar@810
|
26 |
typedef ListGraph::Node Node;
|
|
alpar@810
|
27 |
typedef ListGraph::Edge Edge;
|
|
alpar@810
|
28 |
typedef ListGraph::NodeIt NodeIt;
|
|
alpar@810
|
29 |
typedef ListGraph::EdgeIt EdgeIt;
|
|
alpar@810
|
30 |
|
|
alpar@810
|
31 |
ListGraph G;
|
|
alpar@810
|
32 |
|
|
alpar@810
|
33 |
Node s=G.addNode();
|
|
alpar@810
|
34 |
Node v1=G.addNode();
|
|
alpar@810
|
35 |
Node v2=G.addNode();
|
|
alpar@810
|
36 |
Node v3=G.addNode();
|
|
alpar@810
|
37 |
Node v4=G.addNode();
|
|
alpar@810
|
38 |
Node t=G.addNode();
|
|
alpar@810
|
39 |
|
|
alpar@810
|
40 |
Edge e1 = G.addEdge(s, v1);
|
|
alpar@810
|
41 |
Edge e2 = G.addEdge(s, v2);
|
|
alpar@810
|
42 |
Edge e3 = G.addEdge(v1, v2);
|
|
alpar@810
|
43 |
Edge e4 = G.addEdge(v2, v1);
|
|
alpar@810
|
44 |
Edge e5 = G.addEdge(v1, v3);
|
|
alpar@810
|
45 |
Edge e6 = G.addEdge(v3, v2);
|
|
alpar@810
|
46 |
Edge e7 = G.addEdge(v2, v4);
|
|
alpar@810
|
47 |
Edge e8 = G.addEdge(v4, v3);
|
|
alpar@810
|
48 |
Edge e9 = G.addEdge(v3, t);
|
|
alpar@810
|
49 |
Edge e10 = G.addEdge(v4, t);
|
|
alpar@810
|
50 |
|
|
alpar@810
|
51 |
typedef ListGraph::EdgeMap<int> ECostMap;
|
|
alpar@810
|
52 |
typedef ListGraph::EdgeMap<bool> EBoolMap;
|
|
alpar@810
|
53 |
|
|
alpar@810
|
54 |
ECostMap edge_cost_map(G, 2);
|
|
alpar@810
|
55 |
EBoolMap tree_map(G);
|
|
alpar@810
|
56 |
|
|
alpar@810
|
57 |
|
|
alpar@810
|
58 |
//Test with const map.
|
|
alpar@810
|
59 |
check(kruskalEdgeMap(G, ConstMap<ListGraph::Edge,int>(2), tree_map)==10,
|
|
alpar@810
|
60 |
"Total cost should be 10");
|
|
alpar@810
|
61 |
//Test with a edge map (filled with uniform costs).
|
|
alpar@810
|
62 |
check(kruskalEdgeMap(G, edge_cost_map, tree_map)==10,
|
|
alpar@810
|
63 |
"Total cost should be 10");
|
|
alpar@810
|
64 |
|
|
alpar@810
|
65 |
edge_cost_map.set(e1, -10);
|
|
alpar@810
|
66 |
edge_cost_map.set(e2, -9);
|
|
alpar@810
|
67 |
edge_cost_map.set(e3, -8);
|
|
alpar@810
|
68 |
edge_cost_map.set(e4, -7);
|
|
alpar@810
|
69 |
edge_cost_map.set(e5, -6);
|
|
alpar@810
|
70 |
edge_cost_map.set(e6, -5);
|
|
alpar@810
|
71 |
edge_cost_map.set(e7, -4);
|
|
alpar@810
|
72 |
edge_cost_map.set(e8, -3);
|
|
alpar@810
|
73 |
edge_cost_map.set(e9, -2);
|
|
alpar@810
|
74 |
edge_cost_map.set(e10, -1);
|
|
alpar@810
|
75 |
|
|
alpar@810
|
76 |
vector<Edge> tree_edge_vec;
|
|
alpar@810
|
77 |
|
|
alpar@810
|
78 |
//Test with a edge map and inserter.
|
|
alpar@810
|
79 |
check(kruskalEdgeMap_IteratorOut(G, edge_cost_map,
|
|
alpar@810
|
80 |
back_inserter(tree_edge_vec))
|
|
alpar@810
|
81 |
==-31,
|
|
alpar@810
|
82 |
"Total cost should be -31.");
|
|
alpar@810
|
83 |
|
|
alpar@810
|
84 |
check(tree_edge_vec.size()==5,"The tree should have 5 edges.");
|
|
alpar@810
|
85 |
|
|
alpar@810
|
86 |
check(tree_edge_vec[0]==e1 &&
|
|
alpar@810
|
87 |
tree_edge_vec[1]==e2 &&
|
|
alpar@810
|
88 |
tree_edge_vec[2]==e5 &&
|
|
alpar@810
|
89 |
tree_edge_vec[3]==e7 &&
|
|
alpar@810
|
90 |
tree_edge_vec[4]==e9,
|
|
alpar@810
|
91 |
"Wrong tree.");
|
|
alpar@810
|
92 |
|
|
alpar@810
|
93 |
return 0;
|
|
alpar@810
|
94 |
}
|