Paths from search

[saulshanabrook]

I am trying to use A* search to get a a path (the list of edges) between two nodes. I don't care about the intermediary nodes, just the edges/actions between them. I just wrote a function that wraps AStar to do this:

// AStarEdges returns the list of edges from s -> t using the AStar algorithm
func AStarEdges(s, t graph.Node, g graph.Graph, h path.Heuristic) ([]graph.Edge, error) {
    p, _ := path.AStar(s, t, g, h)
    ns, w := p.To(t)
    if w == math.Inf(1) {
        return nil, errors.New("Can't find path")
    }
    es := make([]graph.Edge, 0, len(ns))
    prevN := s
    for _, n := range ns {
        es = append(es, g.Edge(prevN, n))
        prevN = n
    }
    es = append(es, g.Edge(prevN, t))

    return es, nil
}

But this seems like a waste of computation, since the A* search has to figure out the edges anyway. Is there a simpler/easier way to do this?

[kortschak]

This relates to the answer for your other issue (BTW, both of these probably would do better as a post to gonum-dev). The results of a path search are not necessarily unique theoretically, and practically, we think this is important, so we provide a mechanism to get all shortest paths from a source to a destination. Retaining all the edge information for this would potentially be very expensive. Remember that |E| >> |V| for many graphs.

[saulshanabrook]

@kortschak That makes sense. I think for my use case, I will just roll my own A* search that maintains just the information I need. Thanks for the response.

[kortschak]

You may want to benchmark first. The pathtree approach is very efficient.