15 typedef ListGraph::Node Node; |
38 typedef ListGraph::Node Node; |
16 typedef ListGraph::Edge Edge; |
39 typedef ListGraph::Edge Edge; |
17 typedef ListGraph::NodeIt NodeIt; |
40 typedef ListGraph::NodeIt NodeIt; |
18 typedef ListGraph::EdgeIt EdgeIt; |
41 typedef ListGraph::EdgeIt EdgeIt; |
19 |
42 |
20 ListGraph G; |
43 ListGraph g; |
|
44 //Make an example graph g. |
|
45 Node s=g.addNode(); |
|
46 Node v1=g.addNode(); |
|
47 Node v2=g.addNode(); |
|
48 Node v3=g.addNode(); |
|
49 Node v4=g.addNode(); |
|
50 Node t=g.addNode(); |
|
51 |
|
52 Edge e1 = g.addEdge(s, v1); |
|
53 Edge e2 = g.addEdge(s, v2); |
|
54 Edge e3 = g.addEdge(v1, v2); |
|
55 Edge e4 = g.addEdge(v2, v1); |
|
56 Edge e5 = g.addEdge(v1, v3); |
|
57 Edge e6 = g.addEdge(v3, v2); |
|
58 Edge e7 = g.addEdge(v2, v4); |
|
59 Edge e8 = g.addEdge(v4, v3); |
|
60 Edge e9 = g.addEdge(v3, t); |
|
61 Edge e10 = g.addEdge(v4, t); |
21 |
62 |
22 Node s=G.addNode(); |
63 //Make the input and output for the kruskal. |
23 Node v1=G.addNode(); |
|
24 Node v2=G.addNode(); |
|
25 Node v3=G.addNode(); |
|
26 Node v4=G.addNode(); |
|
27 Node t=G.addNode(); |
|
28 |
|
29 Edge e1 = G.addEdge(s, v1); |
|
30 Edge e2 = G.addEdge(s, v2); |
|
31 Edge e3 = G.addEdge(v1, v2); |
|
32 Edge e4 = G.addEdge(v2, v1); |
|
33 Edge e5 = G.addEdge(v1, v3); |
|
34 Edge e6 = G.addEdge(v3, v2); |
|
35 Edge e7 = G.addEdge(v2, v4); |
|
36 Edge e8 = G.addEdge(v4, v3); |
|
37 Edge e9 = G.addEdge(v3, t); |
|
38 Edge e10 = G.addEdge(v4, t); |
|
39 |
|
40 typedef ListGraph::EdgeMap<int> ECostMap; |
64 typedef ListGraph::EdgeMap<int> ECostMap; |
41 typedef ListGraph::EdgeMap<bool> EBoolMap; |
65 typedef ListGraph::EdgeMap<bool> EBoolMap; |
42 |
66 |
43 ECostMap edge_cost_map(G, 2); |
67 ECostMap edge_cost_map(g, 2); |
44 EBoolMap tree_map(G); |
68 EBoolMap tree_map(g); |
45 |
|
46 |
69 |
47 //Test with const map. |
70 // Kruskal. |
48 std::cout << "The weight of the minimum spanning tree is " << kruskalEdgeMap(G, ConstMap<ListGraph::Edge,int>(2), tree_map)<<std::endl; |
71 std::cout << "The weight of the minimum spanning tree by using Kruskal algorithm is " |
|
72 << kruskal(g, ConstMap<ListGraph::Edge,int>(2), tree_map)<<std::endl; |
49 |
73 |
50 /* |
74 //Make another input (non-uniform costs) for the kruskal. |
51 ==10, |
75 ECostMap edge_cost_map_2(g); |
52 "Total cost should be 10"); |
76 edge_cost_map_2.set(e1, -10); |
53 //Test with a edge map (filled with uniform costs). |
77 edge_cost_map_2.set(e2, -9); |
54 check(kruskalEdgeMap(G, edge_cost_map, tree_map)==10, |
78 edge_cost_map_2.set(e3, -8); |
55 "Total cost should be 10"); |
79 edge_cost_map_2.set(e4, -7); |
56 |
80 edge_cost_map_2.set(e5, -6); |
57 edge_cost_map.set(e1, -10); |
81 edge_cost_map_2.set(e6, -5); |
58 edge_cost_map.set(e2, -9); |
82 edge_cost_map_2.set(e7, -4); |
59 edge_cost_map.set(e3, -8); |
83 edge_cost_map_2.set(e8, -3); |
60 edge_cost_map.set(e4, -7); |
84 edge_cost_map_2.set(e9, -2); |
61 edge_cost_map.set(e5, -6); |
85 edge_cost_map_2.set(e10, -1); |
62 edge_cost_map.set(e6, -5); |
|
63 edge_cost_map.set(e7, -4); |
|
64 edge_cost_map.set(e8, -3); |
|
65 edge_cost_map.set(e9, -2); |
|
66 edge_cost_map.set(e10, -1); |
|
67 |
86 |
68 vector<Edge> tree_edge_vec; |
87 vector<Edge> tree_edge_vec; |
69 |
88 |
70 //Test with a edge map and inserter. |
89 //Test with non uniform costs and inserter. |
71 check(kruskalEdgeMap_IteratorOut(G, edge_cost_map, |
90 std::cout << "The weight of the minimum spanning tree with non-uniform costs is " << |
72 back_inserter(tree_edge_vec)) |
91 kruskal(g, edge_cost_map_2, std::back_inserter(tree_edge_vec)) <<std::endl; |
73 ==-31, |
|
74 "Total cost should be -31."); |
|
75 |
92 |
|
93 //The vector for the edges of the output tree. |
76 tree_edge_vec.clear(); |
94 tree_edge_vec.clear(); |
77 |
95 |
78 //The above test could also be coded like this: |
96 //Test with makeKruskalSequenceOutput and makeKruskalSequenceOutput. |
79 check(kruskal(G, |
|
80 makeKruskalMapInput(G, edge_cost_map), |
|
81 makeKruskalSequenceOutput(back_inserter(tree_edge_vec))) |
|
82 ==-31, |
|
83 "Total cost should be -31."); |
|
84 |
97 |
85 check(tree_edge_vec.size()==5,"The tree should have 5 edges."); |
98 std::cout << "The weight of the minimum spanning tree again is " << |
|
99 kruskal(g,makeKruskalMapInput(g,edge_cost_map_2),makeKruskalSequenceOutput(std::back_inserter(tree_edge_vec)))<< std::endl; |
86 |
100 |
87 check(tree_edge_vec[0]==e1 && |
101 |
88 tree_edge_vec[1]==e2 && |
|
89 tree_edge_vec[2]==e5 && |
|
90 tree_edge_vec[3]==e7 && |
|
91 tree_edge_vec[4]==e9, |
|
92 "Wrong tree."); |
|
93 */ |
|
94 return 0; |
102 return 0; |
95 } |
103 } |