Rozważ skierowany wykres na którym można dynamicznie dodawać krawędzie i tworzyć określone zapytania.
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 ) .
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ą .equiv
find
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ń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.
Można zdefiniować i zdefiniować ∙ jako S 1 ∙ S 2, gdy S 1 ∩ S 2 ≠ ∅ . Ale jak obliczyć to przyrostowo?
Prawdopodobnie obliczenie tak dużego zestawu nie jest przydatne, mniejszy zestaw powinien być bardziej interesujący, jak w zwykłym algorytmie znajdowania związku.
confl(u,v)
find
find
find