COIN-OR::LEMON - Graph Library

source: lemon-0.x/test/unionfind_test.cc @ 2205:c20b0eb92a33

Last change on this file since 2205:c20b0eb92a33 was 2205:c20b0eb92a33, checked in by Balazs Dezso, 13 years ago

UnionFind?
Changing the representation of the union-find
it has the same running time but it takes just 2/3 space
! does not auto insert items /performance/

UnionFindEnum?
Changing the interface - more convenient to UnionFind?
Does not based on the stl data structures /it could be disadvantage/

=> does not use singular iterator assignment /not stl conform, but always work/

Just new iterator interface

MaxMatching? + UnionFindTest?
Using new iterator interface instead of the old

File size: 2.7 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
28typedef UnionFindEnum<int, StdMap<int, int> > UFE;
29
30void print(UFE const &ufe) {
31  cout << "Print the classes of the structure:" << endl;
32  int i = 1;
33  for (UFE::ClassIt cit(ufe); cit != INVALID; ++cit) {
34    cout << "  " << i << " (" << cit << "):" << flush;
35    for (UFE::ItemIt iit(ufe, cit); iit != INVALID; ++iit) {
36      cout << " " << iit << flush;
37    }
38    cout << endl;
39    i++;
40  }
41  cout << "done" << endl;
42}
43
44
45int main() {
46  StdMap<int, int> base;
47  UFE U(base);
48
49  U.insert(1);
50  U.insert(2);
51
52  check(U.join(1,2),"Test failed.");
53
54  U.insert(3);
55  U.insert(4);
56  U.insert(5);
57  U.insert(6);
58  U.insert(7);
59
60  check(U.join(1,4),"Test failed.");
61  check(!U.join(2,4),"Test failed.");
62  check(U.join(3,5),"Test failed.");
63
64  U.insert(8,5);
65
66  check(U.size(4) == 3,"Test failed.");
67  check(U.size(5) == 3,"Test failed.");
68  check(U.size(6) == 1,"Test failed.");
69  check(U.size(2) == 3,"Test failed.");
70
71  U.insert(9);
72  U.insert(10,9);
73
74  check(U.join(8,10),"Test failed.");
75
76  check(U.move(9,4),"Test failed.");
77  check(!U.move(9,2),"Test failed.");
78
79  check(U.size(4) == 4,"Test failed.");
80  check(U.size(9) == 4,"Test failed.");
81
82  check(U.move(5,6),"Test failed.");
83
84  check(U.size(5) == 2,"Test failed.");
85  check(U.size(8) == 3,"Test failed.");
86
87  check(U.move(7,10),"Test failed.");
88  check(U.size(7) == 4,"Test failed.");
89
90  U.erase(9);
91  U.erase(1);
92
93  check(U.size(4) == 2,"Test failed.");
94  check(U.size(2) == 2,"Test failed.");
95
96  U.erase(6);
97  U.split(8);
98
99  check(U.size(4) == 2,"Test failed.");
100  check(U.size(3) == 1,"Test failed.");
101  check(U.size(2) == 2,"Test failed.");
102
103  check(U.join(3,4),"Test failed.");
104  check(!U.join(2,4),"Test failed.");
105
106  check(U.size(4) == 3,"Test failed.");
107  check(U.size(3) == 3,"Test failed.");
108  check(U.size(2) == 3,"Test failed.");
109
110  U.makeRep(4);
111  U.makeRep(3);
112  U.makeRep(2);
113
114  check(U.size(4) == 3,"Test failed.");
115  check(U.size(3) == 3,"Test failed.");
116  check(U.size(2) == 3,"Test failed.");
117
118
119  U.eraseClass(4);
120  U.eraseClass(7);
121
122}
Note: See TracBrowser for help on using the repository browser.