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

From: Vladimir Prus (ghost_at_[hidden])
Date: 2005-06-23 02:42:33

Thomas Costa wrote:

> Will a future version of BGL have a "TerminatorFunc" in all the
> visitor types?
> 
> Throwing an exception as part of the "normal" flow of an algorithm
> seems to go against most people's C++ philosophy.

There are two points to note. 

1. As Peter Dimov said (IIRC), exceptions are just non-local goto. In this
case, non-local goto is fine.

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.

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 ;-)

- Volodya