Help calculating best path

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.

2011/11/3 akn <a.kn(a)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

attachment.html (2.79 KB)