All paths in a directed graph

Topics: algorithm, graph
Mar 14, 2013 at 12:40 PM
I am looking for an algorithm to find all paths from one given vertex to another given vertex in a directed non-acyclic graph. The paths must include cycles as well, but only once. For example, if you have a graph like this:

A->B
B->C
B->D
C->A

and your start node is A and end node is D, I want my paths to be:

A, B, D
A, B, C, A, B, D

but not

A, B, C, A, B, C, A, B, C, D

Naturally, the C node could be a whole other subgraph.
I have an algorithm based on depth-first search but it stops as soon as it visits a vertex twice so it does not find the path that includes a cycle.

I realize this is more of a graph theory question than a QuickGraph one but I hope someone can help.
Apr 10, 2013 at 12:34 PM
If my (notoriously flaky) memory from 20 years ago doesn't deceive me, what you're asking isn't all that easy.