16

我正在使用带有路径压缩的 Lengauer 和 Tarjan 算法来计算具有数百万个节点的图的支配树。该算法非常复杂，我不得不承认我没有花时间完全理解它，我只是在使用它。现在我需要计算根节点的直接子节点的支配树，并可能将图形向下递归到某个深度，重复此操作。即，当我为根节点的子节点计算支配树时，我想假装根节点已从图中删除。

我的问题是，是否有一个有效的解决方案，利用已经在初始支配树中为根节点计算的直接支配信息？换句话说，我不想为每个孩子从头开始，因为整个过程非常耗时。

天真地看起来这一定是可能的，因为在图表的深处会有很多节点，它们的 idms 就在它们上方一点点，并且不受图表顶部的变化的影响。

顺便说一句：支配树的主题由编译器人员“拥有”并且在经典图论书籍中没有提到它，这很奇怪。我使用它的应用程序——我的 FindRoots java 堆分析器——与编译器理论无关。

澄清：我在这里谈论有向图。我指的“根”实际上是可达性最大的节点。我已经更新了上面的文本，用“graph”替换了对“tree”的引用。我倾向于将它们视为树木，因为形状主要是树状。该图实际上是 Java 堆中的对象，并且您可以想象它是合理的层次结构。我发现支配树在进行 OOM 泄漏分析时很有用，因为您感兴趣的是“是什么让这个对象保持活力？” 答案最终是它的支配者。支配树可以让你<ahem>看到树林而不是树木。但有时很多垃圾会漂浮到树顶，所以你有一个根，下面有成千上万个孩子。对于这种情况，我想尝试计算以根的每个直接子节点（在原始图中）为根的支配树，然后可能会向下一层等等。（我暂时不担心反向链接的可能性：）

4

4 回答 4

6

boost::lengauer_tarjan_dominator_tree_without_dfs可能有帮助。

于 2008-10-31T09:07:02.997 回答
3

从缺乏评论来看，我猜 Stackoverflow 上没有多少人有相关经验可以帮助你。我就是其中的一员，但我不希望这样一个有趣的问题随着沉闷的砰砰声而落空，所以我会试着伸出援助之手。

我的第一个想法是，如果这个图是由其他编译器生成的，是否值得看一下开源编译器，比如 GCC，看看它是如何解决这个问题的？

我的第二个想法是，您问题的主要观点似乎是避免重新计算树根的结果。

我要做的是围绕每个节点创建一个包装器，其中包含节点本身以及与该节点关联的任何预先计算的数据。然后将使用这些包装类递归地从旧树重建一棵新树。当你构建这棵树时，你将从根开始，一直到叶节点。对于每个节点，您将存储迄今为止所有祖先的计算结果。这样，您应该只需要查看父节点和您正在处理的当前节点数据来计算新节点的值。

我希望这会有所帮助！

于 2008-10-30T16:11:25.603 回答
1

您能否详细说明您从哪种图表开始？我看不出作为树的图与该图的支配树之间有什么区别。每个节点的父节点都应该是它的 idom，它当然会被树中它上面的所有东西所支配。

于 2008-10-30T20:53:23.600 回答
0

我不完全理解你的问题，但在我看来你想要一些增量更新功能。不久前我研究了他们的算法是什么，但在我看来，没有已知的方法可以让大图快速做到这一点（至少从理论的角度来看）。

您可以只搜索“增量更新支配树”来查找一些参考资料。

我猜你知道Eclipse 内存分析器确实使用支配树，所以这个主题不再完全由编译器社区“拥有”:)

于 2009-02-18T10:27:55.600 回答