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
#include
#include <limits>
struct VProp
{};
struct EProp
{
int multiplier;
int weight(int src_distance) { return src_distance * multiplier; }
};
typedef boost::
adjacency_list
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 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());
}
