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