Giving an Example of a Cycle in a Directed Graph

Giving an example of a cycle in a directed graph

I asked the same question in the math stackexchange site, and got an answer. It turned out that Tarjan's algorithm is good for solving this problem. I implemented it in Ruby as follows:

module DirectedGraph; module_function
    ## Tarjan's algorithm
    def strongly_connected_components graph
        @index, @stack, @indice, @lowlink, @scc = 0, [], {}, {}, []
        @graph = graph
        @graph.flatten(1).uniq.each{|v| strong_connect(v) unless @indice[v]}
        @scc
    end
    def strong_connect v
        @indice[v] = @index
        @lowlink[v] = @index
        @index += 1
        @stack.push(v)
        @graph.each do |vv, w|
            next unless vv == v
            if !@indice[w]
                strong_connect(w)
                @lowlink[v] = [@lowlink[v], @lowlink[w]].min
            elsif @stack.include?(w)
                @lowlink[v] = [@lowlink[v], @indice[w]].min
            end
        end
        if @lowlink[v] == @indice[v]
            i = @stack.index(v)
            @scc.push(@stack[i..-1])
            @stack = @stack[0...i]
        end
    end
end

So if I apply it to the example above, I get a list of strongly connected components of the graph:

example_graph = [[1, 2], [2, 3], [3, 4], [3, 5], [3, 6], [6, 2]]
DirectedGraph.strongly_connected_components(example_graph)
#=> [[4], [5], [2, 3, 6], [1]]

By selecting those components that are longer than one, I get the cycles:

DirectedGraph.strongly_connected_components(example_graph)
.select{|a| a.length > 1}
#=> [[2, 3, 6]]

And further if I select from the graph the edges whose both vertices are included in the components, I get the crucial edges that constitute the cycles:

DirectedGraph.strongly_connected_components(example_graph)
.select{|a| a.length > 1}
.map{|a| example_graph.select{|v, w| a.include?(v) and a.include?(w)}}
#=> [[[2, 3], [3, 6], [6, 2]]]

Best algorithm for detecting cycles in a directed graph

Tarjan's strongly connected components algorithm has O(|E| + |V|) time complexity.

For other algorithms, see Strongly connected components on Wikipedia.

Detecting a cycle in a directed graph

Well, you probably got confused between the definition of a back-edge in a directed graph and a back-edge in an undirected graph. Yes, they are different.

While in undirected graph back edges are edges from the current vertex to an-already-visited vertex. (as OP from your link mentioned).

In directed graph the definition for back edge is different. A back edge in a directed graph is an edge from current vertex to a GREY vertex (the DFS for this vertex has started but not yet finished), meaning it is still in the recursion stack.

So if you take the definition of a back edge as it is in a directed graph then yes, it is enough for detecting a cycle.

But if you take the definition of a back edge as it is in an undirected graph then you will need also to make sure that v is in the recursion stack in order to detect a cycle.

See this and this for more information and examples.

Example:
Consider the DFS visit order to be A -> B -> C.

In this example, the edge <A,C> is a back edge in the undericted graph (as C was already visited).

But it is not a back edge in this directed graph - C was already visited but is not in the recursion stack, meaning it is not a cycle.
Sample Image

Finding a cycle in a directed graph using BFS or DFS

DFS algorithm classifies graph edges into three categories^*:

Forward edges
Cross edges
Back edges

If your graph has a back edge, it has a cycle. When you run a DFS algorithm and see a backedge, examine the portion of the path from the vertex to which the back edge leads to the current node will give you a set of nodes from the cycle to which the back edge belongs.

^* Sometimes, tree edges are treated as a separate category from forward edges, which is insignificant for the purposes of this discussion.

Detecting cycles in a graph using DFS: 2 different approaches and what's the difference

Answering my question:

The graph has a cycle if and only if there exists a back edge. A back edge is an edge that is from a node to itself (selfloop) or one of its ancestor in the tree produced by DFS forming a cycle.

Both approaches above actually mean the same. However, this method can be applied only to undirected graphs.

The reason why this algorithm doesn't work for directed graphs is that in a directed graph 2 different paths to the same vertex don't make a cycle. For example: A-->B, B-->C, A-->C - don't make a cycle whereas in undirected ones: A--B, B--C, C--A does.

Find a cycle in undirected graphs

An undirected graph has a cycle if and only if a depth-first search (DFS) finds an edge that points to an already-visited vertex (a back edge).

Find a cycle in directed graphs

In addition to visited vertices we need to keep track of vertices currently in recursion stack of function for DFS traversal. If we reach a vertex that is already in the recursion stack, then there is a cycle in the tree.

Update:
Working code is in the question section above.

Traversal directed graph with cycles

As noted, there is an infinite number of such paths.

However, you can still generate all of them in a lazy way by maintaining all nodes v (and path you used to reach v) you can reach from the start node in k steps for k=1,2,...; if v is your target node, remember it.

When you have to return the next path, (i) pop the first target node off list, and (ii) generate the next candidates for all non-target nodes on the list. If there is no target node on the list, repeat (ii) until you find one.

The method works assuming the path always exists. If you don't find a path in n-1 steps, where n is the number of nodes, simply report that no path exists.

Here's the pseudo code for an algorithm that generates paths from shortest to longest assuming unit weights:

class Node {
    int steps
    Node prev

    Node(int steps=0, Node prev=null) {
        prev = prev
        steps = steps
    }
}

class PathGenerator {
    Queue<Node> nodes
    Node start, target;

    PathGenerator(Node start, Node target) {
        start = start
        target = target

        nodes = new Queue<>()
        nodes.add(start) // assume start.steps=0 and stat.prev=null
    }

    Node nextPath(int n) {
        current_length = -1;
        do {
            node = nodes.poll()
            current_length = node.steps
            // expand to all others you can reach from node
            for each u in node.neighbors()
                list.add(new Node(node, node.steps+1))
            // if node is the target, return the path
            if (node == target)
                return node
        } while (current_length < n);
       throw new Exception("no path of length <=n exists");
    }
}

Beware that the list nodes can grow exponentially in the worst case (think of what happens in case you run it on a complete graph).

Giving an Example of a Cycle in a Directed Graph