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

21 Jun 2009


      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@bl-logic.dk> 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@lists.boost.org [mailto:boost-bounces@lists.boost.org]
On Behalf Of Ross Levine
Sent: 21. juni 2009 05:17
To: boost@lists.boost.org
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@bl-logic.dk> 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@lists.boost.org [mailto:
boost-bounces@lists.boost.org]
On Behalf Of Jeremiah Willcock
Sent: 24. maj 2009 00:18
To: boost@lists.boost.org
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