forked from jegonzal/PowerGraph
-
Notifications
You must be signed in to change notification settings - Fork 0
/
union_find_test.cxx
116 lines (99 loc) · 2.97 KB
/
union_find_test.cxx
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
/**
* Copyright (c) 2009 Carnegie Mellon University.
* All rights reserved.
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing,
* software distributed under the License is distributed on an "AS
* IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either
* express or implied. See the License for the specific language
* governing permissions and limitations under the License.
*
* For more about this software visit:
*
* http://www.graphlab.ml.cmu.edu
*
*/
#include <graphlab/util/union_find.hpp>
#include <graphlab/util/random.hpp>
#include <graphlab/parallel/pthread_tools.hpp>
graphlab::concurrent_union_find uf2;
void add_even() {
for (size_t i = 2; i < 1000000; i+=2) {
size_t unionwith = 0;
while(1){
unionwith = graphlab::random::fast_uniform((size_t)0, i - 1);
if (unionwith % 2 == 0) break;
}
uf2.merge(i, unionwith);
}
}
void add_odd() {
for (size_t i = 3; i < 1000000; i+=2) {
size_t unionwith = 0;
while(1){
unionwith = graphlab::random::fast_uniform((size_t)0, i - 1);
if (unionwith % 2 == 1) break;
}
uf2.merge(i, unionwith);
}
}
class UnionFindTest: public CxxTest::TestSuite {
public:
void test_union_find() {
graphlab::union_find<size_t, size_t> uf;
uf.init(1000);
// union all the odd together and all the even together
for (size_t i = 2; i < 1000; i+=2) {
size_t unionwith = 0;
while(1){
unionwith = graphlab::random::fast_uniform((size_t)0, i - 1);
if (unionwith % 2 == 0) break;
}
uf.merge(i, unionwith);
}
// union all the odd together and all the even together
for (size_t i = 3; i < 1000; i+=2) {
size_t unionwith = 0;
while(1){
unionwith = graphlab::random::fast_uniform((size_t)0, i - 1);
if (unionwith % 2 == 1) break;
}
uf.merge(i, unionwith);
}
// assert that all evens are together and all odds are together
size_t evenid = uf.find(0);
for (size_t i = 0; i < 1000; i+=2) {
TS_ASSERT_EQUALS(uf.find(i), evenid);
}
size_t oddid = uf.find(1);
for (size_t i = 1; i < 1000; i+=2) {
TS_ASSERT_EQUALS(uf.find(i), oddid);
}
}
void test_union_find2() {
uf2.init(1000000);
graphlab::thread_group tg;
tg.launch(add_even);
tg.launch(add_even);
tg.launch(add_even);
tg.launch(add_odd);
tg.launch(add_odd);
tg.launch(add_odd);
tg.join();
// assert that all evens are together and all odds are together
size_t evenid = uf2.find(0);
for (size_t i = 0; i < 1000000; i+=2) {
TS_ASSERT_EQUALS(uf2.find(i), evenid);
}
size_t oddid = uf2.find(1);
for (size_t i = 1; i < 1000000; i+=2) {
TS_ASSERT_EQUALS(uf2.find(i), oddid);
}
}
};