# BFSVisitor Concept

This concept defines the visitor interface for `breadth_first_search()`. Users can define a class with the BFSVisitor interface and pass and object of the class to `breadth_first_search()`, thereby augmenting the actions taken during the graph search.

### Refinement of

none

### Notation

`V` | A type that is a model of BFSVisitor.
`vis` | An object of type `V`.
`G` | A type that is a model of Graph.
`g` | An object of type `G`.
`e` | An object of type `boost::graph_traits<G>::edge_descriptor`.
`s,u` | An object of type `boost::graph_traits<G>::vertex_descriptor`.

### Associated Types

none

### Valid Expressions

Name | Expression | Return Type | Description
--- | --- | --- | ---
Initialize Vertex | `vis.initialize_vertex(s, g)` | `void` | This is invoked on every vertex of the graph before the start of the graph search.
Discover Vertex | `vis.discover_vertex(u, g)` | `void` | This is invoked when a vertex is encountered for the first time.
Examine Vertex | `vis.examine_vertex(u, g)` | `void` | This is invoked on a vertex as it is popped from the queue. This happens immediately before `examine_edge()` is invoked on each of the out-edges of vertex `u`.
Examine Edge | `vis.examine_edge(e, g)` | `void` | This is invoked on every out-edge of each vertex after it is discovered.
Tree Edge | `vis.tree_edge(e, g)` | `void` | This is invoked on each edge as it becomes a member of the edges that form the search tree.
Non-Tree Edge | `vis.non_tree_edge(e, g)` | `void` | This is invoked on back or cross edges for directed graphs and cross edges for undirected graphs.
Gray Target | `vis.gray_target(e, g)` | `void` | This is invoked on the subset of non-tree edges who's target vertex is colored gray at the time of examination. The color gray indicates that the vertex is currently in the queue.
Black Target | `vis.black_target(e, g)` | `void` | This is invoked on the subset of non-tree edges who's target vertex is colored black at the time of examination. The color black indicates that the vertex has been removed from the queue.
Finish Vertex | `vis.finish_vertex(u, g)` | `void` | This invoked on a vertex after all of its out edges have been added to the search tree and all of the adjacent vertices have been discovered (but before their out-edges have been examined).

### Models

- `bfs_visitor`

### See also

Visitor concepts

Copyright © 2000 | Jeremy Siek, Univ.of Notre Dame (jsiek@lsc.nd.edu) Lie-Quan Lee, Univ.of Notre Dame (llee1@lsc.nd.edu) Andrew Lumsdaine, Univ.of Notre Dame (lums@lsc.nd.edu)