Several changes. \n If new map is added to mapstorage it emits signal with the name of the new map. This was important, because from now on not only tha mapwin should be updated. \n Furthermore algobox gets a pointer to mapstorage instead of only the mapnames from it. This is important because without it it would be complicated to pass all of the required maps to algobox.
2 * test/kruskal_test.cc - Part of LEMON, a generic C++ optimization library
4 * Copyright (C) 2006 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5 * (Egervary Research Group on Combinatorial Optimization, EGRES).
7 * Permission to use, modify and distribute this software is granted
8 * provided that this copyright notice appears in all copies. For
9 * precise terms see the accompanying LICENSE file.
11 * This software is provided "AS IS" with no warranty of any kind,
12 * express or implied, and with no claim as to its suitability for any
20 #include "test_tools.h"
21 #include <lemon/maps.h>
22 #include <lemon/kruskal.h>
23 #include <lemon/list_graph.h>
24 #include <lemon/concept/maps.h>
25 #include <lemon/concept/graph.h>
29 using namespace lemon;
31 void checkCompileKruskal()
33 concept::WriteMap<concept::StaticGraph::Edge,bool> w;
35 kruskal(concept::StaticGraph(),
36 concept::ReadMap<concept::StaticGraph::Edge,int>(),
42 typedef ListGraph::Node Node;
43 typedef ListGraph::Edge Edge;
44 typedef ListGraph::NodeIt NodeIt;
45 typedef ListGraph::EdgeIt EdgeIt;
56 Edge e1 = G.addEdge(s, v1);
57 Edge e2 = G.addEdge(s, v2);
58 Edge e3 = G.addEdge(v1, v2);
59 Edge e4 = G.addEdge(v2, v1);
60 Edge e5 = G.addEdge(v1, v3);
61 Edge e6 = G.addEdge(v3, v2);
62 Edge e7 = G.addEdge(v2, v4);
63 Edge e8 = G.addEdge(v4, v3);
64 Edge e9 = G.addEdge(v3, t);
65 Edge e10 = G.addEdge(v4, t);
67 typedef ListGraph::EdgeMap<int> ECostMap;
68 typedef ListGraph::EdgeMap<bool> EBoolMap;
70 ECostMap edge_cost_map(G, 2);
74 //Test with const map.
75 check(kruskal(G, ConstMap<ListGraph::Edge,int>(2), tree_map)==10,
76 "Total cost should be 10");
77 //Test with a edge map (filled with uniform costs).
78 check(kruskal(G, edge_cost_map, tree_map)==10,
79 "Total cost should be 10");
81 edge_cost_map.set(e1, -10);
82 edge_cost_map.set(e2, -9);
83 edge_cost_map.set(e3, -8);
84 edge_cost_map.set(e4, -7);
85 edge_cost_map.set(e5, -6);
86 edge_cost_map.set(e6, -5);
87 edge_cost_map.set(e7, -4);
88 edge_cost_map.set(e8, -3);
89 edge_cost_map.set(e9, -2);
90 edge_cost_map.set(e10, -1);
92 vector<Edge> tree_edge_vec(5);
94 //Test with a edge map and inserter.
95 check(kruskal(G, edge_cost_map,
96 tree_edge_vec.begin())
98 "Total cost should be -31.");
100 tree_edge_vec.clear();
102 check(kruskal(G, edge_cost_map,
103 back_inserter(tree_edge_vec))
105 "Total cost should be -31.");
107 tree_edge_vec.clear();
109 //The above test could also be coded like this:
111 makeKruskalMapInput(G, edge_cost_map),
112 makeKruskalSequenceOutput(back_inserter(tree_edge_vec)))
114 "Total cost should be -31.");
116 check(tree_edge_vec.size()==5,"The tree should have 5 edges.");
118 check(tree_edge_vec[0]==e1 &&
119 tree_edge_vec[1]==e2 &&
120 tree_edge_vec[2]==e5 &&
121 tree_edge_vec[3]==e7 &&
122 tree_edge_vec[4]==e9,