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