Quero um algoritmo que forneça uma instância de um ciclo em um gráfico direcionado, se houver algum. Alguém pode me mostrar uma direção? Em pseudo-código, ou preferencialmente, em Ruby?

Eu perguntei anteriormenteuma pergunta semelhante, e seguindo as sugestões lá, implementei o algoritmo de Kahn em Ruby que detecta se um gráfico tem um ciclo, mas quero não apenas se ele tem um ciclo, mas também uma possível instância desse cicl

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

Algoritmo de Kahn

def cyclic? graph
  ## The set of edges that have 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

O algoritmo acima informa se um gráfico tem um ciclo:

cyclic?(example_graph) #=> true

mas eu quero não apenas isso, mas um exemplo de ciclo como este:

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

Se eu fosse exibir a variávelgraph no código acima, no final do exame, fornecerá:

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

que inclui o ciclo que eu quero, mas também inclui arestas extras que são irrelevantes para o cicl