edge property for weighted search with vertex property for max_dist cutoff.
Hi all, How can I use a vertex property for search cutoff on graphs that are weighted based on an edge property? I want the search to visit the vertex based on the edge weights but the cutoff to be based on a vertex property. Thanks Tasos
On 10/11/2013 11:02 AM, Tasos Varoudis wrote:
Hi all,
How can I use a vertex property for search cutoff on graphs that are weighted based on an edge property? I want the search to visit the vertex based on the edge weights but the cutoff to be based on a vertex property.
I assume you are referring to Dijkstra's algorithm. If you want to abort the search at any given point, you have to raise an exception from the graph visitor. For example: class VisitorExample(gt.DijkstraVisitor): def __init__(self, prop): self.prop = prop def discover_vertex(self, u): if self.prop[u] > 10: raise gt.StopSearch() dist, pred = gt.dijkstra_search(g, g.vertex(0), weight, VisitorExample(prop)) I hope this helps. Cheers, Tiago -- Tiago de Paula Peixoto <tiago@skewed.de>
Hi and thanks, The difference between the solution below and that I need is that in order to compute the "cutoff prop" you need to follow the path that the visitor took and if the sum of the prop of the vertices that the visitor past is >X stop. How would you do that? thanks T -- View this message in context: http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/... Sent from the Main discussion list for the graph-tool project mailing list archive at Nabble.com.
On 10/14/2013 10:49 AM, Tasos wrote:
Hi and thanks,
The difference between the solution below and that I need is that in order to compute the "cutoff prop" you need to follow the path that the visitor took and if the sum of the prop of the vertices that the visitor past is >X stop.
How would you do that?
If you notice in the documentation, you'll see that the visitor object can specify all sorts of event points callbacks, which you can use to gather information during the run of the algorithm. The point where we distance of a vertex has been computed is the "examine_vertex" event point. Hence: class VisitorExample(gt.DijkstraVisitor): def __init__(self, dist, thresh): self.dist = dist self.thresh = thresh def examine_vertex(self, u): if self.dist[u] > self.thresh: raise gt.StopSearch() dist = g.new_vertex_property("double") visitor = VisitorExample(dist, 10) # don't forget to pass the same 'dist' property to the search # function as well dist, pred = gt.dijkstra_search(g, g.vertex(0), weight, visitor, dist_map=dist) Cheers, Tiago -- Tiago de Paula Peixoto <tiago@skewed.de>
Stupid question.. but Im probably missing something! Is it possible for the same Edge Weighted graph... graph_tool.search.dijkstra_search(g_DirG, dist_map=temp_dist, source=g_DirG.vertex(i), weight=eprop_ang_weight) graph_tool.topology.shortest_distance(g_DirG, dist_map=temp_dist, source=g_DirG.vertex(i), weights=eprop_ang_weight) the shortest_distance run a lot faster than dijkstra... I assume sort-dist is using dijkstra with some visitor to do the job. How is that possible? T -- View this message in context: http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/... Sent from the Main discussion list for the graph-tool project mailing list archive at Nabble.com.
On 10/14/2013 02:03 PM, Tasos wrote:
Stupid question.. but Im probably missing something!
Is it possible for the same Edge Weighted graph...
graph_tool.search.dijkstra_search(g_DirG, dist_map=temp_dist, source=g_DirG.vertex(i), weight=eprop_ang_weight) graph_tool.topology.shortest_distance(g_DirG, dist_map=temp_dist, source=g_DirG.vertex(i), weights=eprop_ang_weight)
the shortest_distance run a lot faster than dijkstra... I assume sort-dist is using dijkstra with some visitor to do the job. How is that possible?
It is simple. The dijkstra_search() function calls every event function of the supplied visitor, which is a _Python_ object. The shortest_distance() function has everything implemented in C++, hence the performance difference. Cheers, Tiago -- Tiago de Paula Peixoto <tiago@skewed.de>
participants (3)
-
Tasos -
Tasos Varoudis
-
Tiago de Paula Peixoto