Encontrar todos los ciclos en un gráfico dirigido
¿Cómo puedo encontrar (iterar) TODOS los ciclos en un gráfico dirigido desde/hacia un nodo determinado?
Por ejemplo, quiero algo como esto:
A->B->A
A->B->C->A
pero no: B->C->B
Encontré esta página en mi búsqueda y dado que los ciclos no son lo mismo que los componentes fuertemente conectados, seguí buscando y finalmente encontré un algoritmo eficiente que enumera todos los ciclos (elementales) de un gráfico dirigido. Es de Donald B. Johnson y el artículo se puede encontrar en el siguiente enlace:
http://www.cs.tufts.edu/comp/150GA/homeworks/hw1/Johnson%2075.PDF
Se puede encontrar una implementación de Java en:
http://normalisiert.de/code/java/elementaryCycles.zip
Puede encontrar una demostración de Mathematica del algoritmo de Johnson aquí ; la implementación se puede descargar desde la derecha ( "Descargar código de autor" ).
Nota: En realidad, existen muchos algoritmos para este problema. Algunos de ellos se enumeran en este artículo:
http://dx.doi.org/10.1137/0205007
Según el artículo, el algoritmo de Johnson es el más rápido.
La primera búsqueda en profundidad con retroceso debería funcionar aquí. Mantenga una serie de valores booleanos para realizar un seguimiento de si visitó un nodo antes. Si se queda sin nuevos nodos a los que ir (sin llegar a un nodo en el que ya haya estado), simplemente retroceda y pruebe con una rama diferente.
El DFS es fácil de implementar si tiene una lista de adyacencia para representar el gráfico. Por ejemplo adj[A] = {B,C} indica que B y C son hijos de A.
Por ejemplo, el pseudocódigo siguiente. "inicio" es el nodo desde el que comienza.
dfs(adj,node,visited):
if (visited[node]):
if (node == start):
"found a path"
return;
visited[node]=YES;
for child in adj[node]:
dfs(adj,child,visited)
visited[node]=NO;
Llame a la función anterior con el nodo inicial:
visited = {}
dfs(adj,start,visited)
La opción más sencilla que encontré para resolver este problema fue utilizar la biblioteca de Python llamada networkx.
Implementa el algoritmo de Johnson mencionado en la mejor respuesta de esta pregunta, pero su ejecución es bastante sencilla.
En resumen necesitas lo siguiente:
import networkx as nx
import matplotlib.pyplot as plt
# Create Directed Graph
G=nx.DiGraph()
# Add a list of nodes:
G.add_nodes_from(["a","b","c","d","e"])
# Add a list of edges:
G.add_edges_from([("a","b"),("b","c"), ("c","a"), ("b","d"), ("d","e"), ("e","a")])
#Return a list of cycles described as a list o nodes
list(nx.simple_cycles(G))
Respuesta: [['a', 'b', 'd', 'e'], ['a', 'b', 'c']]
