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::property
dependency_graph_t;
typedef boost::graph_traits::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'
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 &)' : could not deduce
template argument for 'const boost::vec_adj_list_impl
&' from 'boost::reverse_graph'
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 &)' : could not deduce
template argument for 'const boost::adj_list_impl
&' from 'boost::reverse_graph'
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'
