[boost] [BGL] Performance improvement minimum spanning tree

From: Magnus Ekdahl (maguno_at_[hidden])
Date: 2006-08-24 04:49:05

A while ago I had a problem with the MST algorithm in boost. Essentially 
profiling reviled that the MST algorithm was a bottleneck for the 
computation I was performing. Thus I had to investigate the performance 
bottlenecks in boost mst and with this mail I want to investigate the 
potential for improving current boost implementation.

What is the proposed way of getting the prim algorithm updated in boost?

First let me argue that there is room for improvement. I have made a 
test program that constructs 1000 random complete graphs with 1000 nodes 
and the execution time is as follows

actually implementing jarniks algorithm
prim_minimum_spanning_tree  47.585s

current prim (djikstra wrapper) 3m2638s (338% slower)

kruskal_minimum_spanning_tree 40m57s (5063% slower)

The 47.585s performance is achieved by just implementing Jarnik/Prims 
algorithm using the relaxed_heap (that is already in boost, but code is 
available if necessary). As a side effect it seems to be a good test for 
the relaxed_heap, given that it revealed problems with the Fibonacci 
heap[1].

1. http://lists.boost.org/boost-users/2006/07/20876.php

I also want to take the opportunity to ask about the meaning of the 
minimum spanning tree algorithm as such, since efficient implementations 
in the future could be helped a lot by knowing exactly what the problem 
that should be solved is.

Given the hardness to understand the actual generality of the MST 
problem the current implementation tries to solve, I find it difficult 
to see how efficient algorithms can be heuristically selected. I.e. can 
you use num_edges(g) as an indicator of sparseness?

-- 
Magnus Ekdahl