With multiple cycles between 2 nodes

Question

Trying to find all cycles in a directed graph, via DFS. But got an issue.

---

Issue

When there are multiple cycles between 2 nodes, sometimes only the longest one can be detected, the shorter one is skipped.

This is due to when a node is visited, I will skip it, thus that shorter cycle is skipped. But, if I don't skip visited node, the DFS search will repeat forever.

---

Example

Graph:

1 -> [2, 4]
2 -> [3]
3 -> [4]
4 -> [1]

There are 2 cycles between 1 and 4:

• (A) 1 -> 2 -> 3 -> 4 -> 1
• (B) 1 -> 4 -> 1

Cycle B can't be detected, if A is detected first, because 4 will be skipped due to visited, and it never goes back to 1.

---

Current ideas

• One possible solution is to start from every node, even it's already visited. But I want a better solution.
• Calculate & remember hash of path, skip only when the same hash exists? That would take some memory, right? And, there are still possibility 2 different path with the same hash lead to the same node, it can't solve the problem entirely.

Any idea?

Answer 1

Credits: https://www.hackerearth.com/practice/notes/finding-all-elementry-cycles-in-a-directed-graph/

integer list array A(n);logical array marked(n);integer stack current_stack ;integer stack marked_stack;/* A(n) is the array of list wich is adjacency list representation*/
 integer procedure intialize(); /*initialize the values*/
    begin;
    for i in n do 
         marked(i):=false
integer procedure print_cycles();
    begin
        for i in current_stack do
            print i ;       
logical procedure backtrack(k) do
    begin
        logical flag=false;
        current_stack->push(k);
        marked_stack->push(k);
        marked(n):=true;
        for i in A(k) do
            if i < s; /* To find only disticnt cycles in topological manner*/
               delete A(i);
            if i==s; /Cycle found */
                print_cycles()
            if marked(i):= false;
                backtrack(n); /*continue dfs*/
        if flag :=true;
            for i in marked_stack do /*unmark the elements that have been visited in any of the cycles starting from s*/
                marked(i):=false;
        current_stack->pop(k);
        backtrack:=flag
    end   backtrack(k)
begin 
    integer procedure backtrack_Util();
        begin
            for s in n do
               backtrack(s);
               while marked_stack(s)->empty do
                    for i in marked_stack do
                        marked(i):=false
     end backtrack_Util()

We want to find distinct cycles. Hence, we need to visit vertices in some order. In that order, we need to find cycles starting from that vertex and the cycle should not contain any vertices that are before the starting vertex in the ordering. How to obtain that ordering? The words topological manner in one of the comments above is ambiguous with topological sort which is not the case. I think we can pick an ordering as simple as vertex number like 0,1,2,..,v. Let us say we wish to find a cycle starting from 2. To avoid finding of duplicate cycles, we will not use vertex 0 and 1. If there is any cycle that consists of edge from 2 to 1 or 2 to 0, it would already have been considered when finding cycles starting from 0 or 1.

---

Let me introduce a concrete reference that will help you with the task. It is Johnson's algorithm. Apparently, it is the fastest way to accomplish the task.

On page 3, it mentions:

To avoid duplicating circuits, a vertex v is blocked when it is added to some elementary path beginning in s. It stays blocked as long as every path from v to s intersects the current elementary path at a vertex other than s. Furthermore, a vertex does not become a root vertex for constructing elementary paths unless it is the least vertex in at least one elementary circuit.

You can also watch this youtube video for more understanding.

I think this information is acceptable.