[Boost-users] [BGL] Parameter: CompareFunction - dijkstra_shortest_paths

From: Leandro T. C. Melo (ltcmelo_at_[hidden])
Date: 2007-07-28 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.