lemon-0.x: test/unionfind_test.cc@b71f8ff62046

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

     2  *

     3  * This file is a part of LEMON, a generic C++ optimization library

     4  *

     5  * Copyright (C) 2003-2006

     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).

     8  *

     9  * Permission to use, modify and distribute this software is granted

    10  * provided that this copyright notice appears in all copies. For

    11  * precise terms see the accompanying LICENSE file.

    12  *

    13  * This software is provided "AS IS" with no warranty of any kind,

    14  * express or implied, and with no claim as to its suitability for any

    15  * purpose.

    16  *

    17  */

    19 #include <iostream>

    21 #include <lemon/maps.h>

    22 #include <lemon/unionfind.h>

    23 #include "test_tools.h"

    25 using namespace lemon;

    26 using namespace std;

    28 template <typename T>

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

    31 typedef UnionFindEnum<int, BaseMap> UFE;

    33 void print(UFE const &ufe) {

    34   UFE::ClassIt cit;

    35   cout << "Print the classes of the structure:" << endl;

    36   int i = 1;

    37   for (ufe.first(cit); ufe.valid(cit); ufe.next(cit)) {

    38     cout << "  " << i << " (" << cit << "):" << flush;

    39     UFE::ItemIt iit;

    40     for (ufe.first(iit, cit); ufe.valid(iit); ufe.next(iit)) {

    41       cout << " " << iit << flush;

    42     }

    43     cout << endl;

    44     i++;

    45   }

    46   cout << "done" << endl;

    47 }

    50 int main() {

    51   UFE::MapType base;

    52   UFE U(base);

    54   U.insert(1);

    55   U.insert(2);

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

    59   U.insert(3);

    60   U.insert(4);

    61   U.insert(5);

    62   U.insert(6);

    63   U.insert(7);

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

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

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

    69   U.insert(8,5);

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

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

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

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

    76   U.insert(9);

    77   U.insert(10,9);

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

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

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

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

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

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

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

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

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

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

    94   U.erase(9);

    95   U.erase(1);

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

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

   100   U.erase(6);

   101   U.split(8);

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

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

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

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

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

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

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

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

   114   U.makeRep(4);

   115   U.makeRep(3);

   116   U.makeRep(2);

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

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

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

   123   U.eraseClass(4);

   124   U.eraseClass(7);

   126 }

author	deba
	Mon, 03 Apr 2006 16:34:23 +0000
changeset 2034	b71f8ff62046
parent 1956	a055123339d5
child 2205	c20b0eb92a33
permissions	-rw-r--r--