edge property for weighted search with vertex property for max_dist cutoff.

graph-tool
1

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

2

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

3

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

4

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

5

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

6

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