COIN-OR::LEMON - Graph Library

source: lemon-0.x/test/unionfind_test.cc @ 2100:6fbe90faf02a

Last change on this file since 2100:6fbe90faf02a was 2005:84ec2948eb1f, checked in by Mihaly Barasz, 14 years ago

unionfind_test: double erase is not supported anymore

File size: 2.8 KB
Line 
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 */
18
19#include <iostream>
20
21#include <lemon/maps.h>
22#include <lemon/unionfind.h>
23#include "test_tools.h"
24
25using namespace lemon;
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;
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}
48
49
50int main() {
51  UFE::MapType base;
52  UFE U(base);
53
54  U.insert(1);
55  U.insert(2);
56
57  check(U.join(1,2),"Test failed.");
58
59  U.insert(3);
60  U.insert(4);
61  U.insert(5);
62  U.insert(6);
63  U.insert(7);
64
65  check(U.join(1,4),"Test failed.");
66  check(!U.join(2,4),"Test failed.");
67  check(U.join(3,5),"Test failed.");
68
69  U.insert(8,5);
70
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.");
75
76  U.insert(9);
77  U.insert(10,9);
78  check(U.join(8,10),"Test failed.");
79
80  check(U.move(9,4),"Test failed.");
81  check(!U.move(9,2),"Test failed.");
82
83  check(U.size(4) == 4,"Test failed.");
84  check(U.size(9) == 4,"Test failed.");
85
86  check(U.move(5,6),"Test failed.");
87
88  check(U.size(5) == 2,"Test failed.");
89  check(U.size(8) == 3,"Test failed.");
90
91  check(U.move(7,10),"Test failed.");
92  check(U.size(7) == 4,"Test failed.");
93
94  U.erase(9);
95  U.erase(1);
96
97  check(U.size(4) == 2,"Test failed.");
98  check(U.size(2) == 2,"Test failed.");
99
100  U.erase(6);
101  U.split(8);
102
103  check(U.size(4) == 2,"Test failed.");
104  check(U.size(3) == 1,"Test failed.");
105  check(U.size(2) == 2,"Test failed.");
106
107  check(U.join(3,4),"Test failed.");
108  check(!U.join(2,4),"Test failed.");
109
110  check(U.size(4) == 3,"Test failed.");
111  check(U.size(3) == 3,"Test failed.");
112  check(U.size(2) == 3,"Test failed.");
113
114  U.makeRep(4);
115  U.makeRep(3);
116  U.makeRep(2);
117
118  check(U.size(4) == 3,"Test failed.");
119  check(U.size(3) == 3,"Test failed.");
120  check(U.size(2) == 3,"Test failed.");
121
122
123  U.eraseClass(4);
124  U.eraseClass(7);
125
126}
Note: See TracBrowser for help on using the repository browser.