Re: [Boost-Users] Re: [BGL] How to prune a BFS or exit a BFS

From: Jeremy Siek (jsiek_at_[hidden])
Date: 2002-11-01 10:46:02

Hi,

On Fri, 1 Nov 2002, kweeheong wrote:
tan.k.> After doing some more work, I believe the following information
tan.k.> can be added.
tan.k.>
tan.k.> If DFS/BFS is invoked without a color map, an internal one is
tan.k.> created. This can be seen in the code
tan.k.> dfs_dispatch<detail::error_property_not_found>, for example.

Yes. It also says this (rather tersely) in the documentation for BFS/DFS.

UTIL/OUT: color_map(ColorMap color)
...
Default: an iterator_property_map created from a std::vector of
default_color_type of size num_vertices(g) and using the i_map
for the index map.

tan.k.> This means that DFS/BFS has access to a color map, whether
tan.k.> user-provided or intenally-provided.
tan.k.>
tan.k.> However, the DFS/BFS visitor can only access a color map if passed
tan.k.> from the user. It has no access to the internal color map.

That is true.

tan.k.> The same reasoning goes for the queue of vertices.
tan.k.>
tan.k.>
tan.k.> Feedback and comments are welcome, esp if there is a different or
tan.k.> better way.

Here's how I would do it:

  1. For pruning, use an external color map that gets passed to the
   visitor and the algorithm.
  2. For early exit, throw an exception.

Cheers,
Jeremy

----------------------------------------------------------------------
 Jeremy Siek                          http://php.indiana.edu/~jsiek/
 Ph.D. Student, Indiana Univ. B'ton   email: jsiek_at_[hidden]
 C++ Booster (http://www.boost.org)   office phone: [phone]
----------------------------------------------------------------------