Boost logo

Boost :

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


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk