[BGL] How to prune a BFS or exit a BFS
I have a custom BFS visitor used to traverse a graph. Is there a built-in way to - prune off a vertex's descendants from the search - exit a BFS These ( pruning and terminating ) are separate situations. I believe the following will work; however, I do not know how to access the relevant data structures. - To prune off a vertex's descendents from the search In the custom BFS visitor's discover_vertex event, set the color of all its adjacent descendants to "black". - To exit a BFS In the custom BFS visitor's discover_vertex event, once the required vertex is found, empty the queue of vertices. How can I access a vertex's color and a BFS's queue? Or is there a better way?
After doing some more work, I believe the following information can be added. If DFS/BFS is invoked without a color map, an internal one is created. This can be seen in the code dfs_dispatchdetail::error_property_not_found, for example. This means that DFS/BFS has access to a color map, whether user-provided or intenally-provided. However, the DFS/BFS visitor can only access a color map if passed from the user. It has no access to the internal color map. The same reasoning goes for the queue of vertices. Feedback and comments are welcome, esp if there is a different or better way.
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_dispatchdetail::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@osl.iu.edu C++ Booster (http://www.boost.org) office phone: (812) 855-3608 ----------------------------------------------------------------------
participants (2)
-
Jeremy Siek -
kweeheong