Re: [boost] Re: halting graph algorithms

From: Dave Harris (brangdon_at_[hidden])
Date: 2003-09-14 04:56:56

In-Reply-To: <200309121019.51819.ghost_at_[hidden]>
On Fri, 12 Sep 2003 10:19:51 +0400 Vladimir Prus (ghost_at_[hidden]) wrote:
> > 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.
> 
> [...] 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.

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.

> 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.

-- Dave Harris, Nottingham, UK