Buscar todas las bases de ciclo en un gráfico, con las coordenadas vértice dadas

Question

Una pregunta similar is posted here.

Tengo un gráfico no dirigido con Vertex V y Edge E. Estoy buscando un algoritmo para identificar todas las bases de ciclo en ese gráfico. Un ejemplo de un gráfico de este tipo se muestra a continuación:

Ahora, todas las coordenadas de vértices son conocido (a diferencia pregunta anterior, y contraria a la explicación en el diagrama anterior) Por lo tanto, es posible encontrar los ciclos más pequeños que abarcan todo el gráfico.

En este gráfico, es posible que haya bordes que no forman ningún ciclo.

¿Cuál es el mejor algoritmo para hacer esto?

Aquí es otro ejemplo de que se puede echar un vistazo a:

Suponiendo que e1 es el borde que es recogido en primer lugar, y la flecha muestra la dirección del borde.

Answer 1

No he probado esto y es bastante codicioso pero debería funcionar:

1. Escoja un nodo
2. ir a uno de TI de los vecinos de
3. seguir adelante hasta llegar de nuevo a su nodo de partida , pero no puedes visitar un nodo antiguo.
4. Si obtiene un ciclo, guárdelo si aún no existe o un subconjunto de esos nodos constituye un ciclo. Si el nodo en el ciclo es un subconjunto de los nodos en otro ciclo, elimine el ciclo más grande (¿o tal vez se divida en dos?)
5. Comience en 2 con un vecino nuevo.
6. Comienza de nuevo en 1 con un nuevo nodo.

Comentarios: En 3 deberías, por supuesto, hacer lo mismo que para el paso 2, así que toma todos los caminos posibles.

Quizás eso sea un comienzo? Como dije, no lo he probado, así que no está optimizado.

EDIT: Una versión no documentada y no optimizada de una implementación del algoritmo se puede encontrar aquí: https://gist.github.com/750015. Pero no resuelve completamente la solución, ya que solo puede reconocer subconjuntos "verdaderos".