Najlepszy algorytm do wykrywania cykli na ukierunkowanym wykresie

Jaki jest najskuteczniejszy algorytm wykrywania wszystkich cykli w obrębie ukierunkowanego wykresu?

Mam ukierunkowany wykres przedstawiający harmonogram zadań, które należy wykonać, zadanie jest węzłem, a zależność jest krawędzią. Muszę wykryć przypadek błędu cyklu na tym wykresie, co prowadzi do cyklicznych zależności.

Silnie powiązany algorytm Tarjana ma O(|E| + |V|)złożoność czasową.

Aby zapoznać się z innymi algorytmami, zobacz Silnie połączone komponenty na Wikipedii.

Biorąc pod uwagę, że jest to harmonogram zadań, podejrzewam, że w pewnym momencie zamierzasz je posortować według proponowanej kolejności wykonania.

W takim przypadku implementacja sortowania topologicznego może w każdym przypadku wykryć cykle. UNIX na tsortpewno tak. Myślę, że jest bardziej prawdopodobne, że bardziej efektywne jest wykrywanie cykli w tym samym czasie, co tsortowanie, niż w osobnym kroku.

Zatem pytanie może brzmieć „jak najskuteczniej tsortować”, a nie „jak najskuteczniej wykrywać pętle”. Na którą odpowiedź brzmi prawdopodobnie „użyj biblioteki”, ale w przypadku braku następującego artykułu z Wikipedii:

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

ma pseudo-kod dla jednego algorytmu i krótki opis innego z Tarjan. Oba mają O(|V| + |E|)złożoność czasową.

Najprostszym sposobem na to jest wykonanie pierwszego przejścia na głębokości (DFT) na wykresie .

Jeśli wykres ma nwierzchołki, jest to O(n)algorytm złożoności czasowej. Ponieważ prawdopodobnie będziesz musiał wykonać DFT, zaczynając od każdego wierzchołka, całkowita złożoność staje się O(n^2).

Musisz utrzymać stos zawierający wszystkie wierzchołki na bieżącej głębokości pierwszego przejścia , przy czym pierwszym elementem jest węzeł główny. Jeśli natrafisz na element, który jest już na stosie podczas DFT, to masz cykl.

Według Lemma 22.11 z Cormen i wsp., Wstęp do algorytmów (CLRS):

Kierunkowy wykres G jest acykliczny wtedy i tylko wtedy, gdy przeszukiwanie G w pierwszej głębokości nie daje żadnych tylnych krawędzi.

Zostało to wspomniane w kilku odpowiedziach; tutaj podam również przykład kodu oparty na rozdziale 22 CLRS. Przykładowy wykres pokazano poniżej.

Pseudo-kod CLRS dla pierwszego wyszukiwania w głąb brzmi:

W przykładzie na rysunku 22.4 CLRS wykres składa się z dwóch drzew DFS: jednego składającego się z węzłów u , v , x i y , a drugiego z węzłów w i z . Każde drzewo zawiera jedną tylną krawędź: jedną od x do v, a drugą od z do z (pętla własna).

Realizacja kluczem jest to, że krawędź tylna napotkaniu gdy w DFS-VISITfunkcji podczas iteracji nad sąsiadami vo uwęzeł spotyka się z GRAYkolorem.

Poniższy kod Python jest adaptacją pseudokodu CLRS z ifdodaną klauzulą ​​wykrywającą cykle:

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)

Zauważ, że w tym przykładzie timepseudokod CLRS nie jest przechwytywany, ponieważ jesteśmy zainteresowani jedynie wykrywaniem cykli. Istnieje również pewien kod do zbudowania reprezentacji wykresu sąsiedztwa na podstawie listy krawędzi.

Po uruchomieniu tego skryptu drukuje następujące dane wyjściowe:

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

Są to dokładnie tylne krawędzie w przykładzie na CLRS, rysunek 22.4.

Rozpocznij z DFS: cykl istnieje tylko i tylko wtedy, gdy podczas DFS zostanie wykryty back-edge . Zostało to udowodnione w wyniku teorii białej ścieżki.

Moim zdaniem najbardziej zrozumiałym algorytmem wykrywania cyklu na ukierunkowanym wykresie jest algorytm kolorowania wykresów.

Zasadniczo algorytm kolorowania wykresów prowadzi wykres w systemie DFS (Głębokie pierwsze wyszukiwanie, co oznacza, że ​​bada ścieżkę całkowicie przed eksploracją innej ścieżki). Gdy znajdzie tylną krawędź, oznacza wykres jako zawierający pętlę.

Aby uzyskać szczegółowe wyjaśnienie algorytmu kolorowania wykresów, przeczytaj ten artykuł: http://www.geeksforgeeks.org/detect-cycle-direct-graph-using-colors/

Zapewniam również implementację kolorowania wykresów w JavaScript https://github.com/dexcodeinc/graph_algorithm.js/blob/master/graph_algorithm.js

Jeśli nie możesz dodać właściwości „odwiedzonych” do węzłów, użyj zestawu (lub mapy) i po prostu dodaj wszystkie odwiedzone węzły do ​​zestawu, chyba że są już w zestawie. Użyj unikalnego klucza lub adresu obiektów jako „klucza”.

Daje to również informacje o węźle „root” cyklicznej zależności, który przyda się, gdy użytkownik będzie musiał rozwiązać problem.

Innym rozwiązaniem jest próba znalezienia następnej zależności do wykonania. Aby to zrobić, musisz mieć stos, w którym możesz zapamiętać, gdzie jesteś teraz i co musisz zrobić dalej. Sprawdź, czy zależność jest już na tym stosie, zanim ją wykonasz. Jeśli tak, znalazłeś cykl.

Chociaż może wydawać się, że ma złożoność O (N * M), musisz pamiętać, że stos ma bardzo ograniczoną głębokość (więc N jest mały) i że M staje się mniejszy z każdą zależnością, którą możesz sprawdzić jako „wykonany” plus możesz zatrzymać wyszukiwanie, gdy znajdziesz liść (więc nigdy nie musisz sprawdzać każdego węzła -> M też będzie mały).

W MetaMake utworzyłem wykres jako listę list, a następnie usunąłem każdy węzeł, gdy je wykonałem, co naturalnie zmniejszyło objętość wyszukiwania. W rzeczywistości nigdy nie musiałem przeprowadzać niezależnej kontroli, wszystko działo się automatycznie podczas normalnego wykonywania.

Jeśli potrzebujesz trybu „tylko test”, po prostu dodaj flagę „pracy na sucho”, która wyłącza wykonywanie rzeczywistych zadań.

Nie ma algorytmu, który mógłby znaleźć wszystkie cykle na ukierunkowanym wykresie w czasie wielomianowym. Załóżmy, że skierowany wykres ma n węzłów, a każda para węzłów ma połączenia ze sobą, co oznacza, że ​​masz pełny wykres. Tak więc każdy niepusty podzbiór tych n węzłów wskazuje cykl i istnieje 2 ^ n-1 takich podzbiorów. Dlatego nie istnieje algorytm wielomianowy. Załóżmy więc, że dysponujesz wydajnym (nie głupim) algorytmem, który może określić liczbę ukierunkowanych cykli na wykresie, możesz najpierw znaleźć silnie połączone komponenty, a następnie zastosować swój algorytm na tych połączonych komponentach. Ponieważ cykle istnieją tylko wewnątrz komponentów, a nie między nimi.

Zaimplementowałem ten problem w sml (programowanie imperatywne). Oto zarys. Znajdź wszystkie węzły, które mają stopień niezależny lub stopień zerowy 0. Takie węzły nie mogą być częścią cyklu (więc je usuń). Następnie usuń wszystkie przychodzące lub wychodzące krawędzie z takich węzłów. Rekurencyjnie zastosuj ten proces do wynikowego wykresu. Jeśli na końcu nie pozostanie ci żaden węzeł ani krawędź, wykres nie będzie miał żadnych cykli, w przeciwnym razie ma.

W ten sposób robię Sortowanie topologiczne, licząc liczbę odwiedzonych wierzchołków. Jeśli liczba ta jest mniejsza niż całkowita liczba wierzchołków w DAG, masz cykl.

/mathpro/16393/finding-a-cycle-of-fixed-length Podoba mi się to rozwiązanie najlepiej na 4 długości :)

Również czarodziej mówi, że musisz zrobić O (V ^ 2). Uważam, że potrzebujemy tylko O ​​(V) / O (V + E). Jeśli wykres jest podłączony, DFS odwiedzi wszystkie węzły. Jeśli wykres ma połączone wykresy podrzędne, to za każdym razem, gdy uruchamiamy DFS na wierzchołku tego wykresu podrzędnego, znajdziemy połączone wierzchołki i nie będziemy musieli brać ich pod uwagę przy następnym uruchomieniu DFS. Dlatego możliwość działania dla każdego wierzchołka jest nieprawidłowa.

Jeśli DFS znajdzie krawędź, która wskazuje na już odwiedzony wierzchołek, masz tam cykl.

Jak powiedziałeś, masz zestaw zadań, które należy wykonać w określonej kolejności. Topological sortbiorąc pod uwagę wymaganą kolejność planowania zadań (lub problemów z zależnościami, jeśli jest to a direct acyclic graph). Uruchom dfsi utrzymuj listę i zacznij dodawać węzeł na początku listy, a jeśli napotkasz węzeł, który jest już odwiedzany. Następnie znalazłeś cykl na danym wykresie.

Jeśli wykres spełnia tę właściwość

|e| > |v| - 1

wtedy wykres zawiera przynajmniej cykl.