Dar un ejemplo de un ciclo en un gráfico dirigido.

Quiero un algoritmo que dé una instancia de un ciclo en un gráfico dirigido si hay alguno. ¿Alguien me puede mostrar una dirección? ¿En pseudocódigo, o preferentemente, en Ruby?

Anteriormente hice una pregunta similar y, siguiendo las sugerencias, implementé el algoritmo de Kahn en Ruby que detecta si una gráfica tiene un ciclo, pero quiero no solo si tiene un ciclo, sino también una posible instancia de dicho ciclo.

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 

El algoritmo anterior indica si un gráfico tiene un ciclo:

 cyclic?(example_graph) #=> true 

Pero no solo quiero eso, sino un ejemplo de un ciclo como este:

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

Si tuviera que dar salida a la graph la variable en el código anterior al final del examen, dará:

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

que incluye el ciclo que quiero, pero también incluye bordes adicionales que son irrelevantes para el ciclo.

Hice la misma pregunta en el sitio de intercambio de matemáticas y obtuve una respuesta. Resultó que el algoritmo de Tarjan es bueno para resolver este problema. Lo implementé en Ruby de la siguiente manera:

 module DirectedGraph; module_function ## Tarjan's algorithm def strongly_connected_components graph @index, @stack, @indice, @lowlink, @scc = 0, [], {}, {}, [] @graph = graph @graph.flatten(1).uniq.each{|v| strong_connect(v) unless @indice[v]} @scc end def strong_connect v @indice[v] = @index @lowlink[v] = @index @index += 1 @stack.push(v) @graph.each do |vv, w| next unless vv == v if !@indice[w] strong_connect(w) @lowlink[v] = [@lowlink[v], @lowlink[w]].min elsif @stack.include?(w) @lowlink[v] = [@lowlink[v], @indice[w]].min end end if @lowlink[v] == @indice[v] i = @stack.index(v) @scc.push(@stack[i..-1]) @stack = @stack[0...i] end end end 

Entonces, si lo aplico al ejemplo anterior, obtengo una lista de componentes fuertemente conectados del gráfico:

 example_graph = [[1, 2], [2, 3], [3, 4], [3, 5], [3, 6], [6, 2]] DirectedGraph.strongly_connected_components(example_graph) #=> [[4], [5], [2, 3, 6], [1]] 

Al seleccionar aquellos componentes que son más largos que uno, obtengo los ciclos:

 DirectedGraph.strongly_connected_components(example_graph) .select{|a| a.length > 1} #=> [[2, 3, 6]] 

Y además, si selecciono de la gráfica los bordes cuyos vértices están incluidos en los componentes, obtengo los bordes cruciales que constituyen los ciclos:

 DirectedGraph.strongly_connected_components(example_graph) .select{|a| a.length > 1} .map{|a| example_graph.select{|v, w| a.include?(v) and a.include?(w)}} #=> [[[2, 3], [3, 6], [6, 2]]] 

La primera búsqueda en profundidad, donde se realiza un seguimiento de los vértices visitados y el padre le dará el ciclo. Si ve un borde en un vértice visitado anteriormente, entonces ha detectado un ciclo entre su padre, usted y ese vértice. Un pequeño problema que puede encontrar es que, si se trata de un ciclo de longitud> 3, solo podrá indicar los tres vértices involucrados y tendrá que investigar un poco para encontrar el rest de vértices en el ciclo.

Para la investigación, puede iniciar una amplia búsqueda en primer lugar ‘arriba’ del árbol a partir del padre y buscar el vértice visitado, debería poder encontrar todo el ciclo haciendo eso.