# Getting an instance of a cycle in a directed graph

(I asked the same question in stackoverflow, but thought that this website might be the another good place to ask this.)

I want an algorithm that gives one instance of a cycle in a directed graph if there is any. Can anyone show me a direction maybe in pseudo-code?

I implemented Kahn's (1962) algorithm in Ruby that detects if a graph has a cycle, but I want to know not only whether it has a cycle, but also one possible instance of such cycle.

example_graph = [[1, 2], [2, 3], [3, 4], [3, 5], [3, 6], [6, 2]]


Kahn's algorithm

def cyclic?(graph)
## The set of edges that has not been examined
graph = graph.dup
n, m = graph.transpose
## The set of nodes that are the supremum in the graph
sup = (n - m).uniq
while sup_old = sup.pop do
sup_old = graph.select{|n, _| n == sup_old}
graph -= sup_old
sup_old.each {|_, ssup| sup.push(ssup) unless graph.any?{|_, n| n == ssup}}
end
!graph.empty?
end


The above algorithm tells whether a graph has a cycle:

cyclic?(example_graph) #=> true


but I want not only that but an example of a cycle like this:

#=> [[2, 3], [3, 6], [6, 2]]


If I were to output the variable graph of the above code at the end of examination, it will give:

#=> [[2, 3], [3, 4], [3, 5], [3, 6], [6, 2]]


which includes the cycle I want, but it also includes extra edges that are irrelevant to the cycle.

-

Use Tarjan's algorithm to look for strongly connected components. When you find a component with more than one node in it, it will be defined by one or more edges in the depth-first tree; such a back edge together with a path from one end to another in the depth-first tree is a cycle.

-
Thanks. This seems to be the best way to do it. –  sawa Mar 16 '12 at 1:20