
Boost Users : 
From: Leandro T. C. Melo (ltcmelo_at_[hidden])
Date: 20070728 10:26:27
Hello all.
It is clear for me the reason for template parameter CombineFunction
in dijkstra_shortest_paths. For instance, prim_minimum_spanning_tree
makes use of it to correct compute the MST. Basically, in Dijkstra's
it is something like this:
distance = distance of vertex v + weight of edge e;
And in Prim's only the weight is considered:
distance = weight of edge e;
This is reflected on the argument used for the CombineFunction in
Prim's function (from file prim_minimum_spanning_tree.hpp):
prim_minimum_spanning_tree(...)
{
typedef typename property_traits<WeightMap>::value_type W;
std::less<W> compare;
detail::_project2nd<W,W> combine;
dijkstra_shortest_paths(...);
}
Where _project2nd is:
template <class U, class V> struct _project2nd
{
V operator()(U, V v) const { return v; }
};
However, it is not clear the reason of the CompareFunction template
parameter (which is a predicate). First, because, I don't see a
situation where not using std::less<Some_type> would make any sence,
because of the way the Dijkstra's algorithm is constructed. Second,
because the value_type of the DistanceMap must be the same of the
value_type of WeightMap (according to the documentation). Therefore,
why the following two lines of code in Prim's implementation (from the
function I pointed at beginning of the email)?
typedef typename property_traits<WeightMap>::value_type W;
std::less<W> compare;
Since, in Dijkstra's algorithm the only difference is that DistanceMap
is used as an argument for the definition of the value_type from
property_traits. Am I loosing something here? If yes, would anyone
explain it to me?
Thank you,
Leandro.
Boostusers list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net