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

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

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

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

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

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

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