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@raytheon.com +1 (310) 647-8832
_______________________________________________ Jeremy Siek <jsiek@osl.iu.edu> http://www.osl.iu.edu/~jsiek Ph.D. Student, Indiana University Bloomington C++ Booster (http://www.boost.org) _______________________________________________