Weight as a function of distance at source

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()); }

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

In a way, yes. But I don't see where dijkstra would fail here given the weights are always positive. A regular bfs from a given start time should populate the distances to all nodes, identical to dijkstra On Fri, Dec 18, 2020 at 6:39 AM Alex Hagen-Zanker < a.hagen-zanker@surrey.ac.uk> wrote:
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

In a way, yes. But I don't see where dijkstra would fail here given the weights are always positive. A regular bfs from a given start time should populate the distances to all nodes, identical to dijkstra
I think you are right, as long as you cannot get a better connection by arriving later. The combine function is supposed to combine a distance and a weight, typically these are the same type. Perhaps you are better off incorporating the waiting time in your weight property map. You might be able to do this using the function_property_map (https://www.boost.org/doc/libs/1_59_0/libs/property_map/doc/function_propert... ). Or to create your own property map, similar to this: template<class G, class DistanceMapType, class TravelTimeMapType> class weightmap { using distance_type = int; using weight_type = int; public: using key_type = Edge<G>; using value_type = weight_type; using reference = weight_type; using category = boost::readable_property_map_tag; weight_type get(const Edge<G>& e) const { weight_type travel = get(travel_time_map,e); distance_type distance = get(distance_map, boost::source(e)); weight_type wait = 60 - distance % 60; // assuming hourly service return travel + wait; } private: DistanceMapType distance_map; // total time to each vertex TravelTimeMapType travel_time_map; // time to travel over each edge }; template<class G> int get(const weightmap<G>& w, const Edge<G>& e) { return w.get(e); }. On Fri, Dec 18, 2020 at 6:39 AM Alex Hagen-Zanker <a.hagen-zanker@surrey.ac.uk<mailto:a.hagen-zanker@surrey.ac.uk>> wrote:
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
participants (2)
-
Alex Hagen-Zanker
-
Amit Prakash Ambasta