¿Cuál es el algoritmo más eficiente para detectar todos los ciclos de un grafo dirigido?
Tengo un grafo dirigido que representa un programa de trabajos que deben ser ejecutados, siendo un trabajo un nodo y una dependencia una arista. Necesito detectar el caso de error de un ciclo dentro de este grafo que conlleva dependencias cíclicas.
El algoritmo de componentes fuertemente conectados de Tarjan's tiene una complejidad de tiempo O(|E| + |V|)
.
Para otros algoritmos, véase Strongly connected components en Wikipedia.
Dado que se trata de una programación de trabajos, sospecho que en algún momento vas a ordenarlos en un orden de ejecución propuesto.
Si ese es el caso, entonces una implementación de ordenación topológica puede en cualquier caso detectar ciclos. UNIX tsort
ciertamente lo hace. Creo que es probable que sea más eficiente detectar los ciclos al mismo tiempo que la ordenación, en lugar de hacerlo en un paso separado.
Así que la pregunta podría ser, "cómo puedo tsort más eficiente", en lugar de "cómo puedo detectar más eficientemente los bucles". A lo que la respuesta es probablemente "utilizar una biblioteca", pero en su defecto el siguiente artículo de Wikipedia:
tiene el pseudocódigo de un algoritmo, y una breve descripción de otro de Tarjan. Ambos tienen una complejidad de tiempo O(|V| + |E|)
.
Si no puede añadir una propiedad "visitada" a los nodos, utilice un conjunto (o mapa) y simplemente añada todos los nodos visitados al conjunto, a menos que ya estén en él. Utilice una clave única o la dirección de los objetos como "clave".
Esto también le da la información sobre el nodo "raíz" de la dependencia cíclica que será útil cuando un usuario tiene que arreglar el problema.
Otra solución es tratar de encontrar la siguiente dependencia a ejecutar. Para ello, debe tener alguna pila en la que pueda recordar dónde se encuentra ahora y qué debe hacer a continuación. Comprueba si una dependencia ya está en esta pila antes de ejecutarla. Si lo está, has encontrado un ciclo.
Aunque esto pueda parecer que tiene una complejidad de O(N*M) debes recordar que la pila tiene una profundidad muy limitada (por lo que N es pequeño) y que M se hace más pequeño con cada dependencia que puedes marcar como "ejecutada" además puedes detener la búsqueda cuando encuentres una hoja (por lo que nunca tienes que comprobar cada nodo -> M también será pequeño).
En MetaMake, creé el gráfico como una lista de listas y luego eliminé cada nodo a medida que los ejecutaba, lo que naturalmente redujo el volumen de búsqueda. En realidad nunca tuve que ejecutar una comprobación independiente, todo ocurrió automáticamente durante la ejecución normal.
Si usted necesita un "test only" modo, sólo tiene que añadir un "dry-run" bandera que desactiva la ejecución de los trabajos reales.