On 16.05.2015 12:01, Jeremy Herbert wrote:
Hi all,
First, thanks very much for creating this library. It has helped me a great deal to fiddle with graph algorithms in the comfort of my favourite language!
I'm currently having trouble performing an astar search on an explicit undirected graph. The graph I have is not crazy large (50,000 vertices with ~150,000 edges), but I need to perform a large number of astar searches (on the order of the number of vertices). As the python visitor class instance is required for the astar to terminate, it seems I'm having quite poor performance as a result of many calls back to python:
ncalls tottime percall cumtime percall filename:lineno(function) 88138526 116.708 0.000 153.115 0.000 __init__.py:113(wrapped_visitor_member) 4202 110.596 0.026 302.442 0.072 __init__.py:1195(astar_search) 88138526 34.008 0.000 38.130 0.000 __init__.py:107(__getattr__) 264384698 30.718 0.000 30.718 0.000 {method 'update' of 'dict' objects} 88090728 5.512 0.000 5.512 0.000 __init__.py:1132(initialize_vertex) 88138690 4.122 0.000 4.122 0.000 {built-in method callable} 33616 0.146 0.000 0.152 0.000 __init__.py:1415(vertex)
In this case, the only function in my visitor class that is defined is: def edge_relaxed(self, e): if e.target() == self.end: raise StopSearch()
Unfortunately, there is really not much one can do. Since the visitor needs to be exposed via python, it needs to have python callbacks, which are very slow. It seems to me that the only viable alternative is to implement it fully in C++.
I've also tried looking at doing the search implicitly, but I can't for the life of me get it to work. I tried to copy the original euclidean astar example from the documentation and convert it to implicit, but it doesn't seem to work. Could anyone tell me what I'm doing wrong here? I'm guessing that some of the function arguments listed as optional are not so ;)
from graph_tool.search import StopSearch, AStarVisitor, astar_search import graph_tool.generation as gt
from numpy.random import random from math import sqrt
class VisitorExample(AStarVisitor):
def __init__(self, touched_v, touched_e, target): self.touched_v = touched_v self.touched_e = touched_e self.target = target
def discover_vertex(self, u): self.touched_v[u] = True
def examine_edge(self, e): self.touched_e[e] = True
def edge_relaxed(self, e): if e.target() == self.target: raise StopSearch()
def h(v, target, pos): return sqrt(sum((pos[v].a - pos[target].a) ** 2))
points = random((500, 2)) * 4 points[0] = [-0.01, 0.01] points[1] = [4.01, 4.01] g, pos = gt.triangulation(points, type="delaunay") weight = g.new_edge_property("double") # Edge weights corresponding to # Euclidean distances for e in g.edges(): weight[e] = sqrt(sum((pos[e.source()].a - pos[e.target()].a) ** 2)) touch_v = g.new_vertex_property("bool") touch_e = g.new_edge_property("bool")
target = g.vertex(1) dist, pred = astar_search(g, g.vertex(0), weight, VisitorExample(touch_v, touch_e, target), implicit=True, heuristic=lambda v: h(v, target, pos))
print(pred.a)
# output is:
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
--
The above seems identical to the example in the documentation. What is implicit here? Best, Tiago -- Tiago de Paula Peixoto <tiago@skewed.de>