Re: [boost] Re: halting graph algorithms

From: Vladimir Prus (ghost_at_[hidden])
Date: 2003-09-12 01:19:51

Hi Dave,

Dave Harris wrote:

> > Another possible problem is that performance may suffer. Personally, I
> > don't know if this is true. The algorithm has a lot of code already,
> > and single if statement might have negligible effect.
>
> I've not looked at your specific graph visitor code, but I have some
> general comments. In my experience with visitor it is best to move the
> data traversal out of the nodes and into the visitor class itself, and
> keep it separate from type discovery. This gives the author of a visitor
> subclass more control, and allows him to use instance variables to
> communicate instead of returning bools.

What you say above and the code which I've snipped is interesting. In fact, I 
implemented recursive visitor once, and made visitor do the traversal -- just 
as you propose -- though the motivation probably was different (it allows 
visitor to decide if children should be visited, or not and besides, the 
traversal code is exactly the same for all kinds of nodes).

Probably, this technique you describe could be used there, though I decided 
that each visitor method will return either "stop" or "recurse" explicitly, 
to avoid errors.

But the problem is that it cannot be applied to BGL. First the traversal 
algorithm is a big monolithic entity. Second, we're looking not for a way to 
avoid traversing children of a given vertex, but to immediately halt the 
entire algorithm on certain condition.

Still, thanks for suggestion!

- Volodya