Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
add comment

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer
    
Thanks. This seems to be the best way to do it. –  sawa Mar 16 '12 at 1:20
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.