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
– templatetypedef, Commented Jan 16, 2012 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
– Aaron McDaid, Commented Jan 16, 2012 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
– Jubstuff, Commented Jan 16, 2012 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
– Aaron McDaid, Commented Jan 16, 2012 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
– Aaron McDaid, Commented Jan 16, 2012 at 21:15

Aaron McDaid · Accepted Answer · 2012-01-18 12:11:12Z

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, 2012 at 12:11

answered Jan 16, 2012 at 22:13

Aaron McDaid

27.3k10 gold badges73 silver badges95 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

Clement Over a year ago

Nice clear code. In terms of performance, would this find all the simple paths only once or can they be found multiple times?

Aaron McDaid Over a year ago

@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.

Naveen Dennis Over a year ago

This code will not detect cycles in the graph that do not begin with the path_so_far variable

Aaron McDaid Over a year ago

@NaveenDennis, it will find such cycles, as requested in the question. This doesn't require that S be in the cycle

user180326 · Accepted Answer · 2012-01-16 21:22:40Z

0

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.

answered Jan 16, 2012 at 21:22

user180326

Comments

n. m. could be an AI · Accepted Answer · 2012-01-16 21:37:18Z

0

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.

answered Jan 16, 2012 at 21:37

n. m. could be an AI

122k14 gold badges141 silver badges267 bronze badges

Comments

Clement · Accepted Answer · 2014-05-15 23:21:15Z

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

Collectives™ on Stack Overflow

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

4 Answers 4

4 Comments

Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

4 Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related