|
Boost : |
From: Lloyd J Lewins (llewins_at_[hidden])
Date: 2005-02-21 13:00:08
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]
+1 (310) 647-8832
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk