Re: [boost] How to speed up the djikstra graph

Subject: Re: [boost] How to speed up the djikstra graph
From: Lennart Berg (LB_at_[hidden])
Date: 2009-06-21 09:44:48

Well I need a path cost from one source to all possible destinations, so
naturally I picked dijkstra.

judging from the time complexity I thought dijstra would be faster than A*
A*:
O((E + V) log V).
Dijkstra:
O(V Log V)

I have never given heuristics any thoughts.

I still would like to hear how to solve the last issue to implement the new
d-ary heap.

But that might only give me a 5-10% boost.

isn't there a way to do incremental updates to a graph instead of running a
new total run every time?
(changing edge weights and adding / removing edges on the fly, and then only
update the vertexes that where affected by the update?)

-----Original Message-----
From: boost-bounces_at_[hidden] [mailto:boost-bounces_at_[hidden]]
On Behalf Of Ross Levine
Sent: 21. juni 2009 05:17
To: boost_at_[hidden]
Subject: Re: [boost] How to speed up the djikstra graph

Hi Lennart,

Have you considered using astar_search instead of djikstra? With a good
heuristic, A* can be much faster than Djikstra, which is a special case of
A* where the heuristic is constant.

On Fri, Jun 19, 2009 at 5:56 PM, Lennart Berg <LB_at_[hidden]> wrote:

> Hi
>
> I have tried mixing and fixing the graph files for quite some time now.
>
> the last problem I have met is that:
>
>  namespace detail {
>    template <class Graph, class IndexMap, class Value, bool
> KnownNumVertices>
>    struct vertex_property_map_generator_helper {};
>    template <class Graph, class IndexMap, class Value>
>    struct vertex_property_map_generator_helper<Graph, IndexMap, Value,
> true> {
>      typedef boost::iterator_property_map<Value*, IndexMap> type;
>      static type build(const Graph& g, const IndexMap& index,
> boost::scoped_array<Value>& array_holder) {
>        array_holder.reset(new Value[num_vertices(g)]);
>        std::fill(array_holder.get(), array_holder.get() + num_vertices(g),
> Value());
>        return make_iterator_property_map(array_holder.get(), index);
>      }
>    };
>
>    template <class Graph, class IndexMap, class Value>
>    struct vertex_property_map_generator_helper<Graph, IndexMap, Value,
> false> {
>      typedef boost::vector_property_map<Value, IndexMap> type;
>      static type build(const Graph& g, const IndexMap& index,
> boost::scoped_array<Value>& array_holder) {
>        return boost::make_vector_property_map<Value>(index);
>      }
>    };
>
>    template <class Graph, class IndexMap, class Value>
>    struct vertex_property_map_generator {
>      typedef boost::is_base_and_derived<
>                boost::vertex_list_graph_tag,
>                typename boost::graph_traits<Graph>::traversal_category>
>              known_num_vertices;
>      typedef vertex_property_map_generator_helper<Graph, IndexMap, Value,
> known_num_vertices::value> helper;
>      typedef typename helper::type type;
>      static type build(const Graph& g, const IndexMap& index,
> boost::scoped_array<Value>& array_holder) {
>        return helper::build(g, index, array_holder);
>      }
>    };
>  }
>
> And the corresponding default color helper resulting in VC6 compiler
> errors.
> (template already defined as non-template)
> I am stuck, if you could please advise me on how to rewrite these
templates
> for VC6.
>
>
> -----Original Message-----
> From: boost-bounces_at_[hidden] [mailto:boost-bounces_at_[hidden]]
> On Behalf Of Jeremiah Willcock
> Sent: 24. maj 2009 00:18
> To: boost_at_[hidden]
> Subject: Re: [boost] How to speed up the djikstra graph
>
> 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
> _______________________________________________
> Unsubscribe & other changes:
> http://lists.boost.org/mailman/listinfo.cgi/boost
>
> _______________________________________________
> Unsubscribe & other changes:
> http://lists.boost.org/mailman/listinfo.cgi/boost
>
_______________________________________________
Unsubscribe & other changes:
http://lists.boost.org/mailman/listinfo.cgi/boost