c++ boost::Graph::breadth_first_search()

c++ boost::Graph::breadth_first_search()

breath_first_search() is a inbuilt method in BGL interface for graph traversal. In this method the traversal starts from the second parameter passed in the function, and it will visit all the nodes distance-wise i.e. firstly all the nodes with distance equal to one will be visited, then two and so on, like a wave.

It don't return anything, it just visit all the nodes of the graph. what to be done with the data in that visited node is decided by the visitor passed to the third parameter of the breath_first_search() function. In the below example we use the visitor to calculate the distance i.e. the line crossed between the nodes.

The examplar code is given below :

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/breadth_first_search.hpp>
#include <boost/graph/named_function_params.hpp>
#include <boost/graph/visitors.hpp>
#include <boost/array.hpp>
#include <array>
#include <utility>
#include <iterator>
#include <algorithm>
#include <iostream>

using namespace std;
using namespace boost;

int main()
  enum { one, two, three, four };

  std::array<std::pair<int, int>, 4> edges{{
    make_pair(one, two),
    make_pair(two, three),
    make_pair(three, four),
    make_pair(four, one)

  typedef adjacency_list<setS, vecS, undirectedS> graph;
  graph g{edges.begin(), edges.end(), 4};

  boost::array<int, 4> distances{{0}};

  breadth_first_search(g, one, visitor( make_bfs_visitor( record_distances(distances.begin(), on_tree_edge{}))));

    for (auto e=distances.begin(); e != distances.end(); ++e)
        cout<< *e<<"\n";

 * The tag boost::on_tree_edge in the above Example specifies that a distance should be               recorded when a new node has been found.