Re: [Boost-users] [BGL] how to actually search with DFS/BFS?

From: Douglas Gregor (doug.gregor_at_[hidden])
Date: 2005-06-23 09:21:04

On Jun 23, 2005, at 2:42 AM, Vladimir Prus wrote:
> 2. TerminatorFunc does not do what you're asking for. It does not 
> terminate
> the search as soon as you find a certain vertces -- for that exception 
> is
> fine. The TerminatorFunc parameter prevents the search to go *past* 
> certain
> vertices.
>
> Consider:
>
>
>    A ------- B -------- C ----------- D
>     \
>      \
>       \
>        E ------ F -------- G
>
> If terminator func returns true on 'B', then depth_first_visit will 
> visit
> 'A', 'B', 'E', 'F', and 'G', but not 'C' or 'D'. It was invented (by 
> me)
> exactly for that purpose. I wanted to find all paths starting at a 
> given
> vertex ending is a special 'terminating' vertices.

Ah, right. I remember this discussion now. But I don't remember why 
filtered_graph wasn't a better answer.

> Lastly, I don't think adding this parameter to depth_first_*search* 
> (as Doug
> suggested), I doubt it's needed. DFS will visit all vertices, and if 
> you
> want to find a vertex satisfying a predicate you can use the 'find_if'
> algorithm ;-)

I think it's rather a question of reachability... can I get to vertex v 
from vertex u.

        Doug