[Boost-users] ok, need help was (re: BGL - retrieving a subgraph)

From: Noah Roberts (roberts.noah_at_[hidden])
Date: 2007-05-22 14:32:24

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'