Re: [boost] [BGL] depth_first_visitor improvement?

From: Douglas Gregor (gregod_at_[hidden])
Date: 2002-01-25 07:22:05

On Friday 25 January 2002 07:10 am, you wrote:
> Hi,
> 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?

It sounds like you want a filtered_graph where the vertex predicate weeds out 
all vertices that have empty labels. Then run your depth-first search on the 
filtered_graph.

        Doug