c++ - How to traverse an graph branch, from specific node with Boost.Graph? -

will grateful .
have tree structure , want print nodes in order of occurrence, respect of hierarchy .

for example wan traverse child of n1:

[n0, n1[n2, n3, n4[n5], n6] 

and i'm expect get

n1 n2 n3 n4 n5 

but i'm receive different, using snippet :

    typedef boost::adjacency_list<boost::lists, boost::vecs, boost::undirecteds> mygraph;     typedef boost::graph_traits<mygraph>::vertex_descriptor myvertex;          class myvisitor : public boost::default_dfs_visitor         {         public:           void discover_vertex(myvertex v, const mygraph& g) const           {             cerr << v << endl;             return;           }         };  int _tmain(int argc, _tchar* argv[]) {          mygraph g;          boost::add_edge(0, 1, g);         boost::add_edge(0, 2, g);         boost::add_edge(0, 3, g);         boost::add_edge(2, 4, g);          myvisitor vis;          //2 - n2 node          boost::depth_first_search(g,  boost::visitor(vis).root_vertex(2) );         return 0;  } 

output :

2 0 1 3 4 

but i'm expect (2 , childs)

2 4 

please help.

thank you.

your graph undirected, means backedge (0,2) taken.

try changing undirecteds directeds

to avoid reporting vertices discovered additional roots, adjust visitor detect when first root done:

live on coliru

#include <boost/graph/adjacency_list.hpp> #include <boost/graph/graphviz.hpp> #include <boost/graph/depth_first_search.hpp> #include <boost/graph/visitors.hpp> #include <iterator>  using graph = boost::adjacency_list<boost::vecs, boost::vecs, boost::directeds>; using vertexpair = std::pair<graph::vertex_descriptor, graph::vertex_descriptor>;  struct visitor : boost::default_dfs_visitor {     using v = graph::vertex_descriptor;      void discover_vertex(v v, const graph& /*g*/) {         if (!root) {             root = v;         }         if (!done) std::cerr << v << "\n";     }      void finish_vertex(v v, const graph& /*g*/) {         done |= (root == v);     }   private:     bool done = false;     boost::optional<v> root; };  int main() {     // [n0, n1[n2, n3, n4[n5], n6] :     // vertexpair const data[] { {1, 2}, {1, 3}, {1, 4}, {4, 5}, };     vertexpair const data[] { {0, 1}, {0, 2}, {0, 3}, {2, 4}, };     graph g(std::begin(data), std::end(data), 7);      boost::depth_first_search(g, boost::visitor(visitor()).root_vertex(2));     //boost::write_graphviz(std::cout, g); } 

prints

2 4 

update

if efficiency want avoid traversing remainder of tree, can use depht_first_visit can take terminatorfunc. here added same visitor:

live on coliru

// in visitor:      // terminatorfunc     bool operator()(v, graph const&) const { return done; }  // later:      visitor vis_termfuc; // combines visitor , terminator functions     std::vector<boost::default_color_type> colormap(num_vertices(g));     boost::depth_first_visit(g, 2, vis_termfuc, colormap.data(), vis_termfuc);