Re: [boost] Summer of Code 2008 [Graph version 2]

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