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.

More Articles of MAYANK KUMAR:

Name Views Likes
c++ boost::Graph::Property_Maps 417 0
c++ boost::Graph::Graph_construction 383 1
c++ boost::Graph::accessing_graph 307 0
c++ boost::Graph::BGL_interface 400 0
C++ program to delete an element into AVL tree 1335 1
c++ boost::Graph::breadth_first_search() 807 0
c++ boost::Graph::weighted_graph 377 10
c++ boost::Graph::interior_properties 293 0
c++ boost::Graph::weighted_graph 322 0
c++ boost::Graph::remove_edge 1362 0
c++ boost::transpose_graph 282 1

Comments