Boost DFS how to save visited vertices?

Question

I'm looking at the solution here, which doesn't work for me (but read under the === line to actually see the current problem).

I tried:

boost::undirected_dfs(G, vertex(0,G), boost::visitor(vis));

but I get

error C2780: 'void boost::undirected_dfs(const Graph &,const boost::bgl_named_params<P,T,R> &)' : expects 2 arguments - 3 provided
error C2780: 'void boost::undirected_dfs(const Graph &,DFSVisitor,VertexColorMap,EdgeColorMap)' : expects 4 arguments - 3 provided

etc. I sort of get what the problem is (I need to pass it some named parameters, but I don't have any in my graph, I think. Also, I don't get what the deal with the color maps is, at all.

=============================================================================

My graph is defined:

typedef boost::adjacency_list<boost::listS, boost::vecS, boost::undirectedS, boost::no_property, EdgeInfoProperty > Graph;
typedef Graph::edge_descriptor Edge;
typedef Graph::vertex_descriptor Vertex;

All I want is to do DFS, at least for now.

So I changed it to boost::depth_first_search, and it seems to work.

I have (note the lack of const for void discover_vertex vs. the solution linked above):

class MyVisitor : public boost::default_dfs_visitor {
public:
    void discover_vertex(Vertex v, const Graph& g)  { //note the lack of const
        if(boost::in_degree(v,g)!=0){ //only print the vertices in the connected component (I already did MCC and removed edges so all the extra vertices are isolated)
            std::cerr << v << std::endl;
            vv.push_back(v);
        }
        return;
    }
    std::vector<Vertex> GetVector() const  { return vv; }
private: 
    std::vector<Vertex> vv;
};

If I leave const there I get error C2663: 'std::vector<_Ty>::push_back' : 2 overloads have no legal conversion for 'this' pointer with [ _Ty=size_t ].

Now, this works fine or at least it prints out the right visited vertices, in the right order:

MyVisitor vis;
boost::depth_first_search(G, boost::visitor(vis));

But when I do:

std::vector<Vertex> vctr = vis.GetVector();
std::cout<<vctr.size();

the size is zero, because my vv doesn't change...

So, how can I get the appropriate class behavior when the class is used as an argument to boost::visitor? (I'm not even sure this is the appropriate question). I need to be able to change EdgeInfoProperty based on which nodes were visited before (or rather based on which vertex is the parent of the current vertex in the DFS traversal, so this would probably just be a first step towards that).

score 3 · Accepted Answer · answered Aug 06 '14 at 17:33

The visitor is passed by value, so you need to share the vector it holds with the instance of MyVisitor copied into the function call.

Try this:

class MyVisitor : public boost::default_dfs_visitor {
public:
    MyVisitor(): vv(new std::vector<Vertex>()){}

    void discover_vertex(Vertex v, const Graph& g)  { //note the lack of const
        if(boost::in_degree(v,g)!=0){ //only print the vertices in the connected component (I already did MCC and removed edges so all the extra vertices are isolated)
            std::cerr << v << std::endl;
            vv->push_back(v);
        }
        return;
    }
    std::vector<Vertex>& GetVector() const  { return *vv; }
private: 
    boost::shared_ptr< std::vector<Vertex> > vv;
};

score 0 · Answer 2 · answered Sep 01 '23 at 17:55

You can also use a global variable or a static data member to store the traversal results.

Global variable

Live on Coliru

This approach is very versatile but also feels a bit quick-and-dirty. Note that you need to reset g_vertices before starting a new traversal. There are two benefits of using a global variable and a Visitor template with a void operator()(...) method.

You can use EventVisitor to toggle between pre-order and post-order traversal, and even extend it to other events.
I name the visitor MyVisitor instead of a more restrictive MyDFSVisitor because you can also apply it to other Boost Graph Library algorithms such as breadth_first_search().

// Pre-order and post-order DFS traversal on an undirected graph with a global
// variable
#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;

namespace {
// Global variable to store traversal results
std::vector<MyVertex> g_vertices;
} // namespace

template <typename Event> struct MyVisitor : public boost::null_visitor {
  // Capture event type to allow both pre-order and post-order traversal
  using event_filter = Event;

  template <typename Vertex, typename Graph>
  void operator()(Vertex v, const Graph &g) {
    g_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);

  {
    // Pre-order [0, 1, 2, 3]
    std::cout << "pre-order traversal:\n";
    auto vis = boost::make_dfs_visitor(MyVisitor<boost::on_discover_vertex>());
    boost::depth_first_search(g, vis, color_map, root);
    for (auto v : g_vertices) {
      std::cout << v << std::endl;
    }
    g_vertices.clear();
  }
  {
    // Post-order [2, 3, 1, 0]
    std::cout << "post-order traversal:\n";
    auto vis = boost::make_dfs_visitor(MyVisitor<boost::on_finish_vertex>());
    boost::depth_first_search(g, vis, color_map, root);
    for (auto v : g_vertices) {
      std::cout << v << std::endl;
    }
    g_vertices.clear();
  }
}

Static data member

Here, I write MyDFSVisitor as a template struct to make it more transferrable to other use cases.

Live on Coliru

// Pre-order and post-order DFS traversal on an undirected graph with a static
// data member
#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;

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

  // pre-order traversal
  template <typename Graph> void discover_vertex(Vertex v, const Graph &g) {
    m_preorder_vertices.push_back(v);
  }

  // post-order traversal
  template <typename Graph> void finish_vertex(Vertex v, const Graph &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<MyVertex> 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;
  }
}

Boost DFS how to save visited vertices?

2 Answers2

Global variable

Static data member

Linked