Weight as a function of distance at source

From: Amit Prakash Ambasta (amit.prakash.ambasta_at_[hidden])
Date: 2020-12-17 03:31:43

Hi,

Looking at BGL implementations, weight, compare and combine are used in
examine edge(e) as

compare(combine(old_distance, get(weight, e)), old_distance)

Additionally, old_distance = m_zero to check for negative weights etc.

In my implementation, edges have a bundled property

struct EdgeProp {
    Distance weight(Distance start) { ... }
};

that returns the cumulative weight on iterating over the edge given a start
distance.

To use this, I should be able to pass a combine function of the form

[]<typename BinaryFunction>(DistanceType d, BinaryFunction f) { return
f(d); }

However, this approach falls apart.

I've tried putting together a formal example here, but not sure why this
fails. (My actual use case is where weights represent nodes in a transport
system and for a person arriving at a vertex at some time Tx, there is a
variable weight of using the next outbound transport = waiting_time +
travel_time, where waiting_time is a function of Tx

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <limits>

struct VProp
{};

struct EProp
{
  int multiplier;

  int weight(int src_distance) { return src_distance * multiplier; }
};

typedef boost::
adjacency_list<boost::vecS, boost::vecS, boost::directedS, VProp, EProp>
  Graph;

template<class G>
using Vertex = boost::graph_traits<G>::vertex_descriptor;

template<class G>
using Edge = boost::graph_traits<G>::edge_descriptor;

int
main()
{
  Graph graph;
  auto source = boost::add_vertex(VProp{}, graph);
  auto target = boost::add_vertex(VProp{}, graph);

  boost::add_edge(source, target, EProp{ 3 }, graph);

  auto index_map = get(boost::vertex_index, graph);

  std::vector<Vertex<Graph>> predecessors(boost::num_vertices(graph));

  auto predecessor_map =
boost::make_iterator_property_map(predecessors.begin(), index_map);

  std::vector<int> distances(boost::num_vertices(graph));
  auto distance_map =
boost::make_iterator_property_map(distances.begin(), index_map);

  auto compare = [](int lhs, int rhs) -> bool { return lhs < rhs; };

  auto combine = []<typename BinaryFunction>(int dst, BinaryFunction
f) -> int { return f(dst); };

  boost::dijkstra_shortest_paths(
    graph,
    source,
    predecessor_map,
    distance_map,
    boost::weight_map(boost::get(&EProp::weight, graph)),
    index_map,
    compare,
    combine,
    std::numeric_limits<int>::min(),
    std::numeric_limits<int>::max(),
    boost::default_dijkstra_visitor());
}