CODEWITHSUNDEEP
c++boostdepth-first-searchboost-graph
oracle3001
oracle3001

Reputation: 1100

C++ Boost graph library: Building a vector of vertices visited in an undirected graph search?

From what I can gather of how to use BGL in order to invoke a DFS of a graph from a known root node I need to do something along the lines of

class MyVisitor : public boost::default_dfs_visitor
{
  public:
  void discover_vertex(MyVertex v, const MyGraph& g) const
 {
    cerr << v << endl;
    return;
 }

};


 void bfsMethod(Graph g, int rootNodeId)
 {

   boost::undirected_dfs(g, vertex(rootNodeId,g), boost::visitor(vis)); 

 }

Now I am not sure how I alter this so that std::vector of vertexId's (or pointers) is built as the DFS visits all vertices in the graph in a similar way to how the minimum spanning tree algorithm can be used e.g.

std::vector < JPEdge > spanning_tree;
kruskal_minimum_spanning_tree(g, std::back_inserter(spanning_tree));

Upvotes: 2

Views: 1203

Answers (2)

wu1meng2
wu1meng2

Reputation: 537

Because both depth_first_search and undirected_dfs pass DFSVisitor vis by value, we cannot use std::vector<> to store traversed vertices, otherwise its size will always be 0 after exiting depth_first_search or undirected_dfs. Instead, we can use a std::shared_ptr<std::vector<>> or static std::vector<> to store the vertices. In my opinion, using a static data member is simpler and more expressive.

Here we can get pre-order traversal with discover_vertex() and post-order traversal with finish_vertex. See DFS Visitor for more details.

Live on Coliru

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/depth_first_search.hpp>
#include <iostream>

using MyGraph = boost::adjacency_list<
    boost::listS, boost::vecS, boost::undirectedS,
    boost::property<boost::vertex_color_t, boost::default_color_type>>;

using MyVertex = boost::graph_traits<MyGraph>::vertex_descriptor;

struct MyDFSVisitor : public boost::default_dfs_visitor {
  inline static std::vector<MyVertex> m_preorder_vertices;
  inline static std::vector<MyVertex> m_postorder_vertices;

  void discover_vertex(MyVertex v, const MyGraph &g) {
    m_preorder_vertices.push_back(v);
  }

  void finish_vertex(MyVertex v, const MyGraph &g) {
    m_postorder_vertices.push_back(v);
  }
};

int main() {
  MyGraph g{};
  boost::add_edge(0, 1, g);
  boost::add_edge(0, 2, g);
  boost::add_edge(1, 2, g);
  boost::add_edge(1, 3, g);

  auto root = boost::vertex(0, g);
  auto color_map = boost::get(boost::vertex_color, g);

  MyDFSVisitor vis;
  boost::depth_first_search(g, vis, color_map, root);
  std::cout << "pre-order traversal : \n"; // 0 1 2 3
  for (auto v : vis.m_preorder_vertices) {
    std::cout << v << std::endl;
  }
  std::cout << "post-order traversal : \n"; // 2 3 1 0
  for (auto v : vis.m_postorder_vertices) {
    std::cout << v << std::endl;
  }
}

Note that inline static is a C++17 feature.

Upvotes: 0

Armen Tsirunyan
Armen Tsirunyan

Reputation: 132994

The vector must be a member of your visitor. In the discover_vertex function, just push the discovered element into the vector.

class MyVisitor : public boost::default_dfs_visitor
{
  public:
  void discover_vertex(MyVertex v, const MyGraph& g) const
 {
    cerr << v << endl;
    vv.push_back(v);
    return;
 }

  vector<MyVertex> GetVector() const {return vv; }

 private: 
 vector<MyVertex> vv;

};

void bfsMethod(Graph g, int rootNodeId)
{
  MyVisitor vis;
  boost::undirected_dfs(g, vertex(rootNodeId,g), vis); 
  vector<MyVertex> vctr = vis.GetVector();

 }

Upvotes: 1

Related Questions