[Graph] Switching from depth_first_search to depth_first_visit
Hello there! I just stumbled over a little bug that is simply due to the wrong visiting pattern used. From what I understand it should simply print a graph with children being indented. The visitor defined for the task itself is just fine. Problem is that currently a depth first *search* is used, which prints each vertex only once. So from my understanding the only thing I need to do is to replace that search with a visit. Sadly replacing the call to depth_first_visit with a call to depth_first_visit is not as easy as I thought ... For the record: The search call itself looks like this: boost::depth_first_search(mGraph, boost::visitor(printer).root_vertex(start)); Looking at the documentation [0] it seems that there is no version with named parameters for the depth first visit. So I need to pass the graph itself, the starting vertex, the visitor and a color map. And its the color map that troubles me ... I have tried around a little to construct such a thing, but so far without success. My try can be found at [1]. This results in a massive compilation error [2]. I am not really experienced with the extent templates are used in the BGL and have no idea what the compiler tries to tell me. Could anyone give me a hint what I am doing wrong? If more sourcecode is required thats not a problem at all. Simply tell me if anything is missing. Access to the source is also not a problem, compilation is quite easy using cmake. Thanks in advance Marcus Riemer [0] http://www.boost.org/doc/libs/1_44_0/libs/graph/doc/depth_first_visit.html [1] http://pastebin.com/ALvnTdj9 [2] http://pastebin.com/bh6d4NpH
On Wed, 16 Mar 2011, Marcus Riemer wrote:
Hello there!
I just stumbled over a little bug that is simply due to the wrong visiting pattern used. From what I understand it should simply print a graph with children being indented.
The visitor defined for the task itself is just fine. Problem is that currently a depth first *search* is used, which prints each vertex only once.
So from my understanding the only thing I need to do is to replace that search with a visit. Sadly replacing the call to depth_first_visit with a call to depth_first_visit is not as easy as I thought ...
For the record: The search call itself looks like this: boost::depth_first_search(mGraph, boost::visitor(printer).root_vertex(start));
Looking at the documentation [0] it seems that there is no version with named parameters for the depth first visit. So I need to pass the graph itself, the starting vertex, the visitor and a color map.
And its the color map that troubles me ... I have tried around a little to construct such a thing, but so far without success. My try can be found at [1]. This results in a massive compilation error [2].
I am not really experienced with the extent templates are used in the BGL and have no idea what the compiler tries to tell me.
Could anyone give me a hint what I am doing wrong?
If more sourcecode is required thats not a problem at all. Simply tell me if anything is missing. Access to the source is also not a problem, compilation is quite easy using cmake.
Thanks in advance Marcus Riemer
A raw std::vector is not enough to use as a color map. If your graph has a vertex index map (which is probably true), you can make a color map as: two_bit_color_map<property_map<Graph, vertex_index_t>::const_type> color_map(num_vertices(graph), get(vertex_index, graph)); I believe that is automatically cleared; otherwise, see the code in depth_first_search() that clears the color map (depth_first_visit() will not do that for you). -- Jeremiah Willcock
A raw std::vector is not enough to use as a color map. If your graph has a vertex index map (which is probably true), you can make a color map as:
two_bit_color_map<property_map<Graph, vertex_index_t>::const_type> color_map(num_vertices(graph), get(vertex_index, graph)); One general question: Wouldn't the const_type be, umm, constant? And therefore the algorithm can't alter the colors? I guess I am wrong, because passing an constant single color map would not make much sense. Or am I overseeing something?
Anyway: I tried to adapt that code and came along with the following: Not using a "using" clause is relevant for my code, as its meant for demonstration purposes and therefore it has to be instantly clear wich functionality comes from which library. boost::two_bit_color_map<boost::property_map< Graph, boost::vertex_index_t> >::const_type color_map(boost::num_vertices(mGraph), boost::get(boost::vertex_index, mGraph)); Which gives me a compilation error: /usr/include/boost/graph/two_bit_color_map.hpp: In instantiation of ‘boost::two_bit_color_map<boost::property_map<boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, BoostEntry, boost::property<boost::edge_weight_t, short int> >, boost::vertex_index_t> >’: /home/marcus/fhw/SeminarSS11/code/netzplan/boost/boost_precedence_diagram.cpp:20:79: instantiated from here /usr/include/boost/graph/two_bit_color_map.hpp:51:56: error: no type named ‘key_type’ in ‘struct boost::property_traits<boost::property_map<boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, BoostEntry, boost::property<boost::edge_weight_t, short int> >, boost::vertex_index_t> >’ /home/marcus/fhw/SeminarSS11/code/netzplan/boost/boost_precedence_diagram.cpp: In member function ‘virtual void BoostPrecedenceDiagram::printFollowingEntriesImplementation(const std::string&)’: /home/marcus/fhw/SeminarSS11/code/netzplan/boost/boost_precedence_diagram.cpp:20:2: error: ‘const_type’ is not a member of ‘boost::two_bit_color_map<boost::property_map<boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, BoostEntry, boost::property<boost::edge_weight_t, short int> >, boost::vertex_index_t> >’ It seems to my that my Graph type (an adjacency_list with a bundled property) does not provide a "key_type". How would I provide that? And is the "const_type member not found" simply a follow up of the first error? Or am I grabbing for the wrong type?
I believe that is automatically cleared; otherwise, see the code in depth_first_search() that clears the color map (depth_first_visit() will not do that for you). I will take a look, but I would hope that boost would not copy my local
color map and reuse it.
Thanks alot so far! Marcus Riemer
On Thu, 17 Mar 2011, Marcus Riemer wrote:
A raw std::vector is not enough to use as a color map. If your graph has a vertex index map (which is probably true), you can make a color map as:
two_bit_color_map<property_map<Graph, vertex_index_t>::const_type> color_map(num_vertices(graph), get(vertex_index, graph)); One general question: Wouldn't the const_type be, umm, constant? And therefore the algorithm can't alter the colors? I guess I am wrong, because passing an constant single color map would not make much sense. Or am I overseeing something?
The map you are getting using const_type is the vertex index map, which is read-only for many graph types simply because it is a function (often the identity, but don't rely on that). From your error message, it looks like you are missing the ::const_type when you try to get the vertex index map, or it is after two_bit_color_map rather than property_map<Graph, vertex_index_t>.
I believe that is automatically cleared; otherwise, see the code in depth_first_search() that clears the color map (depth_first_visit() will not do that for you). I will take a look, but I would hope that boost would not copy my local color map and reuse it.
It won't copy it (just a shallow copy), and depth_first_visit() won't clear it for you, but I believe a two_bit_color_map constructed with just an element count will be cleared by the constructor. -- Jeremiah Willcock
participants (2)
-
Jeremiah Willcock -
Marcus Riemer