Boost logo

Boost :

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?

- Volodya

Boost list run by bdawes at, gregod at, cpdaniel at, john at