Given a weighted undirected graph return the minimum spanning tree (MST), or minimum spanning forest (MSF) if the graph is not connected. For timing purposes the input can either be an adjacency array format with all edges appearing in both directions, or an edge array with all edges appearing in just one direction. In the case that there are multiple possible MSFs (due to equal weights), any MSF is valid.
The input is a graph in the in the weighted edge graph format. The output is a sequence of integers corresponding to the locations of all the edges in the minimum spanning tree (or forest) with respect to the input (zero based). The output needs to be in the sequence format. The edge indices need not be sorted in the output.
For timing purposes any code is allowed to covert from the edge array format to an adjacency format outside of the timed code, but is not allowed to do any other processing of the graph (e.g. reordering to improve locality).
Each distribution should be run for n=10,000,000. The edge weights are selected at random. The weights used for average time are given in parentheses.
randLocalGraph -d 3 -m <5*n> <n> <tmpname>
addWeights <tmpname> <filename>
rMatGraph -a .5 -b .1 -m <5*n> <n> <tmpname>
addWeights <tmpname> <filename>
gridGraph -d 2 <n> <tmpname>
addWeights <tmpname> <filename>
This project has been funded by the following sources:
Intel Labs Academic Research Office for the Parallel Algorithms for Non-Numeric Computing Program,
National Science Foundation, and
IBM Research.