Boost logo

Boost :

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 for
information on a related problem.

-- Jeremiah Willcock

Boost list run by bdawes at, gregod at, cpdaniel at, john at