Encontrar todos los bucles cerrados en un gráfico

Estoy tratando de escribir un código Python que identificará todos los bucles cerrados dentro de un gráfico arbitrario.

Por bucle cerrado, me refiero a un bucle que no visita ningún vértice más de una vez, con la excepción del vértice en el que comienza el bucle (en el caso de esta imagen , DGHD es un ejemplo, como es BCDB , o BCEFDB , etc.) .

Intenté hacer esto con la multiplicación de matrices, escribiendo el gráfico como una matriz con 1s donde se conectan 2 vértices y un 0 donde no lo están, y colocándolos en la potencia nth, sin embargo, esto también tendrá en cuenta los bucles no cerrados.

Esta persona parece haber tenido el mismo trabajo, pero logró resolverlo:

  • Encontrar bucles únicos en el gráfico cerrado.

Me preguntaba si habría algún consejo sobre qué dirección tomar.

NetworkX es un popular paquete de Python para trabajar con gráficos incluidos en muchas distribuciones científicas de Python. Incluye algunos algoritmos para computar ciclos gráficos. En particular, simple_cycles(DiGraph) respondería a su pregunta.

Una advertencia a este enfoque es que tienes que convertir tu gráfica en un dígrafo. Esto significa que cada borde de su gráfico no dirigido se convertirá en un ciclo en su versión dirigida. (Un borde no dirigido se convierte en dos bordes dirigidos). Simplemente puede filtrar la salida para que solo contenga ciclos de longitud tres o más.

Aquí hay un ejemplo usando el gráfico al que has vinculado:

 from networkx import Graph, DiGraph, simple_cycles # construct a graph using a dict: {node:[connected_nodes]} G = Graph( {'A':['B','G','H'], 'B':['A','C','D'], 'C':['B','D','E'], 'D':['B','C','E','F','G', 'H'], 'E':['C','D','F'], 'F':['D','E','G'], 'G':['A','D','F','H'], 'H':['A','D','G'], } ) # optional: draw the graph for verification #labels = dict(zip(G.nodes(),G.nodes())) #networkx.draw_networkx(G,labels=labels) # simple_cycles only accepts DiGraphs. convert G to a bi-directional # digraph. note that every edge of G will be included in this list! DG = DiGraph(G) list(simple_cycles(DG)) 

La salida (truncada) es:

 [['B', 'D', 'H', 'G', 'F', 'E', 'C'], ['B', 'D', 'H', 'G', 'A'], ['B', 'D', 'H', 'A', 'G', 'F', 'E', 'C'], ['B', 'D', 'H', 'A'], ['B', 'D', 'F', 'G', 'H', 'A'], ['B', 'D', 'F', 'G', 'A'], ['B', 'D', 'F', 'E', 'C'], ['B', 'D', 'G', 'F', 'E', 'C'], ... ] 

Si prefiere implementar esto usted mismo sin usar NetworkX, simple_cycles() usa el algoritmo de Johnson. (Ver Donald B. Johnson, Encontrando todos los circuitos elementales de una gráfica dirigida , SIAM J. Comput., 4 (1), 77–84)