From: Vladimir Prus (ghost_at_[hidden])
Date: 2002-01-25 07:10:24
suppose I have a directed graph where vertices are labelled with a
string. Given a vertex, if would like to gather the set of vertices such that
1. They have non-empty label
2. There's a path from start vertex to each of them, which does not pass
through any vertex with non-empty label.
'depth_first_visit' can do almost all I want, but can't enforce (2) -- I need
to be able to stop recursion once a vertex with non-empty label is found.
Would it be reasonable to change the type of DFSVisitor::discover_vertex to
bool, so that out-edges are not examined at all when it returns false. If the
change will cause too much inconvenience for the already written code, maybe
method like 'processing_needed' can be added?
BTW, I'm confused by docs to DFSVisitor::finish_vertex:
This invoked on a vertex after all of its out edges have been added to
the search tree and all of the adjacent vertices have been discovered
(but before their out-edges have been examined).
I don't understand the statement about out-edges of the adjacent vertices. In
fact, depth_first_visit_impl is called and all adjacent vertices and it will
traverse out-edges. Am I wrong?
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk