Minimum Spanning Forest

Compiling

• In ctf/generator, run make -f Makefile.BFS.mpi.
• Download this release of CTF.
• In ctf, run make to create the test_mst executable.

Strong scaling

Run with a R-MAT graph with 2^S vertices and average edge degree E.
./test_mst -S 6 -E 8

Weak scaling

Run with a uniform graph with n vertices and sp*n^2 edges.
./test_mst -n 1000 -sp 0.005

Snap dataset

Matrix market

From file

Command line arguments

• -shortcut3 X: trigger complete shortcutting if global number of vertices with changed parent is less than X. We used 131072.
• -as 1: pairwise implementation of hook step.

Citation

If you use this implementation, please cite this paper.