Hi I am trying to graph-tool solve specific path finding problems. I have
been using NetworkX in past but found it too slow and read good thing about
graph-tool's speed.
Basically I have 2 million + vertices and I want to find best path between 2
points (considering their weight and travel time i.e. cost).
Now Im really interested in astar I can't seem to get it work for some
reason. So in my scenario Im trying to do this:
from graph_tool.all import *
g = Graph()
v0 = g.add_vertex()
v1 = g.add_vertex()
v2 = g.add_vertex()
v3 = g.add_vertex()
v4 = g.add_vertex()
weight = g.new_edge_property("double")
e_1_2 = g.add_edge(v1,v2)
weight[e_1_2] = 1000
e_1_3 = g.add_edge(v1,v3)
weight[e_1_3] = 100
e_3_4 = g.add_edge(v3,v4)
weight[e_3_4] = 200
e_4_2 = g.add_edge(v4,v2)
weight[e_4_2] = 40
class VisitorExample(graph_tool.search.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 gt.StopSearch()
touch_v = g.new_vertex_property("bool")
touch_e = g.new_edge_property("bool")
target = v2
gt = graph_tool.search
time = g.new_vertex_property("int")
pred = g.new_vertex_property("int")
dist, pred = gt.astar_search(g, v1, weight,
VisitorExample(touch_v, touch_e, target),
heuristic=lambda v: 1)
Now I would "astar" to consider weights and choose the best path based on
weight. For example weight for edge (1 & 2) = 1000, so travel from 1 -> 2 I
would like to get a path 1 -> 3 -> 4 > 2 because combined weight of this is
still less than that of 1 -> 2. But when I get the results it only gives
edge 1 & 2 and wouldn't consider the above path.
Could you also shed some light on setting up heuristics and costing
functions for the above scenario.
Thank you.
--
View this message in context:
http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/Help-calculating-best-path-tp3478127p3478127.html
Sent from the Main discussion list for the graph-tool project mailing list
archive at Nabble.com.
_______________________________________________
graph-tool mailing list
[email protected]
http://lists.skewed.de/mailman/listinfo/graph-tool
