[Graph] Switching from depth_first_search to depth_first_visit

[Marcus Riemer]

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

[Jeremiah Willcock]

Post by Marcus Riemer
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 ...
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

[Marcus Riemer]

A raw std::vector is not enough to use as a color map. If your graph has
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

[Jeremiah Willcock]

Post by Marcus Riemer

A raw std::vector is not enough to use as a color map. If your graph has
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>.

Post by Marcus Riemer

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