0
$\begingroup$

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

1 Answers 1

2

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.

  • 0
    Thanks. This seems to be the best way to do it.2012-03-16