breadth_first_visit

Performs a breadth-first traversal without initializing color markers.

Complexity: O(E)
Defined in: <boost/graph/breadth_first_search.hpp>

Example

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/breadth_first_search.hpp>
#include <boost/pending/queue.hpp>
#include <iostream>
#include <vector>

struct VertexProps { int id; };

using Graph = boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, VertexProps>;
using Vertex = boost::graph_traits<Graph>::vertex_descriptor;

struct PrintVisitor : boost::default_bfs_visitor {
    void discover_vertex(Vertex v, const Graph& g) const {
        std::cout << g[v].id << " ";
    }
};

int main() {
    Graph g{5};
    for (int i = 0; i < 5; ++i) { g[i].id = i; }
    boost::add_edge(0, 1, g);
    boost::add_edge(0, 2, g);
    boost::add_edge(1, 3, g);
    boost::add_edge(2, 4, g);

    // breadth_first_visit skips initialization (no white-painting of all vertices).
    // Caller must provide a color map and queue.
    std::vector<boost::default_color_type> colors(num_vertices(g), boost::white_color);
    auto color_map = boost::make_iterator_property_map(colors.begin(), get(boost::vertex_index, g));
    boost::queue<Vertex> q;

    std::cout << "BFS visit order: ";
    boost::breadth_first_visit(g, vertex(0, g), q, PrintVisitor{}, color_map);
    std::cout << std::endl;
}
BFS visit order: 0 1 2 3 4

(1) Positional version

template <class IncidenceGraph, class Buffer,
          class BFSVisitor, class ColorMap>
void breadth_first_visit(const IncidenceGraph& g,
    typename graph_traits<IncidenceGraph>::vertex_descriptor s,
    Buffer& Q, BFSVisitor vis, ColorMap color);
Direction Parameter Description

IN

const IncidenceGraph& g

A directed or undirected graph. The graph type must be a model of Incidence Graph.

IN

vertex_descriptor s

The source vertex where the search is started.

UTIL

Buffer& Q

The queue used to determine the order in which vertices will be discovered. If a FIFO queue is used, then the traversal will be according to the usual BFS ordering. Other types of queues can be used, but the traversal order will be different. For example Dijkstra’s algorithm can be implemented using a priority queue. The type Buffer must be a model of Buffer.

IN

BFSVisitor vis

A visitor object that is invoked inside the algorithm at the event-points specified by the BFS Visitor concept. The visitor object is passed by value [1].

UTIL/OUT

ColorMap color

This is used by the algorithm to keep track of its progress through the graph. The type ColorMap must be a model of Read/Write Property Map and its key type must be the graph’s vertex descriptor type and the value type of the color map must model ColorValue.

(2) Named parameter version

template <class IncidenceGraph, class P, class T, class R>
void breadth_first_visit(IncidenceGraph& G,
    typename graph_traits<IncidenceGraph>::vertex_descriptor s,
    const bgl_named_params<P, T, R>& params);
Direction Parameter Description

IN

IncidenceGraph& g

A directed or undirected graph. The graph type must be a model of Incidence Graph.

IN

vertex_descriptor s

The source vertex where the search is started.

IN

visitor(BFSVisitor vis)

A visitor object that is invoked inside the algorithm at the event-points specified by the BFS Visitor concept. The visitor object is passed by value [1].
Default: bfs_visitor<null_visitor>

UTIL/OUT

color_map(ColorMap color)

This is used by the algorithm to keep track of its progress through the graph. The type ColorMap must be a model of Read/Write Property Map and its key type must be the graph’s vertex descriptor type and the value type of the color map must model ColorValue.
Default: get(vertex_color, g)

UTIL

buffer(Buffer& Q)

The queue used to determine the order in which vertices will be discovered. If a FIFO queue is used, then the traversal will be according to the usual BFS ordering. Other types of queues can be used, but the traversal order will be different. For example Dijkstra’s algorithm can be implemented using a priority queue. The type Buffer must be a model of Buffer.
Default: boost::queue

Description

This function is basically the same as breadth_first_search() except that the color markers are not initialized in the algorithm. The user is responsible for making sure the color for every vertex is white before calling the algorithm. With this difference, the graph type is only required to be an Incidence Graph instead of a Vertex List Graph. Also, this difference allows for more flexibility in the color property map. For example, one could use a map that only implements a partial function on the vertices, which could be more space efficient when the search only reaches a small portion of the graph.

Visitor Event Points

  • vis.examine_vertex(u, g) is invoked on each vertex as it is removed from the queue.

  • vis.examine_edge(e, g) is invoked on every out-edge of each vertex immediately after the vertex is removed from the queue.

  • vis.tree_edge(e, g) is invoked (in addition to examine_edge()) if the edge is a tree edge. The target vertex of edge e is discovered at this time.

  • vis.discover_vertex(u, g) is invoked the first time the algorithm encounters vertex u. All vertices closer to the source vertex have been discovered, and vertices further from the source have not yet been discovered.

  • vis.non_tree_edge(e, g) is invoked (in addition to examine_edge()) if the edge is not a tree edge.

  • vis.gray_target(e, g) is invoked (in addition to non_tree_edge()) if the target vertex is colored gray at the time of examination. The color gray indicates that the vertex is currently in the queue.

  • vis.black_target(e, g) is invoked (in addition to non_tree_edge()) if the target vertex is colored black at the time of examination. The color black indicates that the vertex is no longer in the queue.

  • vis.finish_vertex(u, g) is invoked after all of the out edges of u have been examined and all of the adjacent vertices have been discovered.

Notes

[1] Since the visitor parameter is passed by value, if your visitor contains state then any changes to the state during the algorithm will be made to a copy of the visitor object, not the visitor object passed in. Therefore you may want the visitor to hold this state by pointer or reference.

Edit this Page