Using a EdgePropertyMap('object') as weights

Hi,

I have two problems

class Weights:
  ...

g = Graph(directed=True)
weights = g.new_edge_property('object')

vertex_one = g.add_vertex()
vertex_two = g.add_vertex()
edge = g.add_edge(vertex_one, vertex_two)
weights[edge] = Weights(1)

g.shortest_path(vertex_one, vertex_two, weights)

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.

Hi,

I have two problems

class Weights:
  ...

g = Graph(directed=True)
weights = g.new_edge_property('object')

vertex_one = g.add_vertex()
vertex_two = g.add_vertex()
edge = g.add_edge(vertex_one, vertex_two)
weights[edge] = Weights(1)

g.shortest_path(vertex_one, vertex_two, weights)

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.

Take a look at the search module:

     https://graph-tool.skewed.de/static/doc/search_module.html

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.

Best,
Tiago

You gave the property map the datatype "object", which is not a scalar.

Elliot

attachment.html (123 Bytes)

Hi

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)

attachment.html (5.86 KB)

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.

attachment.html (6.81 KB)

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.

Best,
Tiago

Hi Tiago,

I've tried using examine_edge. However it still doesn't cover the use case
I mentioned where

Cost(edge) = function(edge, Cost_path_until_edge) =
edge[interval_lookup(Cost_path_until_edge, edge.intervals)][cost_interval]

Specifically, before I compute the weight/cost of the edge, I need the cost
calculated at the visitor to the edge.

Since only a single argument u(edge) is passed, I am unable to retrieve the
cost at the visitor attempting to travel via this edge.

attachment.html (4.59 KB)

However, since its invoked at every out of edge of a vertex being visited,
is it possible to find out the cost at the vertex using
*dist_map ?*

attachment.html (5.27 KB)

Just store a property map with costs, and query it using u.source().

Best,
Tiago

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?

attachment.html (4.37 KB)

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.

Best,
Tiago

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?

attachment.html (4.52 KB)

Yes, this is correct.

Best,
Tiago