1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/test/unionfind_test.cc Fri Feb 29 11:01:39 2008 +0000
1.3 @@ -0,0 +1,114 @@
1.4 +/* -*- C++ -*-
1.5 + *
1.6 + * This file is a part of LEMON, a generic C++ optimization library
1.7 + *
1.8 + * Copyright (C) 2003-2008
1.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.11 + *
1.12 + * Permission to use, modify and distribute this software is granted
1.13 + * provided that this copyright notice appears in all copies. For
1.14 + * precise terms see the accompanying LICENSE file.
1.15 + *
1.16 + * This software is provided "AS IS" with no warranty of any kind,
1.17 + * express or implied, and with no claim as to its suitability for any
1.18 + * purpose.
1.19 + *
1.20 + */
1.21 +
1.22 +#include <iostream>
1.23 +
1.24 +#include <lemon/maps.h>
1.25 +#include <lemon/unionfind.h>
1.26 +#include "test_tools.h"
1.27 +
1.28 +using namespace lemon;
1.29 +using namespace std;
1.30 +
1.31 +typedef UnionFindEnum<StdMap<int, int> > UFE;
1.32 +
1.33 +void print(UFE const &ufe) {
1.34 + cout << "Print the classes of the structure:" << endl;
1.35 + int i = 1;
1.36 + for (UFE::ClassIt cit(ufe); cit != INVALID; ++cit) {
1.37 + cout << " " << i << " (" << cit << "):" << flush;
1.38 + for (UFE::ItemIt iit(ufe, cit); iit != INVALID; ++iit) {
1.39 + cout << " " << iit << flush;
1.40 + }
1.41 + cout << endl;
1.42 + i++;
1.43 + }
1.44 + cout << "done" << endl;
1.45 +}
1.46 +
1.47 +
1.48 +int main() {
1.49 + StdMap<int, int> base;
1.50 + UFE U(base);
1.51 +
1.52 + U.insert(1);
1.53 + U.insert(2);
1.54 +
1.55 + check(U.join(1,2) != -1,"Test failed.");
1.56 +
1.57 + U.insert(3);
1.58 + U.insert(4);
1.59 + U.insert(5);
1.60 + U.insert(6);
1.61 + U.insert(7);
1.62 +
1.63 +
1.64 + check(U.join(1,4) != -1,"Test failed.");
1.65 + check(U.join(2,4) == -1,"Test failed.");
1.66 + check(U.join(3,5) != -1,"Test failed.");
1.67 +
1.68 +
1.69 + U.insert(8,U.find(5));
1.70 +
1.71 +
1.72 + check(U.size(U.find(4)) == 3,"Test failed.");
1.73 + check(U.size(U.find(5)) == 3,"Test failed.");
1.74 + check(U.size(U.find(6)) == 1,"Test failed.");
1.75 + check(U.size(U.find(2)) == 3,"Test failed.");
1.76 +
1.77 +
1.78 + U.insert(9);
1.79 + U.insert(10,U.find(9));
1.80 +
1.81 +
1.82 + check(U.join(8,10) != -1,"Test failed.");
1.83 +
1.84 +
1.85 + check(U.size(U.find(4)) == 3,"Test failed.");
1.86 + check(U.size(U.find(9)) == 5,"Test failed.");
1.87 +
1.88 + check(U.size(U.find(8)) == 5,"Test failed.");
1.89 +
1.90 + U.erase(9);
1.91 + U.erase(1);
1.92 +
1.93 + check(U.size(U.find(10)) == 4,"Test failed.");
1.94 + check(U.size(U.find(2)) == 2,"Test failed.");
1.95 +
1.96 + U.erase(6);
1.97 + U.split(U.find(8));
1.98 +
1.99 +
1.100 + check(U.size(U.find(4)) == 2,"Test failed.");
1.101 + check(U.size(U.find(3)) == 1,"Test failed.");
1.102 + check(U.size(U.find(2)) == 2,"Test failed.");
1.103 +
1.104 +
1.105 + check(U.join(3,4) != -1,"Test failed.");
1.106 + check(U.join(2,4) == -1,"Test failed.");
1.107 +
1.108 +
1.109 + check(U.size(U.find(4)) == 3,"Test failed.");
1.110 + check(U.size(U.find(3)) == 3,"Test failed.");
1.111 + check(U.size(U.find(2)) == 3,"Test failed.");
1.112 +
1.113 + U.eraseClass(U.find(4));
1.114 + U.eraseClass(U.find(7));
1.115 +
1.116 + return 0;
1.117 +}