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-15 04:23:51

On Mon, Jan 14, 2013 at 11:18 AM, Jeremiah Willcock <jewillco_at_[hidden]> wrote:
> On Sat, 12 Jan 2013, Ilja Honkonen wrote:
>
>> Hello
>>
>> Is it possible to do a limited depth depth first search without using O(N)
>> 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, ...>?
>
>
> Look at depth_first_visit_impl in <boost/graph/depth_first_search.hpp>; that
> appears to have a way to terminate the search early.  I have asked about
> getting the link mentioned in that code working again.
>
> -- Jeremiah Willcock
>

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.

  Brian