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

Return to the Connected Components Page