How do I create a queue of traversed vertex using boost graph library breadth-first search?

Question

I would like to use boost graph library breadth first search to return a queue of vertex visited when starting on node 1. I read the documentation but still am having trouble understanding how to implement this.

The result below would return a queue in the order: 1,2,3,4 or 1,3,2,4

typedef boost::property<boost::edge_weight_t, unsigned int> EdgeWeightProperty;
typedef boost::adjacency_list<boost::setS, boost::vecS, boost::undirectedS, 
                              boost::no_property, EdgeWeightProperty> Graph;

//create graph and add edge
Graph g;
boost::add_edge(1,2,6,g);
boost::add_edge(2,3,6,g);
boost::add_edge(3,1,6,g);
boost::add_edge(3,4,6,g);

//Perform breadth first using boost and return result in a queue.

There are examples abound for using Boost's built-in BFS visitor: https://stackoverflow.com/questions/14470566/how-to-traverse-graph-in-boost-use-bfs . Use the visitor, and when visiting each node, just enqueue the node ID to the back of the queue. — parktomatomi, Dec 17 '19 at 01:51

William Miller · Accepted Answer · 2023-03-17T22:43:18.443

The boost graph library documentation defines a BFS Visitor concept which states

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

based on this and the bfs.cpp example the preferred method to accomplish what you are asking is to subclass either boost::visitor or boost::default_bfs_visitor and override one or several of

initialize_vertex
discover_vertex
examine_vertex
examine_edge
tree_edge
non_tree_edge
gray_target
black_target
finish_vertex

For your use case I would say it is most appropriate to subclass boost::default_bfs_visitor and override discover_vertex:

discover_vertex(s, g)

Invoked when a vertex is encountered for the first time. s is An object of type boost::graph_traits<Graph>::vertex_descriptor and g is an object of type Graph.

Here is an example of exactly how to do that, with appropriate handling of a std::queue object to record the vertices.

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

typedef boost::property<boost::edge_weight_t, unsigned int> EdgeWeightProperty;
typedef boost::adjacency_list<boost::setS, boost::vecS, boost::undirectedS, 
                              boost::no_property, EdgeWeightProperty> Graph;

class BFSVisitor : public boost::default_bfs_visitor {
public:    
    BFSVisitor(std::queue<Graph::vertex_descriptor>& _v) : visited(_v){}
    void discover_vertex(Graph::vertex_descriptor s, const Graph &g) {
         visited.push(s); 
    }
    std::queue<Graph::vertex_descriptor>& visited;
};

int main() {
    Graph g;
    boost::add_edge(0,1,6,g);
    boost::add_edge(1,2,6,g);
    boost::add_edge(2,3,6,g);
    boost::add_edge(3,1,6,g);
    boost::add_edge(3,4,6,g);

    Graph::vertex_descriptor s = *(boost::vertices(g).first);
    std::queue<Graph::vertex_descriptor> q;
    BFSVisitor vis(q);
    boost::breadth_first_search(g, s, boost::visitor(vis));
    while (!vis.visited.empty()) {
        std::cout << vis.visited.front() << std::endl;
        vis.visited.pop();
    }
}

which will output

Note — Boost expects the graph to start at vertex 0, not 1 - hence the line

boost::add_edge(0,1,6,g);

if you start at vertex 1 there will be no output.

How do I create a queue of traversed vertex using boost graph library breadth-first search?

1 Answers1