Re: [Boost-users] [BGL] simple problem: how to detect connections in a dag?

Subject: Re: [Boost-users] [BGL] simple problem: how to detect connections in a dag?
From: Andrew Sutton (andrew.n.sutton_at_[hidden])
Date: 2010-01-06 11:30:22

> You can throw from discover_vertex visitor.
>>
> Somehow I was afraid of that answer. Is an early stop such an exceptional
> use case that exceptions are the proper solution?
> Or should I consider this rather a limitation of BGL (rendering it useless
> for us as I will not introduce exceptions as part of the normal execution
> path). I wonder if this problem occurs so infrequent that there is no real
> built-in solution
>

Like I said before you, can build a visitor that keeps a reference to the
BFS's internal queue and flush it when you want to terminate the search.
It's not as efficient as throwing an exception since clearing the queue is
O(n), but it should still work. You'd probably want to flush the queue on
finish_vertex so you guarantee that you won't pick up any new vertices in
the next loop.

You could also rewrite the search algorithm to include an explicit stopping
point. The core BFS implementation is probably only 20 lines of fairly
straightforward code.

Andrew Sutton
andrew.n.sutton_at_[hidden]