Re: [Boost-users] [Graph] On Dijkstra SSSP performance

Subject: Re: [Boost-users] [Graph] On Dijkstra SSSP performance
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2012-03-12 22:12:46

On Tue, 13 Mar 2012, Leo Hidd wrote:

>
>> It looks like you may not be passing your weight map into 
>> dijkstra_shortest_paths.  If that isn't the problem, what are the exact 
>> types the compiler says that you are trying to pass to boost::get?  Where 
>> is dijkstra_shortest_paths_no_color_map is it failing (which line, and 
>> which instantiation stack)?
>> 
>> -- Jeremiah Willcock
>
> Jeremiah, here's a test case http://ge.tt/1CPQxuE/v/0 (the 3 million vertices 
> mesh is the bimba6M.obj). There u will see the configuration number 4. In 
> addition, I define a macro USE_BGL_CSR to using compressed sparse row instead 
> of adjacency list. With adjacency list it works fine, but when using csr it 
> fails to compile with the error I reported previously (by the way, it's the 
> only error the compiler will print out). I don't feel like I'm missing the 
> weight map, as I pass it on the graph construction. Please, if you can help 
> me using csr it wold be nice, it should really accelerate SSSP search.

Here's what I get using CSR (GCC 4.7.0 20111231 on Mac OS X, -Ofast 
-DNDEBUG):

reading bimba_6M.obj...
boost graph test...
boost graph SSSP: 1807567 ms
my graph test...
my graph SSSP: 2001208 ms
dist difference between graphs: 0

The only things in your code I needed to change were to add #includes of 
<float.h> and <iostream> into MyGraph.h, and to change the edge weight to 
a bundled property (old-style properties are allowed in adjacency_list but 
not comparessed_sparse_row_graph).

-- Jeremiah Willcock