Mercuriallemon-1.0 / file revision
summary | shortlog | changelog | graph | tags | bookmarks | branches | files | changeset | file | latest | revisions | annotate | diff | comparison | raw | help
test/unionfind_test.cc
author Akos Ladanyi <ladanyi@tmit.bme.hu>
Sun, 13 Apr 2008 13:22:52 +0200
changeset 141 96f81c791f0c
parent 103 b68a7e348e00
child 171 02f4d5d9bfd7
permissions -rw-r--r--
CMake based build system 
     1 /* -*- C++ -*-

     2  *

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

     4  *

     5  * Copyright (C) 2003-2008

     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  */

    18 

    19 #include <iostream>

    20 

    21 #include <lemon/list_graph.h>

    22 #include <lemon/maps.h>

    23 #include <lemon/unionfind.h>

    24 #include "test_tools.h"

    25 

    26 using namespace lemon;

    27 using namespace std;

    28 

    29 typedef UnionFindEnum<ListGraph::NodeMap<int> > UFE;

    30 

    31 int main() {

    32   ListGraph g;

    33   ListGraph::NodeMap<int> base(g);

    34   UFE U(base);

    35   vector<ListGraph::Node> n;

    36   

    37   for(int i=0;i<20;i++) n.push_back(g.addNode());

    38 

    39   U.insert(n[1]);

    40   U.insert(n[2]);

    41 

    42   check(U.join(n[1],n[2]) != -1,"Test failed.");

    43 

    44   U.insert(n[3]);

    45   U.insert(n[4]);

    46   U.insert(n[5]);

    47   U.insert(n[6]);

    48   U.insert(n[7]);

    49 

    50 

    51   check(U.join(n[1],n[4]) != -1,"Test failed.");

    52   check(U.join(n[2],n[4]) == -1,"Test failed.");

    53   check(U.join(n[3],n[5]) != -1,"Test failed.");

    54 

    55 

    56   U.insert(n[8],U.find(n[5]));

    57 

    58 

    59   check(U.size(U.find(n[4])) == 3,"Test failed.");

    60   check(U.size(U.find(n[5])) == 3,"Test failed.");

    61   check(U.size(U.find(n[6])) == 1,"Test failed.");

    62   check(U.size(U.find(n[2])) == 3,"Test failed.");

    63 

    64 

    65   U.insert(n[9]);

    66   U.insert(n[10],U.find(n[9]));

    67 

    68 

    69   check(U.join(n[8],n[10]) != -1,"Test failed.");

    70 

    71 

    72   check(U.size(U.find(n[4])) == 3,"Test failed.");

    73   check(U.size(U.find(n[9])) == 5,"Test failed.");

    74 

    75   check(U.size(U.find(n[8])) == 5,"Test failed.");

    76 

    77   U.erase(n[9]);

    78   U.erase(n[1]);

    79 

    80   check(U.size(U.find(n[10])) == 4,"Test failed.");

    81   check(U.size(U.find(n[2])) == 2,"Test failed.");

    82 

    83   U.erase(n[6]);

    84   U.split(U.find(n[8]));

    85 

    86 

    87   check(U.size(U.find(n[4])) == 2,"Test failed.");

    88   check(U.size(U.find(n[3])) == 1,"Test failed.");

    89   check(U.size(U.find(n[2])) == 2,"Test failed.");

    90 

    91 

    92   check(U.join(n[3],n[4]) != -1,"Test failed.");

    93   check(U.join(n[2],n[4]) == -1,"Test failed.");

    94 

    95 

    96   check(U.size(U.find(n[4])) == 3,"Test failed.");

    97   check(U.size(U.find(n[3])) == 3,"Test failed.");

    98   check(U.size(U.find(n[2])) == 3,"Test failed.");

    99 

   100   U.eraseClass(U.find(n[4]));

   101   U.eraseClass(U.find(n[7]));

   102 

   103   return 0;

   104 }
lemon-1.0