# Weight as a function of distance at source

4 messages
Open this post in threaded view
|

## Weight as a function of distance at source

 Hi,Looking at BGL implementations, weight, compare and combine are used in examine edge(e) ascompare(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[](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 struct VProp{};struct EProp{ int multiplier; int weight(int src_distance) { return src_distance * multiplier; }};typedef boost::adjacency_list Graph;templateusing Vertex = boost::graph_traits::vertex_descriptor;templateusing Edge = boost::graph_traits::edge_descriptor;intmain(){ 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 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 = [](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::min(), std::numeric_limits::max(), boost::default_dijkstra_visitor());}` _______________________________________________ Boost-users mailing list [hidden email] https://lists.boost.org/mailman/listinfo.cgi/boost-users
Open this post in threaded view
|

## Re: Weight as a function of distance at source

 >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. That sounds like you intend to calculate a *dynamic* shortest path, which is not what Dijkstra's algorithm does for you. I know it doesn't answer your question, but I think it is more pertinent. Kind regards, Alex _______________________________________________ Boost-users mailing list [hidden email] https://lists.boost.org/mailman/listinfo.cgi/boost-users