This documentation is being rewritten. If something looks off, please cross-check with the Boost 1.91.0 Boost.Graph docs and open an issue.

BFS Visitor Concept

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

Refinement of

Copy Constructible (copying a visitor should be a lightweight operation).

Notation

V A type that is a model of BFS Visitor.

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 whose 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 whose 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 the out-edges of the adjacent vertices have been examined).

Models

Edit this Page