Ukierunkowane znalezienie związku

Rozważ skierowany wykres na którym można dynamicznie dodawać krawędzie i tworzyć określone zapytania.$G$

Przykład: las rozłączny

Rozważ następujący zestaw zapytań:

arrow(u, v)
equiv(u, v)
find(u)

pierwszy dodaje strzałkę do wykresu, drugi decyduje, czy u ↔ ∗ v , ostatni znajduje kanoniczny reprezentant klasy równoważności ↔ ∗ , tj. r ( u ) taki, że u ↔ ∗ v implikuje r ( v ) = r ( u ) .$u→v$$u↔^*v$$↔^*$$r(u)$$u↔^*v$$r(v)=r(u)$

Istnieje dobrze znany algorytm wykorzystujący rozłożoną strukturę danych lasu implementującą te zapytania w quasi-stałej amortyzacji złożoności, a mianowicie . Zauważ, że w tym przypadku jest implementowany za pomocą .$O(α(n))$equivfind

Bardziej złożony wariant

Teraz interesuje mnie bardziej złożony problem, w którym ważne są wskazówki:

arrow(u, v)
confl(u, v)
find(u)

pierwsza dodaje strzałkę , sekundy decydują, czy istnieje węzeł w osiągalny zarówno u, jak i v , tj. u → ∗ ← ∗ v . Ostatni powinien zwrócić obiekt r ( u ) tak, że u → ∗ ← ∗ v implikuje r ( u ) ∙ r ( v ) gdzie ∙ powinno być łatwo obliczalne. (W celu, powiedzmy, obliczeń$u→v$$w$$u$$v$$u→^*←^*v$$r(u)$$u→^*←^*v$$r(u) \bullet r(v)$$\bullet$confl). Celem jest znalezienie dobrej struktury danych, aby operacje te były szybkie.

Cykle

Wykres może zawierać cykle.

Nie wiem, czy istnieje sposób na wydajne i przyrostowe obliczenie silnie połączonych komponentów, aby rozważyć tylko DAG dla głównego problemu.

Oczywiście doceniłbym również rozwiązanie dla DAG. Odpowiadałoby to inkrementalnemu obliczeniu najmniej powszechnego przodka.

Naiwne podejście

Struktura danych lasu rozłącznego nie jest tu pomocna, ponieważ ignoruje kierunek krawędzi. Zauważ, że nie może być pojedynczym węzłem, w przypadku gdy wykres nie jest zbieżny.$r(u)$

Można zdefiniować i zdefiniować ∙ jako S 1 ∙ S 2, gdy S 1 ∩ S 2 ≠ ∅ . Ale jak obliczyć to przyrostowo?$r(u)=\{v ∣ u→^*v\}$$\bullet$$S_1\bullet S_2$$S_1 ∩ S_2≠∅$

Prawdopodobnie obliczenie tak dużego zestawu nie jest przydatne, mniejszy zestaw powinien być bardziej interesujący, jak w zwykłym algorytmie znajdowania związku.

( Edycja : całkowicie przepisałem moją odpowiedź teraz, gdy moje zrozumienie problemu jest (mam nadzieję) jaśniejsze.)

Wygląda na to, że ten problem można sprowadzić do stopniowego konstruowania i poprawiania aproksymacji przejściowego zamknięcia wykresu, gdy wykres jest budowany i przeszukiwany.

$r(u)$$u$$v$$v \ne u$$u, v$$u$$v$$u$$w$$v$$w$

$u$$u$$R(u)$

Nie mam żadnych pomysłów bezceremonialny dla struktury danych, która rejestruje to, że jest bardziej wydajny niż ogólnym przypadku (np nieco wektora lub tabeli mieszania,), ale można zaktualizować te zestawy stopniowo:

$u$$v$$R(u) = R(u) \cup R(v)$

confl$R(u) \cap R(v)$$R(u)$$R(v)$$R(u)$$R(v)$$R$a jeśli znajdziesz wspólny węzeł, ustaw R (u) = R (v) = R (u) \ cup R (v) .

find(u)$R(u)$conflfind$R$$O(\alpha(n))$confl$R$

Brzmi to tak, jakby to był szczególny przypadek metod La Poutré i van Leeuwen utrzymywania przechodniego zamknięcia wykresu .

$R$