Boost logo

Boost :

From: David Abrahams (dave_at_[hidden])
Date: 2008-04-27 21:42:33


on Wed Mar 05 2008, Loïc Joly <loic.actarus.joly-AT-numericable.fr> wrote:

> Douglas Gregor a écrit :
>>
>>> I also want to redesign the searches for "stoppability" -
>>> either for user-selected termination (as per Loïc's request), or in
>>> the case of disjoint subgraphs.
>>>
>>
>> DFS supports a "TerminatorFunc" to stop early, but this might not be
>> the right approach. Why does everyone dislike throwing an exception
>> to terminate the search? I bet if someone went ahead and benchmarked
>> the two options, the exception would be faster for graphs of non-
>> trivial size.
>>
>
> There are two kind of early-stop. One is : "Stop the search". The other
> one is : "Stop looking in this direction, but continue the search".
>
> Throwing an exception may be a solution for the first category, but I
> don't see how is could help for the second. Maybe another way to go for
> the second would be to manually modify some well chosen colors in the
> visitor functions, but this approach seemed to scary for me to try it.

I would probably do that kind of pruning with a graph adaptor.

-- 
Dave Abrahams
Boost Consulting
http://boost-consulting.com

Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk