while (sets[x] != x) {

x = sets[x] = sets[sets[x]];

}

return sets[x];

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;

}

/**

void update(UnionFindVertex &vertex, graphchi_context &gcontext) {

// do nothing -- all done in the special vertex class

}

/**

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;

}

/**

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);

}

}

/**

void before_exec_interval(vid_t window_st, vid_t window_en, graphchi_context &gcontext) {

}

/**

void after_exec_interval(vid_t window_st, vid_t window_en, graphchi_context &gcontext) {

}

/* GraphChi initialization will read the command line

graphchi_init(argc, argv);

/* Metrics object for keeping track of performance counters

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;