[boost] Re: Priority Queue in boost::graph::dijkstra_shortest_paths

From: Jeremy Siek (jsiek_at_[hidden])
Date: 2005-02-21 13:11:35

The dijkstra_shortest_paths function does not use std::less, but
instead indirect_cmp, which indirects to the distance map to get
the distance of the vertex.

Cheers,
Jeremy

On Feb 21, 2005, at 1:00 PM, Lloyd J Lewins wrote:

> Perhaps I am missing something, but I don't see how
> dijkstra_shortest_paths works currently.
>
> The priority queue (mutable_queue) in dijkstra_shortest_paths should 
> order
> (gray) vertices by their distance from the source vertex. The ordering 
> of
> the mutable_queue is achieved by the compare function, which therefore
> should order vertices by examining the distance map. However, the 
> default
> compare function is simply std::less<D>(), where D is the value_type of
> the distance map. I.e., the compare simply orders the vertices by their
> vertex_descriptor, using less for the value_type (essentially a cast). 
> I
> would think what is really needed is a less function which is bound to 
> the
> distance map, and compares based off distance. For example:
>
>     template<class Map>
>     class less : public std::binary_function<typename
> boost::property_traits<Map>::value_type,
>                                               typename
> boost::property_traits<Map>::value_type, bool>
>     {
>         typedef typename boost::property_traits<Map>::key_type   
> key_type;
>         typedef typename boost::property_traits<Map>::value_type
> value_type;
>
>     public:
>         explicit less(Map& m)
>             : m(m)
>         {
>         }
>
>         bool operator() (const key_type k1,
>                          const key_type k2) const
>         {
>             return m[k1] < m[k2];
>         }
>
>     private:
>         const Map& m;
>     };
>
> In which case the compare function would be somethink like:
> less<DistanceMap>(distance).
>
> Lloyd J. Lewins
> Fellow,
> Raytheon Co.,
> llewins_at_[hidden]
> [phone]
>
_______________________________________________
Jeremy Siek <jsiek_at_[hidden]>
http://www.osl.iu.edu/~jsiek
Ph.D. Student, Indiana University Bloomington
C++ Booster (http://www.boost.org)
_______________________________________________