Najlepszy algorytm do wykrywania cykli w grafie kierowanym [zamknięty]

Biorąc pod uwagę, że jest to harmonogram prac, podejrzewam, że w pewnym momencie zamierzasz posortować je w proponowaną kolejność wykonania.

Jeśli tak jest, to sortowanie topologiczne wdrożenie może w każdym przypadku wykryć cykle. UNIX tsort z pewnością tak. Myślę, że jest prawdopodobne, że jest to bardziej efektywne wykrywanie cykli w tym samym czasie co tsorting, a nie w oddzielnym kroku.

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

Zgodnie z Lematem 22.11 z Cormen et al., Wprowadzenie do algorytmów (CLRS):

Graf skierowany G jest acykliczny wtedy i tylko wtedy, gdy głębsze wyszukiwanie G nie daje 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 przedstawiono poniżej.

Pseudo-kod CLRS do wyszukiwania głębi odsłon:

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

Kluczem jest to, że tylna krawędź napotyka się, gdy w DFS-VISIT funkcja, podczas iteracji nad sąsiadami v z u, napotkany jest węzeł z kolorem GRAY.

Poniższy kod Pythona jest adaptacją pseudokodu CLRS z dodaną klauzulą if, która wykrywa 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, time w pseudokodzie CLRS nie jest przechwytywany, ponieważ interesuje nas tylko wykrywanie cykli. Jest też jakiś kod boilerplate do budowania reprezentacji listy adjacency grafu z listy krawędzie.

Gdy skrypt jest wykonywany, wypisuje następujące wyjście:

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

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

Najprostszym sposobem, aby to zrobić jest zrobić głębokość pierwszy Trawers (DFT) grafu .

Jeśli Wykres ma wierzchołki n, jest to algorytm złożoności czasu O(n). 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 utrzymywać stos zawierający wszystkie wierzchołki w bieżącej głębokości pierwszego przejścia, a jego pierwszym elementem jest węzeł główny. Jeśli natkniesz się na element, który jest już w stos podczas DFT, a następnie masz cykl.

Moim zdaniem najbardziej zrozumiałym algorytmem wykrywania cyklu w grafie skierowanym jest algorytm Graf-kolorowanie -.

Zasadniczo, algorytm kolorowania grafu porusza się po grafie w sposób DFS (najpierw Wyszukiwanie głębokości, co oznacza, że bada ścieżkę całkowicie przed zbadaniem innej ścieżki). Gdy znajdzie tylną krawędź, zaznacza 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/

Ponadto dostarczam implementację kolorowania Wykresów w JavaScript https://github.com/dexcodeinc/graph_algorithm.js/blob/master/graph_algorithm.js

Zacznij od DFS: cykl istnieje wtedy i tylko wtedy, gdy podczas DFS odkryto tylną krawędź . Jest to udowodnione w wyniku teorii białej ścieżki.

Jeśli nie możesz dodać właściwości "odwiedzone" 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óre przydadzą się, gdy użytkownik będzie musiał rozwiązać problem.

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

Chociaż może to wydawać się mieć złożoność O (N*M), musisz pamiętać, że stos ma bardzo ograniczoną głębokość (więc N jest małe) i że M staje się mniejszy z każdą zależnością, którą możesz odpisać jako "wykonaną", plus możesz zatrzymać wyszukiwanie, gdy znajdziesz liść (więc nigdy musisz sprawdzać każdy węzeł -> m będzie się zmniejszać Małe też).

W MetaMake stworzyłem wykres jako listę list, a następnie usunąłem każdy węzeł podczas ich wykonywania, co naturalnie zmniejszyło wolumen wyszukiwania. Nigdy nie musiałem uruchamiać niezależnej kontroli, wszystko działo się automatycznie podczas normalnego wykonywania.

Jeśli potrzebujesz trybu "tylko test", po prostu dodaj flagę "dry-run", która wyłącza wykonywanie rzeczywistych zadań.

Nie ma algorytmu, który mógłby znaleźć wszystkie cykle w grafie skierowanym w czasie wielomianowym. Załóżmy, że wykres skierowany ma n węzłów i Każda para węzłów ma połączenia ze sobą, co oznacza, że masz kompletny Wykres. Tak więc każdy niepusty podzbiór tych n węzłów oznacza cykl i istnieje 2^N-1 liczba takich podzbiorów. Nie istnieje więc żaden wielomianowy algorytm czasu. Załóżmy więc, że masz wydajny (nie głupi) algorytm, który może powiedzieć ci liczbę kierowanych cykli w Wykres, możesz najpierw znaleźć silne 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 (imperative programming) . Oto zarys . Znajdź wszystkie węzły, które mają wartość indegree lub outegree równą 0 . Takie węzły nie mogą być częścią cyklu ( więc usuń je). Następnie usuń wszystkie przychodzące lub wychodzące krawędzie z takich węzłów. Rekurencyjnie zastosuj ten proces do wykresu wynikowego. Jeśli na końcu nie zostanie żaden węzeł lub krawędź , Wykres nie ma żadnych cykli, w przeciwnym razie ma.

Sposób, w jaki to robię, polega na sortowaniu topologicznym, liczeniu liczby odwiedzonych wierzchołków. Jeśli liczba ta jest mniejsza niż całkowita liczba wierzchołków w DAG, masz cykl.

Https://mathoverflow.net/questions/16393/finding-a-cycle-of-fixed-length najbardziej podoba mi się to rozwiązanie specjalnie na 4 długość:)

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

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 muszą być wykonane w określonej kolejności. Topological sort podano Ci wymaganą kolejność planowania zadań(lub problemów z zależnościami, jeśli jest to direct acyclic graph). Uruchom dfs i utrzymaj listę, i zacznij dodawać węzeł na początku listy, a jeśli napotkasz węzeł, który jest już odwiedzony. Następnie znalazłeś cykl na danym wykresie.

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

|e| > |v| - 1

Wtedy wykres zawiera co najmniej cykl.