Boost logo

Boost :

Subject: Re: [boost] How to speed up the djikstra graph
From: Ross Levine (ross.levine_at_[hidden])
Date: 2009-06-21 15:48:33


For A*, a heuristic should be ideally less than the actual minimum distance
from the current point to the end. So for example, euclidean distance is
often used. Also, A* tends to be faster if the Heuristic is good, since it
tests fewer paths.

On Sun, Jun 21, 2009 at 9:44 AM, Lennart Berg <LB_at_[hidden]> wrote:

> 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
>
> _______________________________________________
> Unsubscribe & other changes:
> http://lists.boost.org/mailman/listinfo.cgi/boost
>


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk