Minimum Spanning Tree

Problem Description

This benchmark computes a minimum spanning tree in a weighted undirected graph with by using Boruvka's algorithm.

Algorithm

The algorithm is implemented by successive edge-relaxations of the minimum weight edges. However, since an explicit edge-relaxation involves modifying the graph, the implementation performs edge-relaxation indirectly. This is done by keeping track of the set of nodes that have been merged, called components, which avoids modifications to the graph. Each component's size grows in each iteration, while the number of components reduces (due to components getting merged). The algorithm terminates when only one component remains. When the input graph is disconnected, the algorithm terminates when the number of components does not change in an iteration and it computes a minimum spanning forest.

Figure: Before edge-contraction and after edge-contraction

The computation is split across a sequence of kernels. This program is generated by IrGL compiler.

do {
  find the minimum weight edge out of each component;
  merge a component with its partner;
} while the number of components changes;

NOTE: Only use the symmetric graph files (.sym.gr) as inputs.

Performance

Graph	Time (ms)
FLA.sym	35
rmat12.sym	8
2d-2e20.sym	124
USA-road-d.CTR	11
USA-road-d.W	138
USA-road-d.USA	663
orkut	964
livejournal	3074
indochina	2173

The above performance is observed on a 1733.500 Mhz GeForce GTX 1080 6000 with 8119 MB of main memory.