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

17 Jan 2013

      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 ?
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... 
looks promising but even a simple program in that style doesn't compile:

typedef adjacency_list Graph_T;
property_map::type colors;

/usr/include/boost/graph/detail/adjacency_list.hpp: In instantiation of 
”struct boost::vec_adj_list_any_vertex_pa::bind_, 
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::no_property>”
/usr/include/boost/graph/detail/adjacency_list.hpp:2718:12:   required 
from ”struct 
boost::vec_adj_list_vertex_property_selector::bind_, boost::no_property, 
boost::vertex_color_t>”
/usr/include/boost/graph/properties.hpp:217:12:   required from ”struct 
boost::detail::vertex_property_map, boost::vertex_color_t>”
/usr/include/boost/graph/properties.hpp:228:10:   required from ”struct 
boost::property_map, 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
             type;
                                                        ^
/usr/include/boost/graph/detail/adjacency_list.hpp:2547:67: virhe: 
forming reference to void

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

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

Ilja Honkonen