src/test/unionfind_test.cc
author deba
Wed, 18 May 2005 13:02:47 +0000
changeset 1427 14c75970840e
parent 1164 80bb73097736
permissions -rw-r--r--
Two minor changes.

DefaultReader<std::string>
comment lines
     1 /* -*- C++ -*-
     2  * src/test/unionfind_test.cc - Part of LEMON, a generic C++ optimization library
     3  *
     4  * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     5  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     6  *
     7  * Permission to use, modify and distribute this software is granted
     8  * provided that this copyright notice appears in all copies. For
     9  * precise terms see the accompanying LICENSE file.
    10  *
    11  * This software is provided "AS IS" with no warranty of any kind,
    12  * express or implied, and with no claim as to its suitability for any
    13  * purpose.
    14  *
    15  */
    16 
    17 #include <iostream>
    18 
    19 #include <lemon/maps.h>
    20 #include <lemon/unionfind.h>
    21 #include "test_tools.h"
    22 
    23 using namespace lemon;
    24 using namespace std;
    25 
    26 template <typename T>
    27 class BaseMap : public StdMap<int,T> {};
    28 
    29 typedef UnionFindEnum<int, BaseMap> UFE;
    30 
    31 void print(UFE const &ufe) {
    32   UFE::ClassIt cit;
    33   cout << "Print the classes of the structure:" << endl;
    34   int i = 1;
    35   for (ufe.first(cit); ufe.valid(cit); ufe.next(cit)) {
    36     cout << "  " << i << " (" << cit << "):" << flush;
    37     UFE::ItemIt iit;
    38     for (ufe.first(iit, cit); ufe.valid(iit); ufe.next(iit)) {
    39       cout << " " << iit << flush;
    40     }
    41     cout << endl;
    42     i++;
    43   }
    44   cout << "done" << endl;
    45 }
    46 
    47 
    48 int main() {
    49   UFE::MapType base;
    50   UFE U(base);
    51 
    52 //   print(U);
    53 
    54   cout << "Insert 1..." << endl;
    55   U.insert(1);
    56 //   print(U);
    57   
    58   cout << "Insert 2..." << endl;
    59   U.insert(2);
    60 //   print(U);
    61   
    62   cout << "Join 1 and 2..." << endl;
    63   check(U.join(1,2),"Test failed.");
    64 //   print(U);
    65 
    66   cout << "Insert 3, 4, 5, 6, 7..." << endl;
    67   U.insert(3);
    68   U.insert(4);
    69   U.insert(5);
    70   U.insert(6);
    71   U.insert(7);
    72 //   print (U);
    73 
    74   cout << "Join 1 - 4, 2 - 4 and 3 - 5 ..." << endl;
    75   check(U.join(1,4),"Test failed.");
    76   check(!U.join(2,4),"Test failed.");
    77   check(U.join(3,5),"Test failed.");
    78 //   print(U);
    79 
    80   cout << "Insert 8 to the component of 5 ..." << endl;
    81   U.insert(8,5);
    82 //   print(U);
    83 
    84   cout << "Size of the class of 4: " << U.size(4) << endl;
    85   check(U.size(4) == 3,"Test failed.");
    86   cout << "Size of the class of 5: " << U.size(5) << endl;
    87   check(U.size(5) == 3,"Test failed.");
    88   cout << "Size of the class of 6: " << U.size(6) << endl;
    89   check(U.size(6) == 1,"Test failed.");
    90   cout << "Size of the class of 2: " << U.size(2) << endl;
    91   check(U.size(2) == 3,"Test failed.");
    92 
    93   cout << "Insert 9 ..." << endl;
    94   U.insert(9);
    95 //   print(U);
    96   cout << "Insert 10 to the component of 9 ..." << endl;
    97   U.insert(10,9);
    98 //   print(U);
    99 
   100   cout << "Join 8 and 10..." << endl;
   101   check(U.join(8,10),"Test failed.");
   102 //   print(U);
   103 
   104   cout << "Move 9 to the class of 4 ..." << endl;
   105   check(U.move(9,4),"Test failed.");
   106 //   print(U);
   107 
   108   cout << "Move 9 to the class of 2 ..." << endl;
   109   check(!U.move(9,2),"Test failed.");
   110 //   print(U);
   111 
   112   cout << "Size of the class of 4: " << U.size(4) << endl;
   113   check(U.size(4) == 4,"Test failed.");
   114   cout << "Size of the class of 9: " << U.size(9) << endl;
   115   check(U.size(9) == 4,"Test failed.");
   116   
   117   cout << "Move 5 to the class of 6 ..." << endl;
   118   check(U.move(5,6),"Test failed.");
   119 //   print(U);
   120 
   121   cout << "Size of the class of 5: " << U.size(5) << endl;
   122   check(U.size(5) == 2,"Test failed.");
   123   cout << "Size of the class of 8: " << U.size(8) << endl;
   124   check(U.size(8) == 3,"Test failed.");
   125 
   126   cout << "Move 7 to the class of 10 ..." << endl;
   127   check(U.move(7,10),"Test failed.");
   128 //   print(U);
   129 
   130   cout << "Size of the class of 7: " << U.size(7) << endl;
   131   check(U.size(7) == 4,"Test failed.");
   132 
   133   cout <<"Erase 9... " << endl;
   134   U.erase(9);
   135 //   print(U);
   136 
   137   cout <<"Erase 1... " << endl;
   138   U.erase(1);
   139 //   print(U);
   140 
   141   cout << "Size of the class of 4: " << U.size(4) << endl;
   142   check(U.size(4) == 2,"Test failed.");
   143   cout << "Size of the class of 2: " << U.size(2) << endl;
   144   check(U.size(2) == 2,"Test failed.");
   145 
   146 
   147   cout <<"Erase 1... " << endl;
   148   U.erase(1);
   149 //   print(U);
   150 
   151   cout <<"Erase 6... " << endl;
   152   U.erase(6);
   153 //   print(U);
   154 
   155   cout << "Split the class of 8... " << endl;
   156   U.split(8);
   157 //   print(U);
   158 
   159 
   160   cout << "Size of the class of 4: " << U.size(4) << endl;
   161   check(U.size(4) == 2,"Test failed.");
   162   cout << "Size of the class of 3: " << U.size(3) << endl;
   163   check(U.size(3) == 1,"Test failed.");
   164   cout << "Size of the class of 2: " << U.size(2) << endl;
   165   check(U.size(2) == 2,"Test failed.");
   166 
   167 
   168   cout << "Join 3 - 4 and 2 - 4 ..." << endl;
   169   check(U.join(3,4),"Test failed.");
   170   check(!U.join(2,4),"Test failed.");
   171 //   print(U);
   172 
   173 
   174   cout << "Size of the class of 4: " << U.size(4) << endl;
   175   check(U.size(4) == 3,"Test failed.");
   176   cout << "Size of the class of 3: " << U.size(3) << endl;
   177   check(U.size(3) == 3,"Test failed.");
   178   cout << "Size of the class of 2: " << U.size(2) << endl;
   179   check(U.size(2) == 3,"Test failed.");
   180 
   181   cout << "Calling makeRep(4)..." << endl;
   182   U.makeRep(4);
   183 //   print(U);
   184   cout << "Calling makeRep(3)..." << endl;
   185   U.makeRep(3);
   186 //   print(U);
   187   cout << "Calling makeRep(2)..." << endl;
   188   U.makeRep(2);
   189 //   print(U);
   190 
   191   cout << "Size of the class of 4: " << U.size(4) << endl;
   192   check(U.size(4) == 3,"Test failed.");
   193   cout << "Size of the class of 3: " << U.size(3) << endl;
   194   check(U.size(3) == 3,"Test failed.");
   195   cout << "Size of the class of 2: " << U.size(2) << endl;
   196   check(U.size(2) == 3,"Test failed.");
   197 
   198 
   199   cout << "eraseClass 4 ..." << endl;
   200   U.eraseClass(4);
   201 //   print(U);
   202 
   203   cout << "eraseClass 7 ..." << endl;
   204   U.eraseClass(7);
   205 //   print(U);
   206 
   207   cout << "done." << endl;
   208 }