[boost] Re: graph_search

From: jsiek_at_[hidden]
Date: 2000-01-09 14:34:14

I'll have to think about this more :) Also, are there any references
I can look at that describe in more detail the algorithm you are
using?

Dave Abrahams writes:
 > you have found the discussion I was referring to.
 > 
 > > So of the requirements, the only one that I see missing is the
 > > ability to return, as in "if (visit(n)) return". Perhaps that
 > > would be easy to add into part of visitor(discover, u, bag).
 > 
 > Maybe I'm missing something, but it seems that if there are 2 incoming edges
 > to a Vertex, the one with higher cost can never be copied into the new
 > lattice in the obvious manner (by discover()) because the Vertex will have
 > been discovered already.
 > 
 > Your code:
 > 
 >   template <class IncidenceGraph, class Vertex, class Bag, class Visitor>
 >   void graph_search(IncidenceGraph& g, Vertex s, Bag& bag, Visitor visitor)
 >   {
 >     typedef typename boost::graph_traits<IncidenceGraph>::incidence_iterator
 >       IncIter;
 >     Vertex u;
 >     IncIter i, end;
 >     start(visitor, s);
 >     bag.push(s);
 >     while (! bag.empty()) {
 >       u = bag.top();
 >       if (is_undiscovered(visitor, u)) {
 >         discover(visitor, u, bag);
 >         for (tie(i,end) = out_edges(u,g); i != end; ++i)
 >           process(visitor, *i, g, bag);
 >       } else {
 >         finish(visitor, u);
 >         bag.pop();
 >       }
 >     }
 >   }
 > 
 > There is also the question you raise of how to terminate a search. Dietmar's
 > algorithm iterators do address this but I don't like some of the things I've
 > heard about them, some of which seem to imply a great cost in efficiency. I
 > do want to have a serious discussion about the possibility of using a
 > special exception type for that job. I have real reservations about the
 > approach stylistically, but I believe it may result in the most efficient
 > implementation of the algorithms nonetheless.
 > 
 > -Dave
 > 
 > ------------------------------------------------------------------------
 > Looking for educational tools for your kids?

 > Find everything you need at SmarterKids.com
 > http://click.egroups.com/1/645/1/_/9351/_/947446113/

 > 
 > -- Create a poll/survey for your group!
 > -- http://www.egroups.com/vote?listname=boost&m=1

 > 
 > 
 >