Find all paths with loops in a directed graph, given the original vertex

Question

I have problems resolving this issue. I have to find all the simple paths starting from the original vertex s containing a simple loop in a directed graph. those. repetition is not allowed, with the exception, of course, of a single repeated vertex where the loop joins back to the path.

I know how to use a DFS visit to find if a graph has cycles, but I cannot find a way to use it to find all such paths starting with s.

For example, in this column

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

Starting with s , the STABCA path will be correctly found. But the STADCA path will not be found because vertex C is marked as visited by DFS.

Can someone tell me how to solve this problem? Thanks

Answer 1

This is actually a fairly simple algorithm, simpler than DFS. You simply enumerate all the paths in a naive recursive search, remembering not to rewrite it anywhere else when the path loops over itself:

(This is just Python-based pseudo-code. I hope it is 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) 

Answer 2

This is a common problem for garbage collection algorithms.

In .net training, I learned that the .net garbage collector detects cycles, starting with two pointers on the graph, one of which moves twice as fast as the other. If the fast advancer goes slow from behind, you have found a cycle. It will be more involved for complex schedules, but it will work without node marking.

Answer 3

When you find the loop, go back and mark the marked peaks when you step past them.

Suppose you find SABCA and want to find the next loop. A is your last node, you should not undo it. Return to C. Is there another edge coming out of C? No, so mark C and go back to B. Is there another edge coming out of B? No, cancel B and go back to A. Is there another edge coming out of A? Yes! there that goes to D. So go there, mark D, go to C, which is now not marked, and then A. Here you find another loop. You clean up again in A, but now there are no more paths that exit from A, so you uncheck A and return to S.

Answer 4

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

Since it uses IEnumerable, which is lazily enumerated, you can use DirectedGraphHelper.FindSimpleCycles (s) .First () if you want the first loop 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 will use it as follows:

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