[boost] Re: graph_search

From: jsiek_at_[hidden]
Date: 2000-01-12 13:30:49

Dave,

Couple questions:

what does last_edge() do?
what happens inside your visit() function?

Dave Abrahams writes:
 > 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