58 Edge e7 = g.addEdge(v2, v4); |
58 Edge e7 = g.addEdge(v2, v4); |
59 Edge e8 = g.addEdge(v4, v3); |
59 Edge e8 = g.addEdge(v4, v3); |
60 Edge e9 = g.addEdge(v3, t); |
60 Edge e9 = g.addEdge(v3, t); |
61 Edge e10 = g.addEdge(v4, t); |
61 Edge e10 = g.addEdge(v4, t); |
62 |
62 |
63 //Make the input and output for the kruskal. |
63 //Make the input for the kruskal. |
64 typedef ListGraph::EdgeMap<int> ECostMap; |
64 typedef ListGraph::EdgeMap<int> ECostMap; |
|
65 ECostMap edge_cost_map(g); |
|
66 |
|
67 // Fill the edge_cost_map. |
|
68 edge_cost_map.set(e1, -10); |
|
69 edge_cost_map.set(e2, -9); |
|
70 edge_cost_map.set(e3, -8); |
|
71 edge_cost_map.set(e4, -7); |
|
72 edge_cost_map.set(e5, -6); |
|
73 edge_cost_map.set(e6, -5); |
|
74 edge_cost_map.set(e7, -4); |
|
75 edge_cost_map.set(e8, -3); |
|
76 edge_cost_map.set(e9, -2); |
|
77 edge_cost_map.set(e10, -1); |
|
78 |
|
79 // Make the map or the vector, which will contain the edges of the minimum |
|
80 // spanning tree. |
|
81 |
65 typedef ListGraph::EdgeMap<bool> EBoolMap; |
82 typedef ListGraph::EdgeMap<bool> EBoolMap; |
66 |
|
67 ECostMap edge_cost_map(g, 2); |
|
68 EBoolMap tree_map(g); |
83 EBoolMap tree_map(g); |
69 |
|
70 // Kruskal. |
|
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; |
|
73 |
|
74 //Make another input (non-uniform costs) for the kruskal. |
|
75 ECostMap edge_cost_map_2(g); |
|
76 edge_cost_map_2.set(e1, -10); |
|
77 edge_cost_map_2.set(e2, -9); |
|
78 edge_cost_map_2.set(e3, -8); |
|
79 edge_cost_map_2.set(e4, -7); |
|
80 edge_cost_map_2.set(e5, -6); |
|
81 edge_cost_map_2.set(e6, -5); |
|
82 edge_cost_map_2.set(e7, -4); |
|
83 edge_cost_map_2.set(e8, -3); |
|
84 edge_cost_map_2.set(e9, -2); |
|
85 edge_cost_map_2.set(e10, -1); |
|
86 |
84 |
87 vector<Edge> tree_edge_vec; |
85 vector<Edge> tree_edge_vec; |
88 |
86 |
89 //Test with non uniform costs and inserter. |
|
90 std::cout << "The weight of the minimum spanning tree with non-uniform costs is " << |
|
91 kruskal(g, edge_cost_map_2, std::back_inserter(tree_edge_vec)) <<std::endl; |
|
92 |
87 |
93 //The vector for the edges of the output tree. |
88 //Kruskal Algorithm. |
94 tree_edge_vec.clear(); |
|
95 |
89 |
96 //Test with makeKruskalMapInput and makeKruskalSequenceOutput. |
90 //Input: a graph (g); a costmap of the graph (edge_cost_map); a |
|
91 //boolmap (tree_map) or a vector (tree_edge_vec) to store the edges |
|
92 //of the output tree; |
97 |
93 |
98 std::cout << "The weight of the minimum spanning tree again is " << |
94 //Output: it gives back the value of the minimum spanning tree, and |
99 kruskal(g,makeKruskalMapInput(g,edge_cost_map_2),makeKruskalSequenceOutput(std::back_inserter(tree_edge_vec)))<< std::endl; |
95 //set true for the edges of the tree in the edgemap tree_map or |
|
96 //store the edges of the tree in the vector tree_edge_vec; |
100 |
97 |
101 |
98 |
|
99 // Kruskal with boolmap; |
|
100 std::cout << "The weight of the minimum spanning tree is " << |
|
101 kruskal(g, edge_cost_map, tree_map)<<std::endl; |
|
102 |
|
103 int k=0; |
|
104 std::cout << "The edges of the tree:" ; |
|
105 for(EdgeIt i(g); i!=INVALID; ++i){ |
|
106 |
|
107 if (tree_map[i]) { |
|
108 std::cout << g.id(i) <<";"; |
|
109 ++k; |
|
110 } |
|
111 } |
|
112 std::cout << std::endl; |
|
113 std::cout << "The size of the tree is: "<< k << std::endl; |
|
114 |
|
115 |
|
116 // Kruskal with vector; |
|
117 std::cout << "The weight of the minimum spanning tree again is " << |
|
118 kruskal(g, edge_cost_map, std::back_inserter(tree_edge_vec)) <<std::endl; |
|
119 |
|
120 |
|
121 |
|
122 std::cout << "The edges of the tree again: " ; |
|
123 for(int i=tree_edge_vec.size()-1; i>=0; i--) |
|
124 std::cout << g.id(tree_edge_vec[i]) << ";" ; |
|
125 std::cout << std::endl; |
|
126 std::cout << "The size of the tree again is: "<< tree_edge_vec.size()<< std::endl; |
|
127 |
|
128 |
102 return 0; |
129 return 0; |
103 } |
130 } |