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/... Sent from the Main discussion list for the graph-tool project mailing list archive at Nabble.com.
2011/11/3 akn a.kn@live.com
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:
[cut]
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.
At first glance (I don't have my reference books here, so I can't look at the gory details of A*), the problem with your code is that the edge (v1,v2) is the first one evaluated by the algorithm and thus it is the first one relaxed because the default distance value is modified from inf to 1000. Then, no other edge is considered, because the algorithm ends.
A workaround could be to erase the edge_relaxed method and use this code instead:
def examine_vertex(self, v): if v == self.target: raise gt.StopSearch()
As you can see, the path is evaluated as 1->3->4->2 with a total cost of 340. This happens because the algorithm now stops only when the target node is the first in the queue (i.e. the closest).
I'm not sure that this one is the best approach, I'll check Nilsson's book and Russel & Norvig later, just to be sure.
For the heuristics, if your graph represents a geographic map (i.e. you have x,y atributes for each node) you could use manhattan distance or euclidean distance: as far as your h function doesn't overestimate the real distance, A* will be fine.
Hope it helps, Giuseppe
-
akn -
Giuseppe Profiti