DAG - Algorytm zapewniający istnienie pojedynczego źródła i pojedynczego zlewu

Question

Muszę się upewnić, że wykres w naszej aplikacji jest DAG z unikalnym źródłem i unikalnym zlewem.

W szczególności muszę upewnić się, że dla danego węzła początkowego i końcowego (które są znane na początku) każdy węzeł na wykresie leży na ścieżce od węzła początkowego do węzła końcowego.

Mam już implementację algorytmu Tarjana, którego używam do identyfikacji cykli i topologicznego algorytmu sortowania, który mogę uruchomić, gdy algorytm Tarjana wykaże, że wykres jest DAG.

Jaki jest najskuteczniejszy sposób upewnienia się, że wykres spełnia to kryterium?

Answer 1

Jeśli twój wykres jest reprezentowany przez macierz sąsiedztwa, wówczas węzeł x jest węzłem źródłowym, jeśli kolumna x macierzy to 0 i jest węzłem umywalkowym, jeśli wiersz x macierzy wynosi 0. Można uruchomić dwa szybkie przejścia na macierzy, aby policzyć liczbę wierszy i kolumn, które są zerami, aby określić, ile źródeł i pochłaniaczy istnieje i jakie są. Wymaga to czasu O (n) i jest prawdopodobnie najszybszym sposobem, aby to sprawdzić.

Jeśli twój wykres jest reprezentowany przez listę sąsiednich obiektów, możesz znaleźć wszystkie węzły zlewne w czasie O (n), sprawdzając, czy żaden węzeł nie ma krawędzi wychodzących. Możesz znaleźć wszystkie pochłaniacze, utrzymując dla każdego węzła wartość boolowską wskazującą, czy ma ona krawędzie wejściowe, co początkowo jest fałszywe. Następnie można iterować na wszystkich krawędziach listy w czasie O (n + m) zaznaczając wszystkie węzły z przychodzącymi krawędziami. Węzły, które nie zostały oznaczone jako mające krawędzie wejściowe, są źródłami. Ten proces wymaga czasu O (m + n) i ma tak niewielki narzut, że prawdopodobnie jest to jedno z najszybszych podejść.

Mam nadzieję, że to pomoże!

Answer 2

Proste wyszukiwanie według szerokości lub głębi powinno to zaspokoić. Po pierwsze możesz zachować zestaw węzłów, które zawierają węzły tonąć, które widziałeś. Po drugie, możesz zachować zestaw węzłów, które odkryłeś używając BFS/DFS. Następnie wykres zostanie połączony, ponieważ jest jeden podłączony komponent. Zakładając, że używasz jakiegoś przylegania reprezentacji lista styl wykresu, algorytm będzie wyglądać mniej więcej tak:

create an empty queue 
create an empty set to store seen vertices 
create an empty set for sink nodes 

add source node to queue 

while queue is not empty 
    get next vertex from queue, add vertex to seen vertices 
    if num of adjacent nodes == 0 
     add sink nodes to sink node set 
    else 
     for each node in adjacent nodes 
     if node is not in seen vertices 
      add node to queue 

return size of sink nodes == 1 && size of seen vertices == total number in graph 

To będzie liniowy liczby wierzchołków i krawędzi w grafie.

Należy pamiętać, że tak długo, jak znasz początek wierzchołka źródła, zapewni to również właściwość jednego źródła: każdy inny wierzchołek będący źródłem nie zostanie wykryty przez BFS/DFS, a tym samym rozmiar widzianych wierzchołków nie będzie całkowitą liczbą na wykresie.

Answer 3

Jeśli twój algorytm przyjmuje jako dane wejściowe DAG, który jest słabo połączony, załóżmy, że istnieje tylko jeden węzeł s, którego stopień-stopień jest zerowy i tylko jeden węzeł t, którego wynik końcowy wynosi zero, podczas gdy wszystkie inne węzły mają wartość dodatnią in-degree i out-degree, a następnie s może dotrzeć do wszystkich innych węzłów, a wszystkie inne węzły mogą osiągnąć t. W wyniku sprzeczności przyjmijmy, że istnieje węzeł v, którego nie można osiągnąć. Ponieważ żadne węzły nie mogą osiągnąć s, to znaczy v również nie może osiągnąć s. Jako takie, v i s są odłączone, co jest sprzeczne z założeniem. Z drugiej strony, jeśli DAG nie jest słabo podłączony, to zdecydowanie nie spełnia wymagań, które chcesz. Podsumowując, możesz najpierw obliczyć słabo połączony komponent DAG po prostu używając BFS/DFS, pamiętając jednocześnie o liczbie węzłów, których in-degree lub out-degree wynosi zero. Złożoność tego algorytmu to O (| E |).

Answer 4

Po pierwsze, wykonaj DFS na wykresie, zaczynając od węzła źródłowego, który, jak mówisz, jest znany z góry. Jeśli napotkasz tylną krawędź [1], masz cykl i możesz wyjść z błędem.Podczas tego przejścia możesz określić, czy istnieją węzły, których nie można uzyskać ze źródła [2], i podjąć odpowiednie działanie.

Po ustaleniu wykres jest DAG, można zapewnić, że każdy węzeł znajduje się na ścieżce od źródła do zlewu przez innego DFS, począwszy od źródła, co następuje:

bool have_path(source, sink) { 
    if source == sink { 
     source.flag = true 
     return true 
    } 

    // traverse all successor nodes of `source` 
    for dst in succ(source) { 
     if not dst.flag and not have_path(dst, sink) 
      return false // exit as soon as we find a node with no path to `sink` 
    } 
    source.flag = true; 
    return true 
} 

procedura have_path ustawia wartość logiczną flag w każdym węźle, dla którego istnieje pewna ścieżka od tego węzła do zlewu. W tym samym czasie procedura przechodzi tylko przez węzły osiągalne ze źródła i przechodzi przez wszystkie węzły osiągalne ze źródła. Jeśli procedura zwraca wartość true, wszystkie węzły dostępne z źródła znajdują się na ścieżce prowadzącej do zlewu. Nieosiągalne węzły były już obsługiwane w pierwszej fazie.

---

[1] krawędź łączący węzeł o większej liczby DFS węzła przy mniejszej liczbie DFS, że nie jest już całkowicie przetworzony, to znaczy jest nadal DFS stos

[2 ] eg nie będą miały przydzielonego numeru DFS