Extracción de ciclos sin cuerda de un gráfico no dirigido

Hace varios años tuve que sumergirme en este tema en el trabajo. Buscando en Google, para mi sorpresa, no encontré ninguna solución preparada. Y aún así, en general, no se ve nada. Entonces tuve que desarrollar el tema desde cero.



Para dejar claro de qué se trata, daré el ejemplo más simple.







El gráfico es muy simple, y para este tipo de gráficos es fácil crear un algoritmo que seleccione ciclos sin cuerda (es decir, ciclos que no tienen intersecciones propias y no se pueden dividir en otros más pequeños). El problema es que los gráficos pueden ser mucho más complicados y se deben prever todos los casos. A través de la deliberación, la codificación, la prueba y el error, al final nació el algoritmo, que ahora funciona en beneficio de los buscadores de ingeniería.



Descripción del texto:

1. Para cada vértice del gráfico, encontramos todos los vértices adyacentes y comenzamos a formar un ciclo moviéndonos hacia cada vértice adyacente por turno.
2. Si el número de vértices adyacentes (excluyendo el que ingresó) = 0, entonces retrocedemos, formando un ciclo ---> elemento 5
3. Si el número de vértices adyacentes (excluyendo el que ingresó) es igual a 1, entonces lo seguimos, formando un ciclo ---> elemento 5
4. ( , ) >=2, ( ), , ---> .5
5. — ? , ---> .2
6. , .
7. , , , .
8. , , ---> .1 ( )
9. Una vez más, pasamos por el ciclo y miramos las ramas de la izquierda. Habiendo encontrado tales sucursales, organizamos una búsqueda en amplitud (o en profundidad, no importa) para cada una. Si al mismo tiempo terminamos en la parte superior del ciclo formado (excepto el actual), entonces interrumpimos la formación del ciclo y vamos a ---> elemento 1
10. Escribimos el ciclo y vamos a buscar uno nuevo ---> elemento 1

Pseudocódigo más grande:





Al principio, se construyeron gráficos cada vez más sofisticados para probar el algoritmo.



o



, al final, se probó en todos los gráficos de exploración reales como este:



no creo que sea óptimo, pero por el momento (ya hace 3 años) funciona sin fallas ni quejas.



No cito el código, casi nadie estará interesado en él, y será difícil sacar una pieza, ya que esta es solo una pequeña parte del trabajo.