Boost logo

Boost :

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


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk