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

From: Loïc Joly (loic.joly_at_[hidden])
Date: 2006-11-22 12:48:26

I'd like to resurect an old thread, because I think it really make using 
BGL algorithms more difficult than they should.

Vladimir Prus a écrit :
> 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.

In my case, I don't want to abort the visit when I have found a node 
with some criteria, I just want to stop visiting further nodes from this 
node. So the exception stuff is not an option. The TerminatorFunc might 
seem a good option, but I want something slightly different. In my case, 
I'd like a termination function called when discovering the edge between 
A and B, that allows me to discard B, C and D, based on some information 
depending on both A and B.

TerminatorFunc consider just one of the several points where we might 
stop visiting a graph. We already have a visitor concepts that exposes 
all interresting points in the algorithm, and I think some of the 
iterator functions might return a boolean values, to act like 
TerminatorFunc, but with a flexibility that will make it useable by all 
users.

With the current BGL, the alternatives I see are:
- Use my own DFS algorithms that can conditionally stop, probably less 
performant, with bugs... which defeats the purpose of the BGL.
- Use current algorithm, but in the visitor functions, manually change 
some colors in the color map to lure DFS into doing what I want. I don't 
feel I have enough knowledge to do this confidently.

Best regards,

-- 
Loïc