Re: [boost] Re: halting graph algorithms

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

In-Reply-To: <bjmcgf$j1n$1_at_[hidden]>
On Wed, 10 Sep 2003 09:23:30 +0400 Vladimir Prus (ghost_at_[hidden]) wrote:
> > Right now my visitor throws an exception which the call catches
> > and ignores, but this doesn't seem very clean. Is there a better
> > way to do this?
> 
> No, it's the only possible method (well, there's also setjump/longjump 
> ;-), but that's no-no in C++ code).
> 
> One other opinion is to make some visitor functions return bool. I 
> believe Jeremy is not happy about this idea and I also too have
> reservations about it.
> 
> The first problem is that its interface change. Even if we can do it,
> it means that some visitor function should return bool, even if it has 
> never need to terminate search at all.
> 
> 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.

So for example we might get routines like:

    class Visitor {
    public:
        Visitor() : m_break(false) {
        }
        
        virtual void visit_node( Node *pNode ) {
            traverse_node_with_speed( pNode );
        }
        
    protected:
        virtual void traverse_node_with_speed( Node *pNode ) {
            for (Node::iterator i = pNode->begin();
                    i != pNode->end(); ++i)
                i->accept( this );
        }
        
        
        virtual void traverse_node_with_break( Node *pNode ) {
            for (Node::iterator i = pNode->begin();
                    i != pNode->end() && !m_break; ++i)
                i->accept( this );
        }
        // ...
        
        void break_traverse() {
            m_break = true;
        }

    private:
        bool m_break;
    };

Here client subclasses can over-ride visit_node() to call whichever 
version of traverse_node() they want. If they use 
traverse_node_with_break(), they can call break_traverse() when they want 
to stop.

Obviously you can juggle the protections and virtual functions to suit you 
needs. For example, you can make Node::begin() etc private, make Visitor a 
friend of Node and make the traverse_node() functions non-virtual, to keep 
things encapsulated. Or you can make Node::begin() a public interface and 
allow clients to write their own traverse_node() functions. You may want 
to move the break infrastructure into a separate subclass of Visitor. Once 
the traversal code is in the visitor, you have a lot of flexibility.

-- Dave Harris, Nottingham, UK