Wydajny sposób rekurencyjnie obliczyć drzewo Dominator?

Question

Używam algorytmu Lengauera i Tarjana z kompresją ścieżek do obliczenia drzewa dominującego dla wykresu, na którym są miliony węzłów. Algorytm jest dość skomplikowany i muszę przyznać, że nie poświęciłem czasu, aby go w pełni zrozumieć, po prostu go używam. Teraz potrzebuję obliczyć drzewa dominujące bezpośrednich potomków węzła głównego i ewentualnie powrócić na dół wykresu do pewnej głębokości powtarzającej tę operację. To znaczy. kiedy obliczam drzewo dominujące dla potomka węzła głównego, chcę udawać, że węzeł główny został usunięty z wykresu.

Moje pytanie brzmi: czy istnieje skuteczne rozwiązanie tego problemu, które wykorzystuje natychmiastowe informacje o dominatorze, które zostały już obliczone w drzewie początkowego dominatora dla węzła głównego? Innymi słowy, nie chcę zaczynać od zera dla każdego z dzieci, ponieważ cały proces jest dość czasochłonny.

Naiwnie wydaje się, że jest to możliwe, ponieważ na wykresie będzie dużo węzłów w głąb wykresu, których idomy znajdują się nieco wyżej i nie są dotknięte zmianami na górze wykresu.

BŁĘDY na bok: to dziwne, że temat drzew dominujących jest "własnością" kompilatorów i nie ma o tym wzmianki w książkach o klasycznej teorii grafów. Aplikacja, dla której go używam - mój analizator sterty java FindRoots - nie jest związana z teorią kompilatora.

Wyjaśnienie: Mówię tu o ukierunkowanych wykresach. "Korzeń", o którym mówię, jest faktycznie węzłem o największej osiągalności. Zaktualizowałem powyższy tekst, zastępując odniesienia do "drzewa" za pomocą "wykresu". Mam tendencję do myślenia o nich jako o drzewach, ponieważ ich kształt jest bardzo podobny do drzewa. Wykres jest faktycznie obiektami w stosie java i jak można sobie wyobrazić, jest rozsądnie hierarchiczny. Znalazłem drzewo dominujące przydatne przy analizie przecieków OOM, ponieważ to, co cię interesuje, to "co utrzymuje ten przedmiot przy życiu?" a odpowiedź ostatecznie jest jego dominatorem. Drzewa Dominatora pozwalają ci zobaczyć drzewa, a nie drzewa. Ale czasami mnóstwo śmieci unosi się na szczycie drzewa, więc masz korzeń z tysiącami dzieci bezpośrednio pod nim. W takich przypadkach chciałbym poeksperymentować z obliczaniem drzew dominujących zakorzenionych w każdym z bezpośrednich dzieci (na oryginalnym wykresie) z korzenia, a następnie może przejść do następnego poziomu w dół i tak dalej. (Próbuję nie martwić się o możliwość odsyłaczy wstecznych :)

Answer 1

boost::lengauer_tarjan_dominator_tree_without_dfs może pomóc.

Answer 2

Sądząc z braku komentarzy, nie ma wielu ludzi na Stackoverflow z doświadczeniem relevent, aby ci pomóc. Jestem jedną z tych osób, ale nie chcę, aby takie interesujące pytanie padło z tępym łomotem, więc spróbuję pomóc.

Moja pierwsza myśl jest taka, że ​​jeśli ten wykres jest generowany przez inne kompilatory, czy warto przyjrzeć się kompilatorowi o otwartym kodzie źródłowym, takim jak GCC, aby zobaczyć, jak rozwiązuje ten problem?

Moja druga myśl jest taka, że ​​głównym punktem twojego pytania wydaje się być unikanie ponownego przeliczania wyniku dla głównego drzewa.

Co mogę zrobić, to utworzyć wrapper wokół każdego węzła, który zawiera sam węzeł i wszelkie wstępnie obliczone dane powiązane z tym węzłem. Nowe drzewo zostanie wtedy zrekonstruowane ze starego drzewa rekurencyjnie za pomocą tych klas opakowania. Podczas konstruowania tego drzewa zaczniesz od korzenia i wybierzesz drogę do węzłów liści. Dla każdego węzła można zapisać wynik obliczeń dla wszystkich dotychczasowych przodków. W ten sposób, będziesz musiał tylko spojrzeć na węzeł nadrzędny i bieżące dane węzła, które przetwarzasz, aby obliczyć wartość dla twojego nowego węzła.

Mam nadzieję, że to pomoże!

Answer 3

Czy możesz opracować, na jakim wykresie zaczynasz? Nie widzę różnicy między wykresem drzewa, a drzewem dominującym tego wykresu. Rodzic każdego węzła powinien być jego idomem i oczywiście będzie on zdominowany przez wszystko, co znajduje się powyżej w drzewie.

Answer 4

Nie w pełni rozumiem twoje pytanie, ale wydaje mi się, że chcesz mieć jakąś dodatkową funkcję aktualizacji. Dowiedziałem się już kiedyś, jakie są ich algorytmy, ale wydawało mi się, że nie ma znanego sposobu, aby duże wykresy zrobiły to szybko (przynajmniej z teoretycznego punktu widzenia).

Możesz po prostu wyszukać "drzewo przyrostowych aktualizacji", aby znaleźć odniesienia.

Chyba jesteś świadomy the Eclipse Memory Analyzer nie używać drzew dominator, więc ten temat nie jest całkowicie „własnością” społeczności kompilator już :)