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: Brian Budge (brian.budge_at_[hidden])
Date: 2013-01-17 20:02:27

On Jan 17, 2013 11:56 AM, "Ilja Honkonen" <ilja.honkonen_at_[hidden]> wrote:
>
> 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.
>
>
I am away from my computer for a while.  My best suggestion is to look
through the (very readable) source for depth_first_visit for how the
template argument gets used.  I supplied my own external map and had to
supply get and put functions correspondingly.

  Brian