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

Question

¿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.

Answer 1

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

Para otros algoritmos, consulte Componentes fuertemente conectados en Wikipedia.

Answer 2

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, entonces una ordenació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 la clasificación, en lugar de en un paso separado.

Entonces, la pregunta podría ser: "¿Cómo hago una clasificación más eficiente?", en lugar de "¿Cómo puedo detectar los bucles de manera más eficiente?". 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.

Answer 3

Comience con un DFS: existe un ciclo si y solo si se descubre un back-edge durante DFS . Esto se demuestra como resultado del teorio del camino blanco.

Answer 4

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

Si el gráfico tiene vértices n , este es un algoritmo de complejidad de tiempo O (n) . Como posiblemente tendrá que hacer un DFT a partir de cada vértice, la complejidad total se convierte en 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.

Answer 5

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 manera DFS (Profund First Search, lo que significa que explora una ruta por completo 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

Answer 6

Si no puede agregar un " visitado " propiedad de 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. Utilice una clave única o la dirección de los objetos como la " clave " ;.

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

Otra solución es intentar encontrar la siguiente dependencia para ejecutar. Para esto, debe tener una pila donde pueda recordar dónde se encuentra ahora y lo que 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 " ; ejecutado " además, puede detener la búsqueda cuando encuentre una hoja (por lo que nunca tendrá 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. Nunca tuve que ejecutar una verificación independiente, todo sucedió automáticamente durante la ejecución normal.

Si necesita una "prueba solamente" modo, simplemente agregue un " ejecución en seco " bandera que inhabilita la ejecución de los trabajos reales.

Answer 7

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. Por lo tanto, cualquier subconjunto no vacío de estos n nodos indica un ciclo y hay 2 ^ n-1 número de dichos 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 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.

Answer 8

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

Answer 9

Según 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 profunda 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.

Pseudocódigo de CLRS para lecturas de búsqueda de profundidad primero:

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

La realización clave es que se encuentra un borde posterior cuando, en la función DFS-VISIT , mientras itera sobre los vecinos v de u , se encuentra un nodo con el color GREY .

El siguiente código de Python es una adaptación del pseudocódigo de CLRS con una cláusula if 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 discovered and 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 tiempo en el pseudocódigo de 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 traseros en el ejemplo en CLRS Figura 22.4.

Answer 10

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.

Answer 11

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, sí.

Answer 12

https://mathoverflow.net/questions/16393/finding-a-cycle -of-fixed-length Me gusta esta solución 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.

Answer 13

Como dijiste, tienes un conjunto de trabajos, debe ejecutarse en cierto orden. Clasificación topológica dado el orden requerido para la programación de trabajos (o para problemas de dependencia si se trata de un gráfico acíclico directo ). Ejecute dfs y 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.

Answer 14

Si un gráfico satisface esta propiedad

|e| > |v| - 1

entonces el gráfico contiene al menos el ciclo.