Ich verwende den Lengauer- und Tarjan-Algorithmus mit Pfadkomprimierung, um den Dominatorbaum für ein Diagramm mit Millionen von Knoten zu berechnen. Der Algorithmus ist ziemlich komplex und ich muss zugeben, dass ich mir nicht die Zeit genommen habe, ihn vollständig zu verstehen. Ich benutze ihn nur. Jetzt muss ich die Dominatorbäume der direkten untergeordneten Knoten des Wurzelknotens berechnen und den Graphen möglicherweise bis zu einer bestimmten Tiefe rekonstruieren, um diese Operation zu wiederholen. Das heißt Wenn ich den Dominatorbaum für ein untergeordnetes Element des Stammknotens berechne, möchte ich so tun, als wäre der Stammknoten aus dem Diagramm entfernt worden.

Meine Frage ist, ob es eine effiziente Lösung dafür gibt, die unmittelbare Dominatorinformationen verwendet, die bereits im anfänglichen Dominatorbaum für den Wurzelknoten berechnet wurden. Mit anderen Worten, ich möchte nicht für jedes der Kinder bei Null anfangen, da der gesamte Prozess ziemlich zeitaufwändig ist.

Naiv gesehen scheint es möglich zu sein, da es in der Tiefe des Graphen viele Knoten gibt, über denen sich nur ein kleines Stück Idoms befinden und die von Änderungen am oberen Rand des Graphen nicht betroffen sind.

Übrigens, es ist bizarr, dass das Thema der Dominatorbäume von Compilern "besessen" wird und in Büchern zur klassischen Graphentheorie nicht erwähnt wird. Die Anwendung, für die ich sie verwende - mein FindRoots Java Heap Analyzer - ist nicht mit der Compilertheorie verwandt.

Klarstellung: Ich spreche hier von gerichteten Graphen. Die "Wurzel", auf die ich mich beziehe, ist tatsächlich der Knoten mit der größten Erreichbarkeit. Ich habe den obigen Text aktualisiert und Verweise auf "Baum" durch "Grafik" ersetzt. Ich neige dazu, sie als Bäume zu betrachten, weil die Form so isthauptsächlich baumartig. Die Grafik zeigt die Objekte in einem Java-Heap und ist, wie Sie sich vorstellen können, einigermaßen hierarchisch. Ich habe festgestellt, dass der Dominator-Baum bei der OOM-Leckanalyse nützlich ist, da Sie sich für die Frage interessieren, was dieses Objekt am Leben erhält. und die Antwort ist letztendlich sein Dominator. Mit Dominator-Bäumen können Sie <ahem> den Wald und nicht die Bäume sehen. Aber manchmal schwimmt viel Müll oben auf dem Baum, sodass Sie eine Wurzel mit Tausenden von Kindern direkt darunter haben. In solchen Fällen möchte ich mit der Berechnung der Dominatorbäume experimentieren, die bei jedem der direkten Kinder (im Originaldiagramm) der Wurzel verwurzelt sind, und dann vielleicht zur nächsten Ebene nach unten gehen und so weiter. (Ich versuche, mir vorerst keine Sorgen über die Möglichkeit von Backlinks zu machen :)