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()
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]
--
I'd rather not implement my solution in C++, because BGL looks complex to say the least!
Thanks,
Jeremy