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 combine;
dijkstra_shortest_paths(...);
}
Where _project2nd is:
template 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 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.
