Re: [Boost-users] limiting searches in BGL

From: Douglas Paul Gregor (gregod_at_[hidden])
Date: 2004-06-16 08:46:40

On Tue, 15 Jun 2004, Jason Crosswhite wrote:

> Douglas Paul Gregor wrote:
>
> > I suspect you want a filtered_graph. Just give it predicates that filter
> >
> >out any points outside the hull. The filtered_graph docs are here:
> >
> >  http://www.boost.org/libs/graph/doc/filtered_graph.html
> >
> >	Doug
> >
> I am not certain, but when I looked at the filtered graph docs, it
> seemed that a filter was run on every point in the graph.  If that is
> true, it is exactly what I want to avoid.  Hopefully I'm wrong.

Then you probably don't want to use filtered_graph, at least not directly
:) Essentially, filtered_graph will apply the given predicates to lists of
vertices and edges in the graph in a lazy manner. So if you have

  filtered_graph<...> g(...);
  for (tie(v, v_end) = vertices(g); v != v_end; ++v) {
    // ...
  }

then the predicate will be called once for each vertex in the underlying
list of vertices.

If you just need to do a depth-first search, then just marking black the
vertices that you don't want to touch works fine. If you have other graph
operations that you need to do, you might want to use filtered_graph to
make those vertices invisible. You could store the in hull/out of hull
flag in a vertex property and access that from the filtered_graph
predicates, if you wanted to compute the information only once but use
filtered_graph.

        Doug