1.1 --- a/src/test/unionfind_test.cc Sat May 21 21:04:57 2005 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,208 +0,0 @@
1.4 -/* -*- C++ -*-
1.5 - * src/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 -}