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 una programación de trabajos que deben ejecutarse, un trabajo es un nodo y una dependencia es un borde. Necesito detectar el caso de error de un ciclo dentro de este gráfico que conduce a dependencias cíclicas.

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

Para otros algoritmos, vea Componentes fuertemente conectados en Wikipedia.

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

Si ese es el caso, una implementación de ordenamiento topológico en cualquier caso puede detectar ciclos. UNIX tsortciertamente lo hace. Creo que es probable que, por lo tanto, sea más eficiente detectar ciclos al mismo tiempo que la clasificación, en lugar de en un paso separado.

Por lo tanto, la pregunta podría ser: "¿Cómo hago una clasificación más eficiente", en lugar de "¿Cómo detecto los bucles más eficientemente?". Para lo cual la respuesta es probablemente "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.

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

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

Debe mantener una pila 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 pila durante el DFT, entonces tienes un ciclo.

De acuerdo con el Lema 22.11 de Cormen et al., Introducción a los algoritmos (CLRS):

Un gráfico dirigido G es acíclico si y solo si una búsqueda en profundidad de G no produce bordes posteriores.

Esto ha sido mencionado en varias respuestas; Aquí también proporcionaré un ejemplo de código basado en el capítulo 22 de CLRS. El gráfico de ejemplo se ilustra a continuación.

El seudocódigo de CLRS para lecturas de búsqueda en profundidad primero:

En el ejemplo de la Figura 22.4 de CLRS, el gráfico consta de dos árboles DFS: uno formado por los nodos u , v , x e y , y el otro por los nodos w y z . Cada árbol contiene un borde posterior: uno de x a v y otro de z a z (un bucle automático).

La comprensión clave es que se encuentra un borde posterior cuando, en la DFS-VISITfunción, al iterar sobre los vecinos vde u, se encuentra un nodo con el GRAYcolor.

El siguiente código de Python es una adaptación del pseudocódigo de CLRS con una ifcláusula agregada que detecta ciclos:

import collections


class Graph(object):
    def __init__(self, edges):
        self.edges = edges
        self.adj = Graph._build_adjacency_list(edges)

    @staticmethod
    def _build_adjacency_list(edges):
        adj = collections.defaultdict(list)
        for edge in edges:
            adj[edge[0]].append(edge[1])
        return adj


def dfs(G):
    discovered = set()
    finished = set()

    for u in G.adj:
        if u not in discovered and u not in finished:
            discovered, finished = dfs_visit(G, u, discovered, finished)


def dfs_visit(G, u, discovered, finished):
    discovered.add(u)

    for v in G.adj[u]:
        # Detect cycles
        if v in discovered:
            print(f"Cycle detected: found a back edge from {u} to {v}.")

        # Recurse into DFS tree
        if v not in finished:
            dfs_visit(G, v, discovered, finished)

    discovered.remove(u)
    finished.add(u)

    return discovered, finished


if __name__ == "__main__":
    G = Graph([
        ('u', 'v'),
        ('u', 'x'),
        ('v', 'y'),
        ('w', 'y'),
        ('w', 'z'),
        ('x', 'v'),
        ('y', 'x'),
        ('z', 'z')])

    dfs(G)

Tenga en cuenta que en este ejemplo, el timepseudocódigo en CLRS no se captura porque solo estamos interesados ​​en detectar ciclos. También hay un código repetitivo para construir la representación de la lista de adyacencia de un gráfico a partir de una lista de bordes.

Cuando se ejecuta este script, imprime el siguiente resultado:

Cycle detected: found a back edge from x to v.
Cycle detected: found a back edge from z to z.

Estos son exactamente los bordes posteriores en el ejemplo en CLRS Figura 22.4.

Comience con un DFS: existe un ciclo si y solo si se descubre un back-edge durante DFS . Esto se demuestra como resultado del teorum de trayectoria blanca.

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

Básicamente, el algoritmo de coloración del gráfico recorre el gráfico de una manera DFS (Profund First Search, lo que significa que explora una ruta completamente antes de explorar otra ruta). Cuando encuentra un borde posterior, marca el gráfico como que contiene un bucle.

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

Además, proporciono una implementación de coloración 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 "clave".

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

Otra solución es tratar de encontrar la siguiente dependencia para ejecutar. Para esto, debe tener una pila donde pueda recordar dónde se encuentra ahora y qué debe hacer a continuación. Compruebe si ya hay una dependencia en esta pila antes de ejecutarla. Si es así, has encontrado un ciclo.

Si bien esto puede parecer que tiene una complejidad de O (N * M), debe recordar que la pila 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 eliminé cada nodo a medida que los ejecutaba, lo que naturalmente redujo el volumen de búsqueda. En realidad, 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 "ejecución en seco" que deshabilita la ejecución de los trabajos reales.

No existe un algoritmo que pueda encontrar todos los ciclos en un gráfico dirigido en tiempo polinómico. 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 tales subconjuntos. Por lo tanto, no existe un algoritmo de tiempo polinómico. Supongamos que tiene un algoritmo eficiente (no estúpido) que le puede decir la cantidad 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 (programación imperativa). Aquí está el bosquejo. Encuentre todos los nodos que tengan un grado de entrada o salida de 0. Tales nodos no pueden ser parte de un ciclo (así que elimínelos). Luego, elimine todos los bordes entrantes o salientes de dichos nodos. Aplicar recursivamente este proceso al gráfico resultante. Si al final no le queda ningún nodo o borde, el gráfico no tiene ningún ciclo, de lo contrario lo tiene.

La forma en que lo hago es hacer un ordenamiento topológico, 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.

/mathpro/16393/finding-a-cycle-of-fixed-length Me gusta esta solución, la mejor especialmente para 4 longitudes :)

También el asistente físico 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 gráficos secundarios conectados, cada vez que ejecutamos 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.

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

Como dijiste, tienes un conjunto de trabajos, debe ejecutarse en cierto orden. Topological sortdado el pedido requerido para la programación de trabajos (o para problemas de dependencia si es a direct acyclic graph). Ejecute dfsy mantenga una lista, y comience a agregar un nodo al comienzo de la lista, y si encontró un nodo que ya ha sido 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 el ciclo.