Performing depth-first algorithm from a specific vertex

I am trying to find a way to perform the depth-first algorithm from a specific vertex by using the boost graph library.

The depth-f开发者_运维知识库irst algorithm provided by Boost library evaluates the graph beginning from the start vertex to the last vertex. But what if the graph has to be searched from a specific vertex?

Any suggestions?

Have a look at BGL's documentation.

There is an overload where you can provide the start vertex.

template <class Graph, class DFSVisitor, class ColorMap>
void depth_first_search(const Graph& g, DFSVisitor vis, ColorMap color, 
                        typename graph_traits<Graph>::vertex_descriptor start)

BGL Provides two mechanisms for setting the starting vertex of depth_first_search. You can either use the overload operator which requires supplying a ColorMap, or you can directly set the property of your visitor:

boost::depth_first_search(myGraph, boost::visitor(myVisitor).root_vertex(myVertex));

boost::depth_first_search(myGraph, boost::visitor(myVisitor).root_vertex(myVertex));

This is simply an example of using the named parameter version of the call to depth_first_search(). See Named Parameters. I found that even if you do specify a vertex other than the root of the graph to start from, the algorithm will still visit all of the vertices in the graph. It will just start from the one you specify.

To visit only those vertices reachable from a specified vertex you need to use the depth_first_visit algorithm. This requires a color map to be specified. Here's a color map that worked for me.

    using Graph = boost::adjacency_list;
    using IndexMap = boost::property_map::const_type;
    IndexMap indexMap = boost::get(boost::vertex_index, m_graph);

    using ColorMap = boost::iterator_property_map;
    std::vector color_vec(num_vertices(m_graph));
    ColorMap colorMap(&color_vec.front(), indexMap);