Connected Components Algorithm Code

Download the code as a single gzipped file or as the following individual files:

README: includes this list and explanations of command-line arguments
Makefile
connect.h: header file containing graph node structures
make_graph.sc: routines for generating a random graph; the graph types include 2D and 3D lattices (with missing edges) and a tertiary graph where every vertex has an average of 3 random neighbors
local.sc: routines for local DFS/BFS
local.old.sc: version of local.sc used for getting performance measurements for the Supercomputing '95 paper; had a minor bug in the sequential code which made sequential execution times include some work necessary only for the parallel algorithm, thereby increasing speedups by about 2-3%
find_comp.sc: the global portion of the hybrid algorithm