[boost] Re: graph_search

From: Dave Abrahams (abrahams_at_[hidden])
Date: 2000-01-09 14:23:40

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