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-19 17:56:26

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