16 * |
16 * |
17 */ |
17 */ |
18 |
18 |
19 #include <iostream> |
19 #include <iostream> |
20 |
20 |
|
21 #include <lemon/list_graph.h> |
21 #include <lemon/maps.h> |
22 #include <lemon/maps.h> |
22 #include <lemon/unionfind.h> |
23 #include <lemon/unionfind.h> |
23 #include "test_tools.h" |
24 #include "test_tools.h" |
24 |
25 |
25 using namespace lemon; |
26 using namespace lemon; |
26 using namespace std; |
27 using namespace std; |
27 |
28 |
28 typedef UnionFindEnum<StdMap<int, int> > UFE; |
29 typedef UnionFindEnum<ListGraph::NodeMap<int> > UFE; |
29 |
30 |
30 void print(UFE const &ufe) { |
31 int main() { |
31 cout << "Print the classes of the structure:" << endl; |
32 ListGraph g; |
32 int i = 1; |
33 ListGraph::NodeMap<int> base(g); |
33 for (UFE::ClassIt cit(ufe); cit != INVALID; ++cit) { |
34 UFE U(base); |
34 cout << " " << i << " (" << cit << "):" << flush; |
35 vector<ListGraph::Node> n; |
35 for (UFE::ItemIt iit(ufe, cit); iit != INVALID; ++iit) { |
36 |
36 cout << " " << iit << flush; |
37 for(int i=0;i<20;i++) n.push_back(g.addNode()); |
37 } |
38 |
38 cout << endl; |
39 U.insert(n[1]); |
39 i++; |
40 U.insert(n[2]); |
40 } |
41 |
41 cout << "done" << endl; |
42 check(U.join(n[1],n[2]) != -1,"Test failed."); |
42 } |
43 |
|
44 U.insert(n[3]); |
|
45 U.insert(n[4]); |
|
46 U.insert(n[5]); |
|
47 U.insert(n[6]); |
|
48 U.insert(n[7]); |
43 |
49 |
44 |
50 |
45 int main() { |
51 check(U.join(n[1],n[4]) != -1,"Test failed."); |
46 StdMap<int, int> base; |
52 check(U.join(n[2],n[4]) == -1,"Test failed."); |
47 UFE U(base); |
53 check(U.join(n[3],n[5]) != -1,"Test failed."); |
48 |
|
49 U.insert(1); |
|
50 U.insert(2); |
|
51 |
|
52 check(U.join(1,2) != -1,"Test failed."); |
|
53 |
|
54 U.insert(3); |
|
55 U.insert(4); |
|
56 U.insert(5); |
|
57 U.insert(6); |
|
58 U.insert(7); |
|
59 |
54 |
60 |
55 |
61 check(U.join(1,4) != -1,"Test failed."); |
56 U.insert(n[8],U.find(n[5])); |
62 check(U.join(2,4) == -1,"Test failed."); |
|
63 check(U.join(3,5) != -1,"Test failed."); |
|
64 |
57 |
65 |
58 |
66 U.insert(8,U.find(5)); |
59 check(U.size(U.find(n[4])) == 3,"Test failed."); |
|
60 check(U.size(U.find(n[5])) == 3,"Test failed."); |
|
61 check(U.size(U.find(n[6])) == 1,"Test failed."); |
|
62 check(U.size(U.find(n[2])) == 3,"Test failed."); |
67 |
63 |
68 |
64 |
69 check(U.size(U.find(4)) == 3,"Test failed."); |
65 U.insert(n[9]); |
70 check(U.size(U.find(5)) == 3,"Test failed."); |
66 U.insert(n[10],U.find(n[9])); |
71 check(U.size(U.find(6)) == 1,"Test failed."); |
|
72 check(U.size(U.find(2)) == 3,"Test failed."); |
|
73 |
67 |
74 |
68 |
75 U.insert(9); |
69 check(U.join(n[8],n[10]) != -1,"Test failed."); |
76 U.insert(10,U.find(9)); |
|
77 |
70 |
78 |
71 |
79 check(U.join(8,10) != -1,"Test failed."); |
72 check(U.size(U.find(n[4])) == 3,"Test failed."); |
|
73 check(U.size(U.find(n[9])) == 5,"Test failed."); |
|
74 |
|
75 check(U.size(U.find(n[8])) == 5,"Test failed."); |
|
76 |
|
77 U.erase(n[9]); |
|
78 U.erase(n[1]); |
|
79 |
|
80 check(U.size(U.find(n[10])) == 4,"Test failed."); |
|
81 check(U.size(U.find(n[2])) == 2,"Test failed."); |
|
82 |
|
83 U.erase(n[6]); |
|
84 U.split(U.find(n[8])); |
80 |
85 |
81 |
86 |
82 check(U.size(U.find(4)) == 3,"Test failed."); |
87 check(U.size(U.find(n[4])) == 2,"Test failed."); |
83 check(U.size(U.find(9)) == 5,"Test failed."); |
88 check(U.size(U.find(n[3])) == 1,"Test failed."); |
84 |
89 check(U.size(U.find(n[2])) == 2,"Test failed."); |
85 check(U.size(U.find(8)) == 5,"Test failed."); |
|
86 |
|
87 U.erase(9); |
|
88 U.erase(1); |
|
89 |
|
90 check(U.size(U.find(10)) == 4,"Test failed."); |
|
91 check(U.size(U.find(2)) == 2,"Test failed."); |
|
92 |
|
93 U.erase(6); |
|
94 U.split(U.find(8)); |
|
95 |
90 |
96 |
91 |
97 check(U.size(U.find(4)) == 2,"Test failed."); |
92 check(U.join(n[3],n[4]) != -1,"Test failed."); |
98 check(U.size(U.find(3)) == 1,"Test failed."); |
93 check(U.join(n[2],n[4]) == -1,"Test failed."); |
99 check(U.size(U.find(2)) == 2,"Test failed."); |
|
100 |
94 |
101 |
95 |
102 check(U.join(3,4) != -1,"Test failed."); |
96 check(U.size(U.find(n[4])) == 3,"Test failed."); |
103 check(U.join(2,4) == -1,"Test failed."); |
97 check(U.size(U.find(n[3])) == 3,"Test failed."); |
|
98 check(U.size(U.find(n[2])) == 3,"Test failed."); |
104 |
99 |
105 |
100 U.eraseClass(U.find(n[4])); |
106 check(U.size(U.find(4)) == 3,"Test failed."); |
101 U.eraseClass(U.find(n[7])); |
107 check(U.size(U.find(3)) == 3,"Test failed."); |
|
108 check(U.size(U.find(2)) == 3,"Test failed."); |
|
109 |
|
110 U.eraseClass(U.find(4)); |
|
111 U.eraseClass(U.find(7)); |
|
112 |
102 |
113 return 0; |
103 return 0; |
114 } |
104 } |