Find all paths with cycles in directed graph, given the source vertex

Question

I'm having trouble solving this problem. I have to find all simple paths starting from a source vertex s containing a simple cycle in a directed graph. i.e. No repeats allowed, except of course for the single repeated vertex where the cycle joins back on the path.

I know how to use a DFS visit to find if the graph has cycles, but I can't find a way to use it to find all such paths starting from s.

For example, in this graph

        +->B-+
        |    v
s-->T-->A<---C
        |    ^
        +->D-+

Starting from s, the path S-T-A-B-C-A will correctly be found. But the path S-T-A-D-C-A will not be found, because the vertex C is marked as Visited by DFS.

Can someone hint me how to solve this problem? Thanks

There may be infinitely many paths containing cycles... can you be more specific about what precisely you're looking for? — templatetypedef, Jan 16 '12 at 20:08
You probably mean paths that do not visit the same vertex again. Is this right? Even then, there will still probably be a stupendous number of them. So you probably want only the smallest cycles? Define a *minimal cycle* to be such that there is no shorter cycle among any subset of its members. Maybe you want all the *minimal cycles*? — Aaron McDaid, Jan 16 '12 at 20:19
Sorry, I meant paths, not cycles. What I'm searching for is a list of all paths in the graph starting from a vertex S and containing a simple cycle. — Jubstuff, Jan 16 '12 at 20:42
You mean all *simple* paths containing a *simple* cycle, where the path starts at *s*? One more question: do you require that *s* be in the cycle or not? Your question is a bit ambiguous on this last point, at one point you say "find all the cycles starting from s". — Aaron McDaid, Jan 16 '12 at 21:10
There will still probably be a *lot* of cycles. In all the networks I deal with, if you start at a node and go on a long random walk, there will almost always be a route back to the start node, where no nodes have ever been revisited. There will be more such paths than you can store on your hard disk! — Aaron McDaid, Jan 16 '12 at 21:15
There can be an exponential number of cycles. For a graph with 20 or so edges, one can probably enumerate all the cycles in a reasonable amount of time. — n. m. could be an AI, Jan 16 '12 at 21:41
@AaronMcDaid no, s doesn't need to be in the cycle. I know that there will be many, but I need to find all of them. — Jubstuff, Jan 18 '12 at 11:31

Aaron McDaid · Accepted Answer · 2012-01-18T12:11:12.840

6

This is actually quite an easy algorithm, simpler than DFS. You simply enumerate all paths in a naive recursive search, remembering not to recurse any further any time the path loops back on itself:

(This is just a Python-inspired pseudocode. I hope it's clear enough.)

 def find_paths_with_cycles(path_so_far):
       node_just_added = path_so_far.back()
       for neigh in out_neighbours(node_just_added):
           if neigh in path_so_far:
               # this is a cycle, just print it
               print path_so_far + [neigh]
           else:
               find_paths_with_cycles(path_so_far + [neigh])


 initial_path = list()
 initial_path.append(s)
 find_paths_with_cycles(initial_path)

edited Jan 18 '12 at 12:11

answered Jan 16 '12 at 22:13

Aaron McDaid

26,501
9
66
88

Nice clear code. In terms of performance, would this find all the simple paths only once or can they be found multiple times? – Clement May 15 '14 at 22:46
1

@Clement, All such paths will be found only once. But there may still be very many of them. For example, it would find `S->A->B->X->Y->Z-X` and `S->B->A->X->Y->Z-X` as separate paths, even though they each contain the same cycle (`X->Y->Z->X`) and use the same nodes to get there (`A` and `B`). The only difference is the order they visit `A` and `B`. – Aaron McDaid May 19 '14 at 13:07
This code will not detect cycles in the graph that do not begin with the `path_so_far` variable – Naveen Dennis Apr 19 '17 at 03:03
@NaveenDennis, it will find such cycles, as requested in the question. This doesn't require that `S` be in the cycle – Aaron McDaid Apr 19 '17 at 17:43

Clement · Answer 2 · 2014-05-15T23:21:15.100

I went ahead and implemented Aaron's algorithm in C#.

Because it uses IEnumerable, which is lazily enumerated, you can use DirectedGraphHelper.FindSimpleCycles(s).First() if you only want the first cycle to be found:

public static class DirectedGraphHelper
{
    public static IEnumerable<Node[]> FindSimpleCycles(Node startNode)
    {
        return FindSimpleCyclesCore(new Stack<Node>(new[] { startNode }));
    }

    private static IEnumerable<Node[]> FindSimpleCyclesCore(Stack<Node> pathSoFar)
    {
        var nodeJustAdded = pathSoFar.Peek();
        foreach (var target in nodeJustAdded.Targets)
        {
            if (pathSoFar.Contains(target))
            {
                yield return pathSoFar.Reverse().Concat(new[] { target }).ToArray();
            }
            else
            {
                pathSoFar.Push(target);
                foreach (var simpleCycle in FindSimpleCyclesCore(pathSoFar))
                {
                    yield return simpleCycle;
                }
                pathSoFar.Pop();
            }
        }
    }
}

public class Node
{
    public string Id { get; private set; }
    public readonly List<Node> Targets = new List<Node>();

    public Node(string id)
    {
        this.Id = id;
    }
}

And you would use it like this:

class Program
{
    static void Main(string[] args)
    {
        var s = new Node("s");
        var t = new Node("t");
        var a = new Node("a");
        var b = new Node("b");
        var c = new Node("c");
        var d = new Node("d");

        s.Targets.Add(t);
        t.Targets.Add(a);
        a.Targets.AddRange(new[] { b, d });
        b.Targets.Add(c);
        c.Targets.Add(a);
        d.Targets.Add(c);

        foreach (var cycle in DirectedGraphHelper.FindSimpleCycles(s))
        {
            Console.WriteLine(string.Join(",", cycle.Select(n => n.Id)));
        }
        Console.Read();
    }
}

score 0 · Answer 3 · answered Jan 16 '12 at 21:22

This is a common problem for garbage collection algorithms.

At a .net training, I learned that the .net garbage collector detects cycles by starting with two pointers in the graph, one of which advances at twice the speed as the other. If the fast advancing one runs into the slow one from behind, you found a cycle. It will be more involved for complex graphs, but it will work without labeling the nodes.

score 0 · Answer 4 · answered Jan 16 '12 at 21:37

When you find a cycle, go back and unmark marked vertices as you retract past them.

Suppose you have found SABCA and want to find the next cycle. A is your final node, you should not unmark it. Go back to C. Is there another edge going out of C? No, so unmark C and go back to B. Is there another edge going out of B? No, unmark B and go back to A. Is there another edge going out of A? Yes! there's one that goes to D. So go there, mark D, go to C which is now unmarked, then to A. Here, you have found another cycle. You again retract to A, but now there are no more paths that lead out of A, so you unmark A and go back to S.

Find all paths with cycles in directed graph, given the source vertex

4 Answers4

Linked