This raises ValueError: property map 'dist_map' is not of scalar type. Is
there a function I can implement in Weights for it to return a scalar value
to be used during calculation of shortest path.
Secondly, consider a directed graph where the edge weight is a function of
cost at edge's origin vertex, i.e. the weight class is defined as:
class Weights:
....
def get_weight(current_cost):
return self.cost * current_cost
Hence during calculation of shortest_path/distance, is it possible to pass
the weight at the traversed/visited edge to get the cost of the edge.
This raises ValueError: property map 'dist_map' is not of scalar type. Is
there a function I can implement in Weights for it to return a scalar value
to be used during calculation of shortest path.
You should use the dijkstra_search() function, and specialize the
DijkstraVisitor class to do what you want.
Secondly, consider a directed graph where the edge weight is a function of
cost at edge's origin vertex, i.e. the weight class is defined as:
class Weights:
....
def get_weight(current_cost):
return self.cost * current_cost
Hence during calculation of shortest_path/distance, is it possible to pass
the weight at the traversed/visited edge to get the cost of the edge.
You can do that with the dijkstra_search() function, as I mentioned
above. However, note that multiplying weights is the same as summing
their logarithms... Hence you could simply use the log of the weights
instead, and save you some trouble.
From what I understand of Dijkstras search, Dijkstras visitor is invoked at
traversal of a vertex. However, this is still separate from the weights
which is a required argument the algorithm takes. In my case however, the
weight of traversing the edge is a function of cost of traversing to the
edge from the origin vertex.
I just used cost * weight as an example. In the actual algorithm,
weight(edge) = interval_search(cost(edge[origin_vertex] ), interval_map)
An actual use case would be finding the fastest route between two cities
given inconnecting flights across multiple intermediary cities. Depending
on departure time, there would be different routes recommended.
Hence, on arriving at an intermediary airport X at time T, the cost to
travel to the next possible intermediary airport Y would be a dependent on
T.
Read the documentation carefully. The visitor is invoked at several
event points, one of which is "examine_edge", which is called before any
edge is discovered by the algorithm. You can use this to set up the
weights. This seems to be exactly what you want.
One last bit. While using any of dijkstra/bellman_ford/astar_search
function, where is the list of edges for shortest path stored?
pred_map is a Vertex Property Map, so while this can give me the list of
visited vertices, I still can not find the edges which were chosen. Is
there a way to retrieve a list of edges in the shortest path as well?
If your graph does not contain parallel edges, you can simply call the
g.edge(pred_map[v], v) function. Otherwise you can simply store the
edges in a list as they are visited, by properly modifying the visitor
object.
If my understanding is correct, I can store the path via the edge_relaxed
function, where the latest call against edge_relax indicates the edge used.
Is this correct?