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 +}