Re: [boost] Re: halting graph algorithms

From: Vladimir Prus (ghost_at_[hidden])
Date: 2003-09-18 05:08:50

Dave Harris wrote:

> > [...] But the problem is that it cannot be applied to BGL. First the
> > traversal algorithm is a big monolithic entity.
>
> That doesn't necessarily mean it can't be moved to the Visitor, but
> never mind. It may mean that you don't want to duplicate the code. If
> so, your original second objection to early termination - the speed
> cost of checking whether to terminate - remains. But as you said at the
> time, this may be insignificant anyway.

Actually, I meants that I don't see straightforward way to convert the 
algorithm to visitors, since complicated things in it might become really 
complicated when split over several parts.

> Your first original objection was that the interface to existing code
> would change, and that visit functions would need to return a bool
> even if they never wanted to terminate. Adding an instance variable to
> the visitor overcomes this problem.
>
>   void Node::accept( Visitor *pVisitor ) {
>       for (iterator i = begin(); i != end() && !pVisitor->m_break; ++i)
>           pVisitor->visit( this );
>   }
>
> As long as m_break is set to false in Visitor's constructor, it can be
> ignored by clients that don't need it. The functions still return void.
> The visitor interface is extended but not changed.

Yep, I figured that idea. And besides, it can be applied to bgl. Visitor can 
have member variable m_break which controls termination. We can memorize this 
idea in case someone will *really* want to try experimenting with early 
termination.

> > 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.
>
> That is what my example code did (or does). When m_break is set to true,
> the for-loop terminates and accept() exits. If all the other accept()
> functions are written the same way, they will all exit and the entire
> algorithm will halt.

Oh, I'm sorry. I failed to notice that m_break is never reset.

- Volodya