Re: [Boost-users] [BGL] Limited depth search without O(number_of_verices) complexity?

Subject: Re: [Boost-users] [BGL] Limited depth search without O(number_of_verices) complexity?
From: Ilja Honkonen (ilja.honkonen_at_[hidden])
Date: 2013-01-17 14:55:52

15.01.2013 11:23, Brian Budge пишет:
>>> additional memory? The following code seems to visit only a part of the
>>> graph but it still requires O(N) memory for the external color map. Could
>>> that be avoided with an internal color map? I didn't manage to get
>>> depth_first_visit(...) to use an internal color map. Would the solution work
>>> also with other graph types besides <vecS, vecS, ...>?
> You can also supply a custom color map.  I think if you look for
> examples using the two_bit_color_map, you'll be able to figure out how
> to do this using something like a boost::unordered_map, which should
> use on the order of the number of touched items memory.

I've been looking at various files for a while now and have only found 
examples where an external vector is used for the map and no hint on how 
to use something else. Or does the following code in bfs.hpp have 
something to do with this (use vertex_color or something)?
choose_const_pmap(get_param(params, vertex_index),
                   g, vertex_index)),

The color map seems to be a template parameter everywhere except in 
places which add at least one more layer of indirection with 
bgl_named_params.

Also it looks like the two_bit_color_map constructor always allocates 
memory for all vertices anyway.

This page 
http://stackoverflow.com/questions/11666131/color-map-in-boost-graph-breadth-first-visit 
looks promising but even a simple program in that style doesn't compile:

typedef adjacency_list<vecS, vecS, undirectedS> Graph_T;
property_map<Graph_T, vertex_color_t>::type colors;

/usr/include/boost/graph/detail/adjacency_list.hpp: In instantiation of 
”struct boost::vec_adj_list_any_vertex_pa::bind_<boost::vertex_color_t, 
boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS>, 
boost::no_property>”:
/usr/include/boost/graph/detail/adjacency_list.hpp:2592:12:   required 
from ”struct 
boost::detail::vec_adj_list_choose_vertex_pa<boost::vertex_color_t, 
boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS>, 
boost::no_property>”
/usr/include/boost/graph/detail/adjacency_list.hpp:2718:12:   required 
from ”struct 
boost::vec_adj_list_vertex_property_selector::bind_<boost::adjacency_list<boost::vecS, 
boost::vecS, boost::undirectedS>, boost::no_property, 
boost::vertex_color_t>”
/usr/include/boost/graph/properties.hpp:217:12:   required from ”struct 
boost::detail::vertex_property_map<boost::adjacency_list<boost::vecS, 
boost::vecS, boost::undirectedS>, boost::vertex_color_t>”
/usr/include/boost/graph/properties.hpp:228:10:   required from ”struct 
boost::property_map<boost::adjacency_list<boost::vecS, boost::vecS, 
boost::undirectedS>, boost::vertex_color_t>”
graafitesti.cpp:38:46:   required from here
/usr/include/boost/graph/detail/adjacency_list.hpp:2541:29: virhe: 
forming reference to void
          typedef value_type& reference;
                              ^
/usr/include/boost/graph/detail/adjacency_list.hpp:2542:35: virhe: 
forming reference to void
          typedef const value_type& const_reference;
                                    ^
/usr/include/boost/graph/detail/adjacency_list.hpp:2545:55: virhe: 
forming reference to void
            <Graph, Graph*, value_type, reference, Tag> type;
                                                        ^
/usr/include/boost/graph/detail/adjacency_list.hpp:2547:67: virhe: 
forming reference to void
            <Graph, const Graph*, value_type, const_reference, Tag> 
const_type;
                                                                    ^
Something is apparently missing but what and from where? Or what should 
be the first parameter of property_map in this case?

Ilja