Boost logo

Boost :

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


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

Boost list run by bdawes at, gregod at, cpdaniel at, john at