Doug Gregor wrote:
To get all of the descendants, you could just run a breadth-first or depth-first search starting at vertex "2", and then record which vertices were visited.
To get the ancestors, you could do exactly the same thing using the reverse graph; see http://www.boost.org/libs/graph/doc/ reverse_graph.html
This fails to compile: typedef boost::adjacency_list < boost::vecS , boost::vecS , boost::bidirectionalS , boost::property<boost::vertex_color_t, boost::default_color_type> , boost::property<boost::edge_weight_t, int>
dependency_graph_t; typedef boost::graph_traits<dependency_graph_t>::vertex_descriptor vertex; struct visitation_tracker : boost::bfs_visitor<> { std::vector<int> & visited; visitation_tracker(std::vector<int> & v) : visited(v) {} template < typename G, typename V > void discover_vertex(V u, G const& g) { visited.push_back(static_cast<int>(u)); } }; std::vector<int> retrieve_client_list(std::string const& cname) const { std::vector<component>::const_iterator fit = std::find_if(components.begin(), components.end(), boost::bind(&component::name, _1) == cname); if (fit == components.end()) throw std::runtime_error(cname + " not found in list of components."); int u = static_cast<int>(std::distance(components.begin(), fit)); std::vector<int> visited; visitation_tracker tracker(visited); boost::breadth_first_search(boost::make_reverse_graph(graph), boost::vertex(u, boost::make_reverse_graph(graph)), boost::visitor(tracker)); return visited; } Errors: 1>c:\projects\utilities\integrator\integrator\dependency_graph.cpp(119) : error C2784: 'subgraph<Graph>::vertex_descriptor boost::vertex(subgraph<Graph>::vertices_size_type,const boost::subgraph<Graph> &)' : could not deduce template argument for 'const boost::subgraph<Graph> &' from 'boost::reverse_graph<BidirectionalGraph,GraphRef>' 1> with 1> [ 1> BidirectionalGraph=dependency_graph_t, 1> GraphRef=const dependency_graph_t & 1> ] 1> c:\boost\include\boost-1_33_1\boost\graph\subgraph.hpp(865) : see declaration of 'boost::vertex' 1>c:\projects\utilities\integrator\integrator\dependency_graph.cpp(119) : error C2784: 'Config::vertex_descriptor boost::vertex(Config::vertices_size_type,const boost::vec_adj_list_impl<Graph,Config,Base> &)' : could not deduce template argument for 'const boost::vec_adj_list_impl<Graph,Config,Base> &' from 'boost::reverse_graph<BidirectionalGraph,GraphRef>' 1> with 1> [ 1> BidirectionalGraph=dependency_graph_t, 1> GraphRef=const dependency_graph_t & 1> ] 1> c:\boost\include\boost-1_33_1\boost\graph\detail\adjacency_list.hpp(2133) : see declaration of 'boost::vertex' 1>c:\projects\utilities\integrator\integrator\dependency_graph.cpp(119) : error C2784: 'Config::vertex_descriptor boost::vertex(Config::vertices_size_type,const boost::adj_list_impl<Derived,Config,Base> &)' : could not deduce template argument for 'const boost::adj_list_impl<Derived,Config,Base> &' from 'boost::reverse_graph<BidirectionalGraph,GraphRef>' 1> with 1> [ 1> BidirectionalGraph=dependency_graph_t, 1> GraphRef=const dependency_graph_t & 1> ] 1> c:\boost\include\boost-1_33_1\boost\graph\detail\adjacency_list.hpp(1848) : see declaration of 'boost::vertex' 1>c:\projects\utilities\integrator\integrator\dependency_graph.cpp(119) : error C2780: 'void boost::breadth_first_search(const VertexListGraph &,graph_traits<G>::vertex_descriptor,Buffer &,BFSVisitor,ColorMap)' : expects 5 arguments - 3 provided 1> c:\boost\include\boost-1_33_1\boost\graph\breadth_first_search.hpp(88) : see declaration of 'boost::breadth_first_search'