1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/test/unionfind_test.cc Mon May 23 04:48:14 2005 +0000
1.3 @@ -0,0 +1,208 @@
1.4 +/* -*- C++ -*-
1.5 + * test/unionfind_test.cc - Part of LEMON, a generic C++ optimization library
1.6 + *
1.7 + * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.8 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.9 + *
1.10 + * Permission to use, modify and distribute this software is granted
1.11 + * provided that this copyright notice appears in all copies. For
1.12 + * precise terms see the accompanying LICENSE file.
1.13 + *
1.14 + * This software is provided "AS IS" with no warranty of any kind,
1.15 + * express or implied, and with no claim as to its suitability for any
1.16 + * purpose.
1.17 + *
1.18 + */
1.19 +
1.20 +#include <iostream>
1.21 +
1.22 +#include <lemon/maps.h>
1.23 +#include <lemon/unionfind.h>
1.24 +#include "test_tools.h"
1.25 +
1.26 +using namespace lemon;
1.27 +using namespace std;
1.28 +
1.29 +template <typename T>
1.30 +class BaseMap : public StdMap<int,T> {};
1.31 +
1.32 +typedef UnionFindEnum<int, BaseMap> UFE;
1.33 +
1.34 +void print(UFE const &ufe) {
1.35 + UFE::ClassIt cit;
1.36 + cout << "Print the classes of the structure:" << endl;
1.37 + int i = 1;
1.38 + for (ufe.first(cit); ufe.valid(cit); ufe.next(cit)) {
1.39 + cout << " " << i << " (" << cit << "):" << flush;
1.40 + UFE::ItemIt iit;
1.41 + for (ufe.first(iit, cit); ufe.valid(iit); ufe.next(iit)) {
1.42 + cout << " " << iit << flush;
1.43 + }
1.44 + cout << endl;
1.45 + i++;
1.46 + }
1.47 + cout << "done" << endl;
1.48 +}
1.49 +
1.50 +
1.51 +int main() {
1.52 + UFE::MapType base;
1.53 + UFE U(base);
1.54 +
1.55 +// print(U);
1.56 +
1.57 + cout << "Insert 1..." << endl;
1.58 + U.insert(1);
1.59 +// print(U);
1.60 +
1.61 + cout << "Insert 2..." << endl;
1.62 + U.insert(2);
1.63 +// print(U);
1.64 +
1.65 + cout << "Join 1 and 2..." << endl;
1.66 + check(U.join(1,2),"Test failed.");
1.67 +// print(U);
1.68 +
1.69 + cout << "Insert 3, 4, 5, 6, 7..." << endl;
1.70 + U.insert(3);
1.71 + U.insert(4);
1.72 + U.insert(5);
1.73 + U.insert(6);
1.74 + U.insert(7);
1.75 +// print (U);
1.76 +
1.77 + cout << "Join 1 - 4, 2 - 4 and 3 - 5 ..." << endl;
1.78 + check(U.join(1,4),"Test failed.");
1.79 + check(!U.join(2,4),"Test failed.");
1.80 + check(U.join(3,5),"Test failed.");
1.81 +// print(U);
1.82 +
1.83 + cout << "Insert 8 to the component of 5 ..." << endl;
1.84 + U.insert(8,5);
1.85 +// print(U);
1.86 +
1.87 + cout << "Size of the class of 4: " << U.size(4) << endl;
1.88 + check(U.size(4) == 3,"Test failed.");
1.89 + cout << "Size of the class of 5: " << U.size(5) << endl;
1.90 + check(U.size(5) == 3,"Test failed.");
1.91 + cout << "Size of the class of 6: " << U.size(6) << endl;
1.92 + check(U.size(6) == 1,"Test failed.");
1.93 + cout << "Size of the class of 2: " << U.size(2) << endl;
1.94 + check(U.size(2) == 3,"Test failed.");
1.95 +
1.96 + cout << "Insert 9 ..." << endl;
1.97 + U.insert(9);
1.98 +// print(U);
1.99 + cout << "Insert 10 to the component of 9 ..." << endl;
1.100 + U.insert(10,9);
1.101 +// print(U);
1.102 +
1.103 + cout << "Join 8 and 10..." << endl;
1.104 + check(U.join(8,10),"Test failed.");
1.105 +// print(U);
1.106 +
1.107 + cout << "Move 9 to the class of 4 ..." << endl;
1.108 + check(U.move(9,4),"Test failed.");
1.109 +// print(U);
1.110 +
1.111 + cout << "Move 9 to the class of 2 ..." << endl;
1.112 + check(!U.move(9,2),"Test failed.");
1.113 +// print(U);
1.114 +
1.115 + cout << "Size of the class of 4: " << U.size(4) << endl;
1.116 + check(U.size(4) == 4,"Test failed.");
1.117 + cout << "Size of the class of 9: " << U.size(9) << endl;
1.118 + check(U.size(9) == 4,"Test failed.");
1.119 +
1.120 + cout << "Move 5 to the class of 6 ..." << endl;
1.121 + check(U.move(5,6),"Test failed.");
1.122 +// print(U);
1.123 +
1.124 + cout << "Size of the class of 5: " << U.size(5) << endl;
1.125 + check(U.size(5) == 2,"Test failed.");
1.126 + cout << "Size of the class of 8: " << U.size(8) << endl;
1.127 + check(U.size(8) == 3,"Test failed.");
1.128 +
1.129 + cout << "Move 7 to the class of 10 ..." << endl;
1.130 + check(U.move(7,10),"Test failed.");
1.131 +// print(U);
1.132 +
1.133 + cout << "Size of the class of 7: " << U.size(7) << endl;
1.134 + check(U.size(7) == 4,"Test failed.");
1.135 +
1.136 + cout <<"Erase 9... " << endl;
1.137 + U.erase(9);
1.138 +// print(U);
1.139 +
1.140 + cout <<"Erase 1... " << endl;
1.141 + U.erase(1);
1.142 +// print(U);
1.143 +
1.144 + cout << "Size of the class of 4: " << U.size(4) << endl;
1.145 + check(U.size(4) == 2,"Test failed.");
1.146 + cout << "Size of the class of 2: " << U.size(2) << endl;
1.147 + check(U.size(2) == 2,"Test failed.");
1.148 +
1.149 +
1.150 + cout <<"Erase 1... " << endl;
1.151 + U.erase(1);
1.152 +// print(U);
1.153 +
1.154 + cout <<"Erase 6... " << endl;
1.155 + U.erase(6);
1.156 +// print(U);
1.157 +
1.158 + cout << "Split the class of 8... " << endl;
1.159 + U.split(8);
1.160 +// print(U);
1.161 +
1.162 +
1.163 + cout << "Size of the class of 4: " << U.size(4) << endl;
1.164 + check(U.size(4) == 2,"Test failed.");
1.165 + cout << "Size of the class of 3: " << U.size(3) << endl;
1.166 + check(U.size(3) == 1,"Test failed.");
1.167 + cout << "Size of the class of 2: " << U.size(2) << endl;
1.168 + check(U.size(2) == 2,"Test failed.");
1.169 +
1.170 +
1.171 + cout << "Join 3 - 4 and 2 - 4 ..." << endl;
1.172 + check(U.join(3,4),"Test failed.");
1.173 + check(!U.join(2,4),"Test failed.");
1.174 +// print(U);
1.175 +
1.176 +
1.177 + cout << "Size of the class of 4: " << U.size(4) << endl;
1.178 + check(U.size(4) == 3,"Test failed.");
1.179 + cout << "Size of the class of 3: " << U.size(3) << endl;
1.180 + check(U.size(3) == 3,"Test failed.");
1.181 + cout << "Size of the class of 2: " << U.size(2) << endl;
1.182 + check(U.size(2) == 3,"Test failed.");
1.183 +
1.184 + cout << "Calling makeRep(4)..." << endl;
1.185 + U.makeRep(4);
1.186 +// print(U);
1.187 + cout << "Calling makeRep(3)..." << endl;
1.188 + U.makeRep(3);
1.189 +// print(U);
1.190 + cout << "Calling makeRep(2)..." << endl;
1.191 + U.makeRep(2);
1.192 +// print(U);
1.193 +
1.194 + cout << "Size of the class of 4: " << U.size(4) << endl;
1.195 + check(U.size(4) == 3,"Test failed.");
1.196 + cout << "Size of the class of 3: " << U.size(3) << endl;
1.197 + check(U.size(3) == 3,"Test failed.");
1.198 + cout << "Size of the class of 2: " << U.size(2) << endl;
1.199 + check(U.size(2) == 3,"Test failed.");
1.200 +
1.201 +
1.202 + cout << "eraseClass 4 ..." << endl;
1.203 + U.eraseClass(4);
1.204 +// print(U);
1.205 +
1.206 + cout << "eraseClass 7 ..." << endl;
1.207 + U.eraseClass(7);
1.208 +// print(U);
1.209 +
1.210 + cout << "done." << endl;
1.211 +}