有效的方式来递归地计算支配树？ [英] Efficient way to recursively calculate dominator tree?
问题描述
我使用的是Lengauer和的Tarjan算法路径COM pression计算支配树的图，其中有以百万计的节点。该算法是相当复杂的，我有，我只是用它来承认我没有花时间去完全理解。现在我有一个需要计算的根节点的直接子支配树，并可能向下递归图到一定深度重复此操作。即当我计算支配树的根节点的一个孩子，我想pretend根节点已经从图表中删除。
I'm using the Lengauer and Tarjan algorithm with path compression to calculate the dominator tree for a graph where there are millions of nodes. The algorithm is quite complex and I have to admit I haven't taken the time to fully understand it, I'm just using it. Now I have a need to calculate the dominator trees of the direct children of the root node and possibly recurse down the graph to a certain depth repeating this operation. I.e. when I calculate the dominator tree for a child of the root node I want to pretend that the root node has been removed from the graph.
我的问题是，是否有一个有效的解决方案，这使得利用已经计算在最初的支配树的根节点直接支配的信息？换句话说，我不想从头开始为每个孩子开始，因为整个过程是相当耗时的。
My question is whether there is an efficient solution to this that makes use of immediate dominator information already calculated in the initial dominator tree for the root node? In other words I don't want to start from scratch for each of the children because the whole process is quite time consuming.
天真现在看来，这必须是可能的，因为会有很多节点的有idoms只是有点远高于他们，不受在图形顶部的变化曲线深处。
Naively it seems it must be possible since there will be plenty of nodes deep down in the graph that have idoms just a little way above them and are unaffected by changes at the top of the graph.
顺便说一句，就像旁白：这是奇怪的是的统治者树的主题是拥有的编译器的人并没有在上图的经典理论书籍没有提到这一点。我FindRoots Java堆分析仪 - - 我使用它的应用程序，是不相关的编译原理
BTW just as aside: it's bizarre that the subject of dominator trees is "owned" by compiler people and there is no mention of it in books on classic graph theory. The application I'm using it for - my FindRoots java heap analyzer - is not related to compiler theory.
澄清：我说的是有向图在这里。 根我其实指的就是以最大的可达性的节点。我已经更新上面的替换引用树与图的文字。我倾向于认为它们是树，因为形状的主要的树状。该图实际上是一个Java堆对象，正如你所想象的合理分层。我发现支配树用做OOM泄漏分析的时候，因为你所感兴趣的是什么让这个对象还活着吗？而答案最终是它的支配。支配树让你到＆lt;啊哈＆GT;见木而非树木。但有时很多垃圾浮到树的顶端，所以你有成千上万的儿童正下方的一个根源。对于这样的情况，我想尝试计算根扎根在每一个直接子支配树（在原始图），然后可能去一个新的水平下降等。 （我想不会担心反向链接暂时的可能性：）
Clarification: I'm talking about directed graphs here. The "root" I refer to is actually the node with the greatest reachability. I've updated the text above replacing references to "tree" with "graph". I tend to think of them as trees because the shape is mainly tree-like. The graph is actually of the objects in a java heap and as you can imagine is reasonably hierarchical. I have found the dominator tree useful when doing OOM leak analysis because what you are interested in is "what keeps this object alive?" and the answer ultimately is its dominator. Dominator trees allow you to <ahem> see the wood rather than the trees. But sometimes lots of junk floats to the top of the tree so you have a root with thousands of children directly below it. For such cases I would like to experiment with calculating the dominator trees rooted at each of the direct children (in the original graph) of the root and then maybe go to the next level down and so on. (I'm trying not to worry about the possibility of back links for the time being :)
推荐答案
<一个href="http://www.boost.org/doc/libs/1_36_0/libs/graph/doc/lengauer_tarjan_dominator.htm"><$c$c>boost::lengauer_tarjan_dominator_tree_without_dfs可能的帮助。
boost::lengauer_tarjan_dominator_tree_without_dfs might help.
这篇关于有效的方式来递归地计算支配树？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
