Re: [boost] How to speed up the djikstra graph

Subject: Re: [boost] How to speed up the djikstra graph
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2009-05-23 18:17:44

On Sun, 24 May 2009, Lennart Berg wrote:

> Sadly due to the restriction of the engine I have to stick with the now
> dated Visual C++ 6.
>
> I am running with boost 1.35.
>
> I have tried the last couple of hours to port the boost trunk to VC6 but it
> seems more or less hopeless for me.
> So unless the 25% speedup is a small patch that can be implemented, I dont
> see any change in the current setup. (The sparsed graph is calling out for a
> newer compiler)
>
> I am currently looking into the parallel boost project and will try to get a
> previus trunk version to work with the 1.35.

You still should benchmark things in release mode.  Please try that and 
see if it changes your performance behavior.  The 25% speedup is a 
relatively small patch, but hasn't been tested on that old of a copy of 
Boost or on that compiler.  To get that, copy over 
boost/graph/detail/d_ary_heap.hpp from a new copy of Boost and look at the 
diffs between the boost/graph/dijkstra_shortest_paths.hpp files to find 
the part where d_ary_heap is used.  I think that can probably be ported 
over; the code is not using C++ in any fancy ways.

As to the compressed sparse row graph, you might be able to take out the 
vertex and edge property support and then use the vertex_index and 
edge_index property maps defined by the graph type as key to external 
property maps.  I believe partial specialization is only required in there 
for bundled properties, which you can avoid by using external properties.

-- Jeremiah Willcock