On Mon, 27 Aug 2012, Tristram Gräbener wrote:
Hello,
I use boost::graph and the Dijkstra algorithm.
My edge property is rather big (I store public transport timetables on them).
In the file boost/graph/relax.hpp, the property of an edge is copied : W w_e = get(w, e);
As my properties are large, it yields some overhead.
I changed that line to const W & w_e = get(w, e);
My benchmarks (on 1000 runs) went from 101 secs down to 87 (using GCC 4.6 -O3)
So my question is : – would it hurt if it used const& instead of copy?
I forgot if the graph library actually returns a reference rather than a copy, but it shouldn't hurt if it returns a reference (as long as you don't modify the graph structure while you're holding that reference).
– am I not correctly using the lib? Maybe should I use an index on the edge property and use a functor to get the data in the different operations (edge_less, combine); but wouldn't it mean re-implementing the properties?
Are your weights used for Dijkstra (not your whole edge property) the full timetables? If so, aren't you using custom compare and combine functions already? In any case, rather than using an index value, you can try using a shared_ptr; with that, copying will work quickly and dereferencing will be easier. -- Jeremiah Willcock