El mejor algoritmo para detectar ciclos en un gráfico dirigido

¿Cuál es el algoritmo más eficiente para detectar todos los ciclos dentro de un gráfico dirigido?

Tengo un gráfico dirigido que representa un cronogtwig de trabajos que deben ejecutarse, un trabajo es un nodo y una dependencia es una ventaja. Necesito detectar el caso de error de un ciclo dentro de este gráfico que conduce a dependencias cíclicas.

El algoritmo de los componentes fuertemente conectados de Tarjan tiene una complejidad de tiempo O(|E| + |V|) .

Para otros algoritmos, vea Componentes fuertemente conectados en Wikipedia.

Dado que este es un cronogtwig de trabajos, sospecho que en algún momento los clasificará en una orden de ejecución propuesta.

Si ese es el caso, entonces una implementación de clasificación topológica puede en cualquier caso detectar ciclos. UNIX tsort ciertamente lo hace. Creo que es probable que, por lo tanto, sea más eficiente detectar ciclos al mismo tiempo que el tsorting, en lugar de hacerlo en un paso separado.

Por lo tanto, la pregunta podría ser: “¿Cómo puedo hacer una transición más eficiente?”, En lugar de “¿cómo puedo detectar loops de manera más eficiente?”. A lo que la respuesta probablemente sea “usar una biblioteca”, pero en su defecto el siguiente artículo de Wikipedia:

http://en.wikipedia.org/wiki/Topological_sorting

tiene el pseudocódigo para un algoritmo y una breve descripción de otro de Tarjan. Ambos tienen O(|V| + |E|) complejidad de tiempo.

Comience con un DFS: existe un ciclo si y solo si se descubre un borde posterior durante el DFS . Esto se prueba como resultado del teorum de camino blanco.

La forma más sencilla de hacerlo es hacer un primer recorrido de profundidad (DFT) del gráfico .

Si el gráfico tiene n vértices, este es un algoritmo de complejidad de tiempo O(n) . Como posiblemente tendrá que hacer una DFT comenzando desde cada vértice, la complejidad total se vuelve O(n^2) .

Debe mantener una stack que contenga todos los vértices en el primer recorrido de profundidad actual , siendo su primer elemento el nodo raíz. Si te encuentras con un elemento que ya está en la stack durante el DFT, entonces tienes un ciclo.

En mi opinión, el algoritmo más comprensible para detectar ciclos en un gráfico dirigido es el algoritmo de coloreado de gráficos.

Básicamente, el algoritmo de coloreado de gráficos recorre el gráfico de una manera DFS (Profundidad de la primera búsqueda, lo que significa que explora un camino completamente antes de explorar otra ruta). Cuando encuentra un borde posterior, marca el gráfico como que contiene un bucle.

Para una explicación detallada del algoritmo de coloreado de gráficos, lea este artículo: http://www.geeksforgeeks.org/detect-cycle-direct-graph-using-colors/

Además, proporciono una implementación de coloreado de gráficos en JavaScript https://github.com/dexcodeinc/graph_algorithm.js/blob/master/graph_algorithm.js

Si no puede agregar una propiedad “visitada” a los nodos, use un conjunto (o mapa) y simplemente agregue todos los nodos visitados al conjunto a menos que ya estén en el conjunto. Use una clave única o la dirección de los objetos como la “clave”.

Esto también le brinda la información sobre el nodo “raíz” de la dependencia cíclica que será útil cuando el usuario tenga que solucionar el problema.

Otra solución es tratar de encontrar la siguiente dependencia para ejecutar. Para esto, debes tener algo de stack donde puedas recordar dónde estás ahora y qué debes hacer a continuación. Compruebe si una dependencia ya está en esta stack antes de ejecutarla. Si es así, has encontrado un ciclo.

Si bien esto puede parecer una complejidad de O (N * M), debe recordar que la stack tiene una profundidad muy limitada (por lo que N es pequeña) y que M se vuelve más pequeña con cada dependencia que puede marcar como “ejecutada” más puede detener la búsqueda cuando encuentre una hoja (para que nunca tenga que verificar cada nodo -> M también será pequeño).

En MetaMake, creé el gráfico como una lista de listas y luego borré todos los nodos cuando los ejecuté, lo que naturalmente reduce el volumen de búsqueda. Nunca tuve que ejecutar una verificación independiente, todo sucedió automáticamente durante la ejecución normal.

Si necesita un modo de “solo prueba”, simplemente agregue un indicador de “marcha en seco” que inhabilita la ejecución de los trabajos reales.

No hay ningún algoritmo que pueda encontrar todos los ciclos en un gráfico dirigido en tiempo polinomial. Supongamos que el gráfico dirigido tiene n nodos y cada par de nodos tiene conexiones entre sí, lo que significa que tiene un gráfico completo. Entonces, cualquier subconjunto no vacío de estos n nodos indica un ciclo y hay 2 ^ n-1 número de dichos subconjuntos. Entonces, no existe un algoritmo de tiempo polinomial. Supongamos que tiene un algoritmo eficiente (no estúpido) que le puede indicar el número de ciclos dirigidos en un gráfico, primero puede encontrar los componentes conectados fuertes, y luego aplicar su algoritmo en estos componentes conectados. Dado que los ciclos solo existen dentro de los componentes y no entre ellos.

Había implementado este problema en sml (progtwigción imperativa). Aquí está el esquema. Encuentra todos los nodos que tienen un grado de indegree o de 0. Dichos nodos no pueden ser parte de un ciclo (entonces quítelos). A continuación, elimine todos los bordes entrantes o salientes de dichos nodos. Aplica de forma recursiva este proceso al gráfico resultante. Si al final no te queda ningún nodo o borde, el gráfico no tiene ningún ciclo, de lo contrario lo ha hecho.

Si DFS encuentra un borde que apunta a un vértice ya visitado, tiene un ciclo allí.

https://mathoverflow.net/questions/16393/finding-a-cycle-of-fixed-length Me gusta esta solución, la mejor especialmente para 4 longitudes 🙂

También Phys Wizard dice que tienes que hacer O (V ^ 2). Creo que solo necesitamos O (V) / O (V + E). Si el gráfico está conectado, DFS visitará todos los nodos. Si el gráfico tiene subgraficos conectados, cada vez que ejecutemos un DFS en un vértice de este gráfico secundario, encontraremos los vértices conectados y no tendremos que considerarlos para la próxima ejecución del DFS. Por lo tanto, la posibilidad de ejecutar para cada vértice es incorrecta.

La forma en que lo hago es hacer una clasificación topológica, contando el número de vértices visitados. Si ese número es menor que el número total de vértices en el DAG, tiene un ciclo.

Como dijo, tiene un conjunto de trabajos, debe ejecutarse en cierto orden. Topological sort dado que se requiere un orden para la progtwigción de trabajos (o para problemas de dependencia si se trata de un direct acyclic graph ). Ejecute dfs y mantenga una lista, y comience a agregar un nodo al principio de la lista, y si encontró un nodo que ya está visitado. Luego encontraste un ciclo en un gráfico dado.

Si un gráfico satisface esta propiedad

 |e| > |v| - 1 

entonces el gráfico contiene al menos en ciclo.