[boost] graph_search

From: jsiek_at_[hidden]
Date: 2000-01-09 14:02:42

Dave Abrahams writes:
 > graph_search.hpp does not seem to satisfy the criteria I had proposed 
 > earlier. Jeremy, can you show how it can be used to solve this problem:
 > 
 >     use best-first-search to make a copy of a lattice
 >     [to justify the best-first-search, you can label nodes in the
 > destination lattice with their least cost from the start node - but I see
 > that this is probably irrelevant from the point of view of the code]

This is the previous discussion you are referring to, yes?

bfs(first, visit, cost)
    q.push(0, first)
    while (!q.empty()):
        c, n = q.pop()
        if not visited(n):
            mark(n)
            if (visit(n)) return
            for e in n.outgoing():
                q.push(c+cost(e), e.destination)

There are a number of problems here. To begin with, you want to label nodes
with costs, so the visit function needs to get the cost somehow. Also, the
obvious place to copy the graph would be the "visit" function, but you don't
get an edge there so you'd have to distort the algorithm so it visits edges.
OK, no problem... except that you don't visit nodes which have already been
visited so you would only ever get a single incoming edge in the graph's
"copy" (it would be a tree). Dietmar's "algorithm iterator" might begin to
address the issue, but I wonder about its applicability in algorithms that
don't have a single, obvious "main loop" with an obvious point at which to
return.

So of the requirements, the only one that I see missing is the
ability to return, as in "if (visit(n)) return". Perhaps that
would be easy to add into part of visitor(discover, u, bag).

Ciao,

Jeremy