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 08:50:12

> I think the question was asking for a path of arbitrary length;
>>
> Indeed. Maybe there is a better term for the property "directly or
> indirectly connected", isn't there?

Transitively connected?

 in that case, breadth_first_search or depth_first_search would find the
> path.
>
The problem here is that we need to stop the search once we've found a
> connection. But neither BFS visitors nor DFS visitors seems to give us a
> chance to cancel the search. The discover_vertex visitor could have this
> ability (I slightly remember that I had the problem to cancel a search in
> BGL some years ago and I wasn't able to solve it by then too)
>

 The most promising (i.e., least invasive) solution to prematurely stopping
an algorithm has been to simply throw and catch an exception. Another trick
was to give your visitor a reference to the queue and color map and then
empty the queue and color any other vertices black to make the algorithm
think that it's done.

Andrew Sutton
andrew.n.sutton_at_[hidden]