lemon-0.x: test/unionfind_test.cc@7a7a1f95cc24

     1 /* -*- C++ -*-

     2  * test/unionfind_test.cc - Part of LEMON, a generic C++ optimization library

     3  *

     4  * Copyright (C) 2006 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  */

    17 #include <iostream>

    19 #include <lemon/maps.h>

    20 #include <lemon/unionfind.h>

    21 #include "test_tools.h"

    23 using namespace lemon;

    24 using namespace std;

    26 template <typename T>

    27 class BaseMap : public StdMap<int,T> {};

    29 typedef UnionFindEnum<int, BaseMap> UFE;

    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 }

    48 int main() {

    49   UFE::MapType base;

    50   UFE U(base);

    52   U.insert(1);

    53   U.insert(2);

    55   check(U.join(1,2),"Test failed.");

    57   U.insert(3);

    58   U.insert(4);

    59   U.insert(5);

    60   U.insert(6);

    61   U.insert(7);

    63   check(U.join(1,4),"Test failed.");

    64   check(!U.join(2,4),"Test failed.");

    65   check(U.join(3,5),"Test failed.");

    67   U.insert(8,5);

    69   check(U.size(4) == 3,"Test failed.");

    70   check(U.size(5) == 3,"Test failed.");

    71   check(U.size(6) == 1,"Test failed.");

    72   check(U.size(2) == 3,"Test failed.");

    74   U.insert(9);

    75   U.insert(10,9);

    76   check(U.join(8,10),"Test failed.");

    78   check(U.move(9,4),"Test failed.");

    79   check(!U.move(9,2),"Test failed.");

    81   check(U.size(4) == 4,"Test failed.");

    82   check(U.size(9) == 4,"Test failed.");

    84   check(U.move(5,6),"Test failed.");

    86   check(U.size(5) == 2,"Test failed.");

    87   check(U.size(8) == 3,"Test failed.");

    89   check(U.move(7,10),"Test failed.");

    90   check(U.size(7) == 4,"Test failed.");

    92   U.erase(9);

    93   U.erase(1);

    95   check(U.size(4) == 2,"Test failed.");

    96   check(U.size(2) == 2,"Test failed.");

    98   U.erase(1);

    99   U.erase(6);

   100   U.split(8);

   102   check(U.size(4) == 2,"Test failed.");

   103   check(U.size(3) == 1,"Test failed.");

   104   check(U.size(2) == 2,"Test failed.");

   106   check(U.join(3,4),"Test failed.");

   107   check(!U.join(2,4),"Test failed.");

   109   check(U.size(4) == 3,"Test failed.");

   110   check(U.size(3) == 3,"Test failed.");

   111   check(U.size(2) == 3,"Test failed.");

   113   U.makeRep(4);

   114   U.makeRep(3);

   115   U.makeRep(2);

   117   check(U.size(4) == 3,"Test failed.");

   118   check(U.size(3) == 3,"Test failed.");

   119   check(U.size(2) == 3,"Test failed.");

   122   U.eraseClass(4);

   123   U.eraseClass(7);

   125 }

author	alpar
	Wed, 01 Feb 2006 11:33:16 +0000
changeset 1937	7a7a1f95cc24
parent 1569	2a455f46f85a
child 1956	a055123339d5
permissions	-rw-r--r--