On Mon, Jan 14, 2013 at 11:18 AM, Jeremiah Willcock <jewillco@osl.iu.edu> 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