[boost] Re: graph_search

From: Dave Abrahams (abrahams_at_[hidden])
Date: 2000-01-09 14:56:58

> I'll have to think about this more :) Also, are there any references
> I can look at that describe in more detail the algorithm you are
> using?

No, but it's not too strange. The code you posted before was an "obvious"
best-first-search, which I posted to illustrate why an obvious approach
might not be sufficiently flexible. What I ended up doing was something more
like this (which is obviously too specialized for a graph algorithm
library):

search_and_copy(first, visit, cost)
    result = new_graph()
    q.push(0, path(first))       // adds an empty path starting at first
    while (!q.empty()):
        c, p = q.pop()

        if (p.last_edge())
            result.add_edge(p.last_edge())

        n = p.last_node()

        if not visited(n):
            mark(n)
            if (visit(n, c)) return    // visit the node with the new cost
            for e in n.outgoing():
                q.push(c+cost(e), path(p, e))

Some key changes to the original algorithm:
    1. edges or paths go in the queue instead of vertices
    2. costs are passed to the visit function

It might be possible to do this more straightforwardly with an adapter which
maps edges to vertices, but it's not clear how you'd do that. You'd also
need a dummy incoming edge for the start vertex.

-Dave