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