Using a EdgePropertyMap('object') as weights

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

Using a EdgePropertyMap('object') as weights

ambasta
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.
Reply | Threaded
Open this post in threaded view
|

Re: Using a EdgePropertyMap('object') as weights

Tiago Peixoto
Administrator
On 18.09.2014 11:42, ambasta wrote:

> 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


--
Tiago de Paula Peixoto <[hidden email]>


_______________________________________________
graph-tool mailing list
[hidden email]
http://lists.skewed.de/mailman/listinfo/graph-tool

signature.asc (836 bytes) Download Attachment
--
Tiago de Paula Peixoto <tiago@skewed.de>
Reply | Threaded
Open this post in threaded view
|

Re: Using a EdgePropertyMap('object') as weights

Elliot
In reply to this post by ambasta

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

Elliot


_______________________________________________
graph-tool mailing list
[hidden email]
http://lists.skewed.de/mailman/listinfo/graph-tool
Reply | Threaded
Open this post in threaded view
|

Re: Using a EdgePropertyMap('object') as weights

ambasta
In reply to this post by Tiago Peixoto

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)

On Sep 18, 2014 7:01 PM, "Tiago Peixoto [via Main discussion list for the graph-tool project]" <[hidden email]> wrote:
On 18.09.2014 11:42, ambasta wrote:

> 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


--
Tiago de Paula Peixoto <[hidden email]>


_______________________________________________
graph-tool mailing list
[hidden email]
http://lists.skewed.de/mailman/listinfo/graph-tool

signature.asc (836 bytes) Download Attachment
--
Tiago de Paula Peixoto <[hidden email]>



To unsubscribe from Using a EdgePropertyMap('object') as weights, click here.
NAML
Reply | Threaded
Open this post in threaded view
|

Re: Using a EdgePropertyMap('object') as weights

ambasta
In reply to this post by Tiago Peixoto
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.

On Fri, Sep 19, 2014 at 1:15 AM, Amit Prakash Ambasta <[hidden email]> wrote:

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)

On Sep 18, 2014 7:01 PM, "Tiago Peixoto [via Main discussion list for the graph-tool project]" <[hidden email]> wrote:
On 18.09.2014 11:42, ambasta wrote:

> 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


--
Tiago de Paula Peixoto <[hidden email]>


_______________________________________________
graph-tool mailing list
[hidden email]
http://lists.skewed.de/mailman/listinfo/graph-tool

signature.asc (836 bytes) Download Attachment
--
Tiago de Paula Peixoto <[hidden email]>



To unsubscribe from Using a EdgePropertyMap('object') as weights, click here.
NAML



--
Ameno dom, Domi ne reo
Amit
Reply | Threaded
Open this post in threaded view
|

Re: Using a EdgePropertyMap('object') as weights

Tiago Peixoto
Administrator
In reply to this post by ambasta
On 18.09.2014 21:46, ambasta wrote:
> 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.

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

--
Tiago de Paula Peixoto <[hidden email]>
_______________________________________________
graph-tool mailing list
[hidden email]
http://lists.skewed.de/mailman/listinfo/graph-tool
--
Tiago de Paula Peixoto <tiago@skewed.de>
Reply | Threaded
Open this post in threaded view
|

Re: Using a EdgePropertyMap('object') as weights

ambasta
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.

On Fri, Sep 19, 2014 at 4:09 AM, Tiago Peixoto [via Main discussion list for the graph-tool project] <[hidden email]> wrote:
On 18.09.2014 21:46, ambasta wrote:
> 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.

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

--
Tiago de Paula Peixoto <[hidden email]>
_______________________________________________
graph-tool mailing list
[hidden email]
http://lists.skewed.de/mailman/listinfo/graph-tool
--
Tiago de Paula Peixoto <[hidden email]>



To unsubscribe from Using a EdgePropertyMap('object') as weights, click here.
NAML



--
Ameno dom, Domi ne reo
Amit
Reply | Threaded
Open this post in threaded view
|

Re: Using a EdgePropertyMap('object') as weights

ambasta
In reply to this post by Tiago Peixoto
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 ?

On Mon, Nov 17, 2014 at 3:00 PM, Amit Prakash Ambasta <[hidden email]> wrote:
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.

On Fri, Sep 19, 2014 at 4:09 AM, Tiago Peixoto [via Main discussion list for the graph-tool project] <[hidden email]> wrote:
On 18.09.2014 21:46, ambasta wrote:
> 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.

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

--
Tiago de Paula Peixoto <[hidden email]>
_______________________________________________
graph-tool mailing list
[hidden email]
http://lists.skewed.de/mailman/listinfo/graph-tool
--
Tiago de Paula Peixoto <[hidden email]>



To unsubscribe from Using a EdgePropertyMap('object') as weights, click here.
NAML



--
Ameno dom, Domi ne reo
Amit



--
Ameno dom, Domi ne reo
Amit
Reply | Threaded
Open this post in threaded view
|

Re: Using a EdgePropertyMap('object') as weights

Tiago Peixoto
Administrator
In reply to this post by ambasta
On 17.11.2014 10:31, ambasta wrote:
> 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.

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

Best,
Tiago

--
Tiago de Paula Peixoto <[hidden email]>


_______________________________________________
graph-tool mailing list
[hidden email]
http://lists.skewed.de/mailman/listinfo/graph-tool

signature.asc (836 bytes) Download Attachment
--
Tiago de Paula Peixoto <tiago@skewed.de>
Reply | Threaded
Open this post in threaded view
|

Re: Using a EdgePropertyMap('object') as weights

ambasta
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?

On Mon, Nov 17, 2014 at 7:13 PM, Tiago Peixoto [via Main discussion list for the graph-tool project] <[hidden email]> wrote:
On 17.11.2014 10:31, ambasta wrote:
> 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.

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

Best,
Tiago

--
Tiago de Paula Peixoto <[hidden email]>


_______________________________________________
graph-tool mailing list
[hidden email]
http://lists.skewed.de/mailman/listinfo/graph-tool

signature.asc (836 bytes) Download Attachment
--
Tiago de Paula Peixoto <[hidden email]>



To unsubscribe from Using a EdgePropertyMap('object') as weights, click here.
NAML



--
Ameno dom, Domi ne reo
Amit
Reply | Threaded
Open this post in threaded view
|

Re: Using a EdgePropertyMap('object') as weights

Tiago Peixoto
Administrator
On 17.11.2014 15:16, ambasta wrote:
> 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.

Best,
Tiago

--
Tiago de Paula Peixoto <[hidden email]>


_______________________________________________
graph-tool mailing list
[hidden email]
http://lists.skewed.de/mailman/listinfo/graph-tool

signature.asc (836 bytes) Download Attachment
--
Tiago de Paula Peixoto <tiago@skewed.de>
Reply | Threaded
Open this post in threaded view
|

Re: Using a EdgePropertyMap('object') as weights

ambasta
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?

On Mon, Nov 17, 2014 at 7:52 PM, Tiago Peixoto [via Main discussion list for the graph-tool project] <[hidden email]> wrote:
On 17.11.2014 15:16, ambasta wrote:
> 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.

Best,
Tiago

--
Tiago de Paula Peixoto <[hidden email]>


_______________________________________________
graph-tool mailing list
[hidden email]
http://lists.skewed.de/mailman/listinfo/graph-tool

signature.asc (836 bytes) Download Attachment
--
Tiago de Paula Peixoto <[hidden email]>



To unsubscribe from Using a EdgePropertyMap('object') as weights, click here.
NAML



--
Ameno dom, Domi ne reo
Amit
Reply | Threaded
Open this post in threaded view
|

Re: Using a EdgePropertyMap('object') as weights

Tiago Peixoto
Administrator
On 17.11.2014 15:42, ambasta wrote:
> 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?

Yes, this is correct.

Best,
Tiago

--
Tiago de Paula Peixoto <[hidden email]>


_______________________________________________
graph-tool mailing list
[hidden email]
http://lists.skewed.de/mailman/listinfo/graph-tool

signature.asc (836 bytes) Download Attachment
--
Tiago de Paula Peixoto <tiago@skewed.de>