Repository navigation
Expand file tree
/
Copy pathunionfind_connectedcomps.cpp
More file actions
208 lines (163 loc) · 6.17 KB
/
Copy pathunionfind_connectedcomps.cpp
File metadata and controls
208 lines (163 loc) · 6.17 KB
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
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
/**
* @file
* @author Aapo Kyrola <[email protected]>
* @version 1.0
*
* @section LICENSE
*
* Copyright [2012] [Aapo Kyrola, Guy Blelloch, Carlos Guestrin / Carnegie Mellon University]
*
* 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.
*
* @section DESCRIPTION
*
* Connected components that uses the Union-Find algorithm. Requires
* O(|V|) of RAM, but only one pass of the data. Thus much faster than
* the completely disk based "connectedcomponents.cpp" example app.
*
* Highly optimized non-idiomatic GraphChi code that uses an overloaded vertex
* class to prevent actually creating the graph in memory.
*
* NOTE/REMARK: THERE IS NO REAL REASON TO USE GRAPHCHI FOR THIS ALGORITHM.
* A SIMPLE CODE THAT READ THE GRAPH ONE EDGE A TIME WOULD BE SUFFICIENT.
*
*/
#define GRAPHCHI_DISABLE_COMPRESSION
#include <string>
#include "graphchi_basic_includes.hpp"
#include "util/labelanalysis.hpp"
using namespace graphchi;
vid_t * sets;
unsigned int * setCounts; // Union-find
/* Find operator of Union-Find with path compression */
vid_t Find(vid_t x);
inline vid_t Find(vid_t x) {
while (sets[x] != x) {
x = sets[x] = sets[sets[x]];
}
return sets[x];
}
typedef vid_t VertexDataType;
typedef bool EdgeDataType; // not relevant
size_t ne = 0;
class UnionFindVertex : public graphchi_vertex<VertexDataType, EdgeDataType> {
public:
UnionFindVertex() : graphchi_vertex<VertexDataType, EdgeDataType> () {}
UnionFindVertex(vid_t _id,
graphchi_edge<EdgeDataType> * iptr,
graphchi_edge<EdgeDataType> * optr,
int indeg,
int outdeg) :
graphchi_vertex<VertexDataType, EdgeDataType> (_id, NULL, NULL, indeg, outdeg) {
}
inline void add_inedge(vid_t src, EdgeDataType * ptr, bool special_edge) {
vid_t setDst = Find(this->vertexid);
vid_t setSrc = Find(src);
// If in same component, nothing to do, otherwise, Unite
if (setSrc != setDst) {
if (setCounts[setSrc] > setCounts[setDst]) {
// A is bigger set, merge with A
sets[setDst] = setSrc;
setCounts[setSrc] += setCounts[setDst];
} else {
// or vice versa
sets[setSrc] = setDst;
setCounts[setDst] += setCounts[setSrc];
}
}
ne++;
}
void add_outedge(vid_t dst, EdgeDataType * ptr, bool special_edge) {
assert(false);
}
bool computational_edges() {
return true;
}
};
/**
* GraphChi programs need to subclass GraphChiProgram<vertex-type, edge-type>
* class. The main logic is usually in the update function.
*/
struct UnionFindProgram : public GraphChiProgram<VertexDataType, EdgeDataType, UnionFindVertex> {
/**
* Vertex update function.
*/
void update(UnionFindVertex &vertex, graphchi_context &gcontext) {
// do nothing -- all done in the special vertex class
}
/**
* Called before an iteration starts.
*/
void before_iteration(int iteration, graphchi_context &gcontext) {
/* Initialize */
sets = new vid_t[gcontext.nvertices];
for(vid_t i=0; i<gcontext.nvertices; i++) sets[i] = i;
setCounts = new unsigned int[gcontext.nvertices];
// All sets start with 1
for(vid_t i=0; i<gcontext.nvertices; i++) setCounts[i] = 1;
}
/**
* Called after an iteration has finished.
*/
void after_iteration(int iteration, graphchi_context &gcontext) {
// Now find everyone
logstream(LOG_INFO) << "Final finds..." << std::endl;
for(size_t i=0; i<gcontext.nvertices; i++) {
sets[i] = Find(i);
}
}
/**
* Called before an execution interval is started.
*/
void before_exec_interval(vid_t window_st, vid_t window_en, graphchi_context &gcontext) {
}
/**
* Called after an execution interval has finished.
*/
void after_exec_interval(vid_t window_st, vid_t window_en, graphchi_context &gcontext) {
}
};
int main(int argc, const char ** argv) {
/* GraphChi initialization will read the command line
arguments and the configuration file. */
graphchi_init(argc, argv);
/* Metrics object for keeping track of performance counters
and other information. Currently required. */
metrics m("union-find-connectedcomponents");
/* Basic arguments for application */
std::string filename = get_option_string("file"); // Base filename
int niters = 1;
/* Detect the number of shards or preprocess an input to create them */
int nshards = convert_if_notexists_novalues<EdgeDataType>(filename,
get_option_string("nshards", "auto"));
// Always run with only thread only (code is not thread-safe)
set_conf("execthreads", "1");
/* Run */
UnionFindProgram unionFind;
graphchi_engine<VertexDataType, EdgeDataType, UnionFindVertex > engine(filename, nshards, false, m);
engine.set_disable_outedges(true);
engine.set_only_adjacency(true);
engine.set_modifies_inedges(false);
engine.set_disable_vertexdata_storage();
engine.run(unionFind, niters);
/* Write vertex data */
std::string outputfile = filename_vertex_data<VertexDataType>(filename);
FILE * f = fopen(outputfile.c_str(), "w");
fwrite(sets, sizeof(vid_t), engine.num_vertices(), f);
fclose(f);
/* Analyze */
analyze_labels<vid_t>(filename);
/* Report execution metrics */
metrics_report(m);
return 0;
}