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-13 13:55:54

On Tue, 13 Mar 2012, Leo Hidd wrote:

> Le 13/03/2012 03:12, Jeremiah Willcock a écrit :
>> 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

> it sounds really good! Do you mind to send me by e-mail the BoostGraph.h file 
> with the modifications you made? Are you using 32 or 64bits OS version? Your 
> processor is Intel, I presume. I changed Edge_Cost definition to: struct 
> Edge_Cost{double weight;}; and now it compiles just fine! That's what 
> supposed to do, that's what you did?

I just added the two #includes that I mentioned.  I'm pretty sure I'm 
running a 64-bit OS (on a Nehalem); I don't remember what the default 
compilation mode is, though.  In regards to your final question, yes, that 
is the change that I made, plus adding the weight map parameter explicitly 
to the call to dijkstra_shortest_paths_no_color_map.

-- Jeremiah Willcock