Re: [Boost-users] [Graph] Switching from depth_first_search to depth_first_visit

Subject: Re: [Boost-users] [Graph] Switching from depth_first_search to depth_first_visit
From: Marcus Riemer (Marcus_at_[hidden])
Date: 2011-03-17 05:13:21

> 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