lemon-main: test/unionfind_test.cc@4e2581021300

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

    19 #include <iostream>

    21 #include <lemon/list_graph.h>

    22 #include <lemon/maps.h>

    23 #include <lemon/unionfind.h>

    24 #include "test_tools.h"

    26 using namespace lemon;

    27 using namespace std;

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

    31 int main() {

    32   ListGraph g;

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

    34   UFE U(base);

    35   vector<ListGraph::Node> n;

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

    39   U.insert(n[1]);

    40   U.insert(n[2]);

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

    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]);

    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.");

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

    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.");

    65   U.insert(n[9]);

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

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

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

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

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

    77   U.erase(n[9]);

    78   U.erase(n[1]);

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

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

    83   U.erase(n[6]);

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

    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.");

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

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

    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.");

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

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

   103   return 0;

   104 }

author	Balazs Dezso <deba@inf.elte.hu>
	Thu, 24 Apr 2008 11:56:44 +0200
changeset 148	4e2581021300
parent 103	b68a7e348e00
child 171	02f4d5d9bfd7
permissions	-rw-r--r--