COIN-OR::LEMON - Graph Library

source: lemon-0.x/test/unionfind_test.cc @ 2196:09af6d2b683b

Last change on this file since 2196:09af6d2b683b was 2005:84ec2948eb1f, checked in by Mihaly Barasz, 15 years ago

unionfind_test: double erase is not supported anymore

File size: 2.8 KB
RevLine 
[906]1/* -*- C++ -*-
2 *
[1956]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
[1359]7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
[906]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
[483]19#include <iostream>
20
[921]21#include <lemon/maps.h>
22#include <lemon/unionfind.h>
[774]23#include "test_tools.h"
[483]24
[921]25using namespace lemon;
[483]26using namespace std;
27
28template <typename T>
29class BaseMap : public StdMap<int,T> {};
30
31typedef UnionFindEnum<int, BaseMap> UFE;
32
33void print(UFE const &ufe) {
34  UFE::ClassIt cit;
[774]35  cout << "Print the classes of the structure:" << endl;
[483]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}
48
49
50int main() {
51  UFE::MapType base;
52  UFE U(base);
53
[1569]54  U.insert(1);
55  U.insert(2);
[483]56
[774]57  check(U.join(1,2),"Test failed.");
[483]58
59  U.insert(3);
60  U.insert(4);
61  U.insert(5);
62  U.insert(6);
63  U.insert(7);
64
[774]65  check(U.join(1,4),"Test failed.");
66  check(!U.join(2,4),"Test failed.");
67  check(U.join(3,5),"Test failed.");
[483]68
69  U.insert(8,5);
70
[774]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.");
[483]75
76  U.insert(9);
77  U.insert(10,9);
[1569]78  check(U.join(8,10),"Test failed.");
[483]79
[1569]80  check(U.move(9,4),"Test failed.");
81  check(!U.move(9,2),"Test failed.");
[483]82
[1569]83  check(U.size(4) == 4,"Test failed.");
84  check(U.size(9) == 4,"Test failed.");
[483]85
[1569]86  check(U.move(5,6),"Test failed.");
[483]87
[774]88  check(U.size(5) == 2,"Test failed.");
89  check(U.size(8) == 3,"Test failed.");
[483]90
[774]91  check(U.move(7,10),"Test failed.");
92  check(U.size(7) == 4,"Test failed.");
[483]93
94  U.erase(9);
[1569]95  U.erase(1);
[483]96
[774]97  check(U.size(4) == 2,"Test failed.");
98  check(U.size(2) == 2,"Test failed.");
[483]99
[1569]100  U.erase(6);
101  U.split(8);
[483]102
[774]103  check(U.size(4) == 2,"Test failed.");
104  check(U.size(3) == 1,"Test failed.");
105  check(U.size(2) == 2,"Test failed.");
[483]106
[774]107  check(U.join(3,4),"Test failed.");
108  check(!U.join(2,4),"Test failed.");
[483]109
[774]110  check(U.size(4) == 3,"Test failed.");
111  check(U.size(3) == 3,"Test failed.");
112  check(U.size(2) == 3,"Test failed.");
[483]113
114  U.makeRep(4);
115  U.makeRep(3);
116  U.makeRep(2);
117
[774]118  check(U.size(4) == 3,"Test failed.");
119  check(U.size(3) == 3,"Test failed.");
120  check(U.size(2) == 3,"Test failed.");
[483]121
122
123  U.eraseClass(4);
[1569]124  U.eraseClass(7);
[483]125
126}
Note: See TracBrowser for help on using the repository browser.