Boost logo

Boost Users :

Subject: Re: [Boost-users] [BGL] Limited depth search without O(number_of_verices) complexity?
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2013-01-14 14:18:09


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


Boost-users list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net