COIN-OR::LEMON - Graph Library

source: lemon-0.x/test/unionfind_test.cc @ 1887:22fdc00894aa

Last change on this file since 1887:22fdc00894aa was 1875:98698b69a902, checked in by Alpar Juttner, 18 years ago

Happy new year to LEMON

File size: 2.8 KB
Line 
1/* -*- C++ -*-
2 * test/unionfind_test.cc - Part of LEMON, a generic C++ optimization library
3 *
4 * Copyright (C) 2006 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5 * (Egervary Research Group on Combinatorial Optimization, EGRES).
6 *
7 * Permission to use, modify and distribute this software is granted
8 * provided that this copyright notice appears in all copies. For
9 * precise terms see the accompanying LICENSE file.
10 *
11 * This software is provided "AS IS" with no warranty of any kind,
12 * express or implied, and with no claim as to its suitability for any
13 * purpose.
14 *
15 */
16
17#include <iostream>
18
19#include <lemon/maps.h>
20#include <lemon/unionfind.h>
21#include "test_tools.h"
22
23using namespace lemon;
24using namespace std;
25
26template <typename T>
27class BaseMap : public StdMap<int,T> {};
28
29typedef UnionFindEnum<int, BaseMap> UFE;
30
31void print(UFE const &ufe) {
32  UFE::ClassIt cit;
33  cout << "Print the classes of the structure:" << endl;
34  int i = 1;
35  for (ufe.first(cit); ufe.valid(cit); ufe.next(cit)) {
36    cout << "  " << i << " (" << cit << "):" << flush;
37    UFE::ItemIt iit;
38    for (ufe.first(iit, cit); ufe.valid(iit); ufe.next(iit)) {
39      cout << " " << iit << flush;
40    }
41    cout << endl;
42    i++;
43  }
44  cout << "done" << endl;
45}
46
47
48int main() {
49  UFE::MapType base;
50  UFE U(base);
51
52  U.insert(1);
53  U.insert(2);
54
55  check(U.join(1,2),"Test failed.");
56
57  U.insert(3);
58  U.insert(4);
59  U.insert(5);
60  U.insert(6);
61  U.insert(7);
62
63  check(U.join(1,4),"Test failed.");
64  check(!U.join(2,4),"Test failed.");
65  check(U.join(3,5),"Test failed.");
66
67  U.insert(8,5);
68
69  check(U.size(4) == 3,"Test failed.");
70  check(U.size(5) == 3,"Test failed.");
71  check(U.size(6) == 1,"Test failed.");
72  check(U.size(2) == 3,"Test failed.");
73
74  U.insert(9);
75  U.insert(10,9);
76  check(U.join(8,10),"Test failed.");
77
78  check(U.move(9,4),"Test failed.");
79  check(!U.move(9,2),"Test failed.");
80
81  check(U.size(4) == 4,"Test failed.");
82  check(U.size(9) == 4,"Test failed.");
83
84  check(U.move(5,6),"Test failed.");
85
86  check(U.size(5) == 2,"Test failed.");
87  check(U.size(8) == 3,"Test failed.");
88
89  check(U.move(7,10),"Test failed.");
90  check(U.size(7) == 4,"Test failed.");
91
92  U.erase(9);
93  U.erase(1);
94
95  check(U.size(4) == 2,"Test failed.");
96  check(U.size(2) == 2,"Test failed.");
97
98  U.erase(1);
99  U.erase(6);
100  U.split(8);
101
102  check(U.size(4) == 2,"Test failed.");
103  check(U.size(3) == 1,"Test failed.");
104  check(U.size(2) == 2,"Test failed.");
105
106  check(U.join(3,4),"Test failed.");
107  check(!U.join(2,4),"Test failed.");
108
109  check(U.size(4) == 3,"Test failed.");
110  check(U.size(3) == 3,"Test failed.");
111  check(U.size(2) == 3,"Test failed.");
112
113  U.makeRep(4);
114  U.makeRep(3);
115  U.makeRep(2);
116
117  check(U.size(4) == 3,"Test failed.");
118  check(U.size(3) == 3,"Test failed.");
119  check(U.size(2) == 3,"Test failed.");
120
121
122  U.eraseClass(4);
123  U.eraseClass(7);
124
125}
Note: See TracBrowser for help on using the repository browser.