Subject: Re: [boost] How to find all paths with a length in a certain range
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2012-07-18 17:38:37
On Tue, 17 Jul 2012, J Birch wrote:
> I am fairly new to Boost, and not the greatest at C++, but I do have a
> bit of experience in dealing with graphs in other languages.
> We currently have some very ugly and inefficient code that effectively
> builds up a graph structure (DAG), and must calculate all paths with a
> length between a certain range, say 3-7.
> I have seen the question asked a few times via Google, but I have seen
> no solution. I have been tinkering around with different examples, but
> have yet to come up with anything useful.
> Would anyone be able to point me in the right direction?
You might want to use dynamic programming on the graph, traversing it in a
reverse topological order. See
information on a related problem.
-- Jeremiah Willcock
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk