Find all paths with cycles in directed graph, give

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

Answer 1

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.

Answer 2

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.

Answer 3

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();
    }
}

Answer 4

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)