Weight as a function of distance at source

classic Classic list List threaded Threaded
4 messages Options
Reply | Threaded
Open this post in threaded view
|

Weight as a function of distance at source

Boost - Users mailing list
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());
}

_______________________________________________
Boost-users mailing list
[hidden email]
https://lists.boost.org/mailman/listinfo.cgi/boost-users
Reply | Threaded
Open this post in threaded view
|

Re: Weight as a function of distance at source

Boost - Users mailing list
>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
Reply | Threaded
Open this post in threaded view
|

Re: Weight as a function of distance at source

Boost - Users mailing list
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 <[hidden email]> 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


_______________________________________________
Boost-users mailing list
[hidden email]
https://lists.boost.org/mailman/listinfo.cgi/boost-users
Reply | Threaded
Open this post in threaded view
|

Re: Weight as a function of distance at source

Boost - Users mailing list

 

>>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_property_map.html ).

 

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 <[hidden email]> 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

 


_______________________________________________
Boost-users mailing list
[hidden email]
https://lists.boost.org/mailman/listinfo.cgi/boost-users