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