Il miglior algoritmo per rilevare i cicli in un grafico diretto

Question

Qual è l'algoritmo più efficiente per rilevare tutti i cicli all'interno di un grafico diretto?

Ho un grafico diretto che rappresenta un programma di lavori che devono essere eseguiti, un lavoro è un nodo e una dipendenza è un vantaggio. Devo rilevare il caso di errore di un ciclo all'interno di questo grafico che porta a dipendenze cicliche.

Answer 1

L'algoritmo dei componenti fortemente connessi di Tarjan ha O (| E | + | V |) complessità temporale.

Per altri algoritmi, vedi Componenti fortemente connessi su Wikipedia.

Answer 2

Dato che si tratta di un programma di lavori, sospetto che ad un certo punto li ordinerai in un ordine di esecuzione proposto.

In tal caso, un'implementazione di ordinamento topologico può in ogni caso rilevare i cicli. Sicuramente UNIX tsort . Penso sia probabile che sia quindi più efficiente rilevare i cicli contemporaneamente allo tsorting, piuttosto che in una fase separata.

Quindi la domanda potrebbe diventare, "come posso eseguire lo tsort in modo più efficiente", piuttosto che "come posso rilevare in modo più efficiente i loop". Per cui la risposta è probabilmente "usa una libreria", ma in mancanza del seguente articolo di Wikipedia:

  

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

ha lo pseudo-codice per un algoritmo e una breve descrizione di un altro da Tarjan. Entrambi hanno O (| V | + | E |) complessità temporale.

Answer 3

Inizia con un DFS: esiste un ciclo se e solo se viene scoperto un back-edge durante DFS . Ciò è dimostrato come risultato della teoria del percorso bianco.

Answer 4

Il modo più semplice per farlo è eseguire una prima traversata in profondità (DFT) del grafico .

Se il grafico presenta n vertici, questo è un algoritmo di complessità temporale O (n) . Poiché probabilmente dovrai fare un DFT a partire da ciascun vertice, la complessità totale diventa O (n ^ 2) .

Devi mantenere uno stack contenente tutti i vertici nel primo attraversamento di profondità corrente , con il suo primo elemento come nodo radice. Se ti imbatti in un elemento che è già nello stack durante il DFT, allora hai un ciclo.

Answer 5

A mio avviso, l'algoritmo più comprensibile per rilevare il ciclo in un grafico diretto è l'algoritmo di colorazione del grafico.

Fondamentalmente, l'algoritmo di colorazione del grafico percorre il grafico in modo DFS (Depth First Search, il che significa che esplora completamente un percorso prima di esplorarne un altro). Quando trova un bordo posteriore, contrassegna il grafico come contenente un ciclo.

Per una spiegazione approfondita dell'algoritmo di colorazione dei grafici, leggi questo articolo: http://www.geeksforgeeks.org/detect-cycle-direct-graph-using-colors/

Fornisco inoltre un'implementazione della colorazione dei grafici in JavaScript https: / /github.com/dexcodeinc/graph_algorithm.js/blob/master/graph_algorithm.js

Answer 6

Se non riesci ad aggiungere un " visitato " proprietà ai nodi, usa un set (o mappa) e aggiungi semplicemente tutti i nodi visitati al set a meno che non siano già nel set. Utilizza una chiave univoca o l'indirizzo degli oggetti come " chiave " ;.

Questo ti dà anche le informazioni su " root " nodo della dipendenza ciclica che tornerà utile quando un utente deve risolvere il problema.

Un'altra soluzione è cercare di trovare la dipendenza successiva da eseguire. Per questo, devi avere un po 'di stack in cui puoi ricordare dove sei ora e cosa devi fare dopo. Controllare se una dipendenza è già in questo stack prima di eseguirla. In tal caso, hai trovato un ciclo.

Anche se questo potrebbe sembrare avere una complessità di O (N * M), devi ricordare che la pila ha una profondità molto limitata (quindi N è piccola) e che M diventa più piccola con ogni dipendenza che puoi spuntare come " ; eseguito " inoltre puoi interrompere la ricerca quando trovi una foglia (quindi non non devi mai controllare tutti i nodi - > M sarà anche piccolo).

In MetaMake, ho creato il grafico come un elenco di elenchi e quindi ho eliminato tutti i nodi mentre li eseguivo, riducendo naturalmente il volume di ricerca. In realtà non ho mai dovuto eseguire un controllo indipendente, è successo automaticamente durante la normale esecuzione.

Se hai bisogno di un " test solo " modalità, basta aggiungere una "quotazione a secco" flag che disabilita l'esecuzione dei lavori effettivi.

Answer 7

Non esiste un algoritmo in grado di trovare tutti i cicli in un grafico diretto in tempo polinomiale. Supponiamo che il grafico diretto abbia n nodi e ogni coppia di nodi abbia connessioni tra loro, il che significa che hai un grafico completo. Quindi qualsiasi sottoinsieme non vuoto di questi n nodi indica un ciclo e ci sono 2 ^ n-1 numero di tali sottogruppi. Quindi non esiste un algoritmo temporale polinomiale.     Supponiamo quindi che tu abbia un algoritmo efficiente (non stupido) che può dirti il ??numero di cicli diretti in un grafico, puoi prima trovare i componenti collegati forti, quindi applicare il tuo algoritmo su questi componenti collegati. Poiché i cicli esistono solo all'interno dei componenti e non tra di essi.

Answer 8

Se DFS trova un bordo che punta a un vertice già visitato, hai un ciclo lì.

Answer 9

Secondo Lemma 22.11 di Cormen et al., Introduzione agli algoritmi (CLRS):

  

Un grafico diretto G è aciclico se e solo se una ricerca in profondità di G non produce bordi posteriori.

Questo è stato menzionato in diverse risposte; qui fornirò anche un esempio di codice basato sul capitolo 22 di CLRS. Il grafico di esempio è illustrato di seguito.

Lo pseudo-codice CLRS per le letture di ricerche approfondite:

Nell'esempio nella Figura 22.4 di CLRS, il grafico è costituito da due alberi DFS: uno costituito da nodi u , v , x , e y e l'altro dei nodi w e z . Ogni albero contiene un bordo posteriore: uno da x a v e un altro da z a z (un loop).

La chiave di realizzazione è che si incontra un bordo posteriore quando, nella funzione DFS-VISIT , mentre si scorre sui vicini v di u , viene rilevato un nodo con il colore GREY .

Il seguente codice Python è un adattamento dello pseudocodice di CLRS con una clausola if che rileva i cicli:

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)

Nota che in questo esempio, il time nello pseudocodice di CLRS non viene acquisito perché siamo interessati solo a rilevare i cicli. Esiste anche un codice di boilerplate per creare la rappresentazione dell'elenco di adiacenza di un grafico da un elenco di spigoli.

Quando viene eseguito, questo script stampa il seguente output:

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

Questi sono esattamente i bordi posteriori nell'esempio in CLRS Figura 22.4.

Answer 10

Il modo in cui lo faccio è fare un ordinamento topologico, contando il numero di vertici visitati. Se quel numero è inferiore al numero totale di vertici nel DAG, hai un ciclo.

Answer 11

Avevo implementato questo problema in sml (programmazione imperativa). Ecco il contorno. Trova tutti i nodi che hanno un livello di errore o un livello inferiore a 0. Tali nodi non possono far parte di un ciclo (quindi rimuoverli). Quindi rimuovere tutti i bordi in entrata o in uscita da tali nodi. Applicare in modo ricorsivo questo processo al grafico risultante. Se alla fine non ti rimane alcun nodo o bordo, il grafico non ha alcun ciclo, altrimenti ha.

Answer 12

https://mathoverflow.net/questions/16393/finding-a-cycle -di-lunghezza fissa Mi piace questa soluzione la migliore specialmente per 4 lunghezze :)

Anche il wizard fisico dice che devi fare O (V ^ 2). Credo che abbiamo bisogno solo di O (V) / O (V + E). Se il grafico è collegato, DFS visiterà tutti i nodi. Se il grafico ha dei sotto-grafici collegati, ogni volta che eseguiamo un DFS su un vertice di questo sotto-grafico troveremo i vertici collegati e non dovremo considerare questi per la prossima corsa del DFS. Pertanto la possibilità di esecuzione per ciascun vertice non è corretta.

Answer 13

Come hai detto, hai una serie di lavori, deve essere eseguito in un certo ordine. Ordinamento topologico dato l'ordine richiesto per la pianificazione dei lavori (o per problemi di dipendenza se si tratta di un grafico aciclico diretto ). Esegui dfs e gestisci un elenco, quindi inizia ad aggiungere un nodo all'inizio dell'elenco e se hai riscontrato un nodo già visitato. Quindi hai trovato un ciclo nel grafico dato.

Answer 14

Se un grafico soddisfa questa proprietà

|e| > |v| - 1

quindi il grafico contiene almeno sul ciclo.