[BGL] dfs on graphs with bundled-properties
I am trying to use an adjacency list with bundled properties and running into lots of problems. I'm wondering if bundled properties is mature enough, or if I should resort to the older style using property maps. Here's a description of one problem I've run into: So I define my graph class with bundled properties as so: struct MyV { int numStars; }; struct MyE { int numStars; }; typedef adjacency_list<setS, setS, bidirectionalS, MyV, MyE> MyGraph; I would like to perform dfs on this graph. So I have a very simple visitor defined: struct star_visitor : public boost::default_dfs_visitor { template <class Vertex, class Graph> void start_vertex(Vertex v, const Graph &) { std::cout << 'start'; } template <class Vertex, class Graph> void discover_vertex(Vertex v, const Graph &) { std::cout << "*"; } template <class Vertex, class Graph> void finish_vertex(Vertex v, const Graph &) { std::cout << 'finish'; } }; Then in my main function, I make a MyGraph object and put in vertices and edges, and assign property values. That works fine. MyGraph g; MyGraph::vertex_descriptor v1 = addVertex(g); MyGraph::vertex_descriptor v2 = addVertex(g); MyGraph::edge_descriptor e2 = addEdge(v1, v2, g); g[*v1].numStars = 100; g[*v2].numStars = 2; g[*e1].numStars = 7; Then I perform dfs on my graph depth_first_search(g, visitor(star_vis)); And I get the following errors. I don't get these errors and my program compiles fine if I do a dfs with my star_visitor on a graph with no properties. Main.cpp c:\boost_1_33_1\boost\property_map.hpp(349) : error C2679: binary '+' : no operator found which takes a right-hand operand of type 'const boost::detail::error_property_not_found' (or there is no acceptable conversion) c:\program files\microsoft visual studio 8\vc\include\vector(366): could be 'std::_Vector_iterator<_Ty,_Alloc> std::_Vector_iterator<_Ty,_Alloc>::operator +(__w64 int) const' with [ _Ty=boost::default_color_type, _Alloc=std::allocator ] while trying to match the argument list '(const std::_Vector_iterator<_Ty,_Alloc>, const boost::detail::error_property_not_found)' with [ _Ty=boost::default_color_type, _Alloc=std::allocator ] c:\boost_1_33_1\boost\property_map.hpp(349) : while compiling class template member function 'boost::default_color_type boost::iterator_property_map::operator [](void *) const' with [ RandomAccessIterator=std::_Vector_iterator>, IndexMap=boost::adj_list_vertex_property_map, T=boost::default_color_type, R=boost::default_color_type & ] c:\documents and settings\istreinu\desktop\naomi\boost_1_33_1\boost\graph\depth_first_search.hpp(250) : see reference to class template instantiation 'boost::iterator_property_map' being compiled with [ RandomAccessIterator=std::_Vector_iterator>, IndexMap=boost::adj_list_vertex_property_map, T=boost::default_color_type, R=boost::default_color_type & ] c:\documents and settings\istreinu\desktop\naomi\boost_1_33_1\boost\graph\depth_first_search.hpp(332) : see reference to function template instantiation 'void boost::detail::dfs_dispatch::apply(const VertexListGraph &,DFSVisitor,Vertex,const boost::bgl_named_params &,boost::detail::error_property_not_found)' being compiled with [ VertexListGraph=MyGraph, DFSVisitor=Star_visitor, Vertex=void *, T=Star_visitor, Tag=boost::graph_visitor_t, Base=boost::no_property ] c:\documents and settings\istreinu\my documents\visual studio 2005\projects\refactorfirst\refactorfirst\main.cpp(228) : see reference to function template instantiation 'void boost::depth_first_search(const VertexListGraph &,const boost::bgl_named_params &)' being compiled with [ VertexListGraph=MyGraph, T=Star_visitor, Tag=boost::graph_visitor_t, Base=boost::no_property ]
On Wed, 2007-03-21 at 19:15 -0400, Naomi Fox wrote:
So I define my graph class with bundled properties as so:
struct MyV { int numStars; };
struct MyE { int numStars; };
typedef adjacency_list<setS, setS, bidirectionalS, MyV, MyE> MyGraph;
Then in my main function, I make a MyGraph object and put in vertices and edges, and assign property values. That works fine. [snip] Then I perform dfs on my graph
depth_first_search(g, visitor(star_vis));
The problem in this case isn't the bundled properties, it's that depth_first_search needs either a color map or an index map, neither of which is available to it. I really wish we could make those error messages make some sense, though :( So, there are a couple of fixes. The goal is to associate each vertex with an index, which is used to efficiently store extra data needed inside the depth_first_search algorithm. There are two ways to do it. The first involves putting the index into MyV, and then explicitly passing an index map to depth_first_search: struct MyV { int numStars; int index; }; // after you build the graph... int idx = 0; BGL_FORALL_VERTICES(v, g, Graph) g[v].index = idx++; // calling DFS depth_first_search(g, visitor(star_vis). vertex_index_map(get(&MyV::index, g))); Alternatively, only could use the more traditional properties approach for the vertex index (MyV still works like it always did!), like this: struct MyV { int numStars; }; // as you originally had written // Tweak the graph type to stick a vertex_index in each vertex typedef adjacency_list<setS, setS, bidirectionalS, property<vertex_index, int, MyV>, MyE> MyGraph; // after you build the graph... int idx = 0; BGL_FORALL_VERTICES(v, g, Graph) put(vertex_index, g, v, idx++); // Calling DFS, as you had before: depth_first_search(g, visitor(star_vis)); Despite the fact that I love bundled properties for everything else, I like the second one better because the BGL knows how to automatically look up the vertex_index property. Cheers, Doug
participants (2)
-
Douglas Gregor
-
Naomi Fox