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

Subject: Re: [Boost-users] [Graph] On Dijkstra SSSP performance
From: Leo Hidd (leohidd_at_[hidden])
Date: 2012-03-13 13:53:51

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?