我正在使用具有路径压缩的Lengauer和Tarjan算法来计算有数百万个节点的图的支配树.算法非常复杂,我不得不承认我没有花时间完全理解它,我只是使用它.现在我需要计算根节点的直接子节点的支配树,并可能将图形向下递减到重复此操作的某个深度.即,当我为根节点的子节点计算支配树时,我想假装根节点已从图中移除.
我的问题是,是否有一个有效的解决方案,利用已经在根节点的初始支配树中计算的直接支配者信息？换句话说,我不想从头开始为每个孩子,因为整个过程非常耗时.
天真地看起来一定是可能的,因为在图表的内部会有很多节点,这些节点在它们之上只有一点点,并且不受图形顶部变化的影响.
顺便说一句:在统治者树的主题是由编译人员"拥有"并且在经典图论的书中没有提到它,这是奇怪的.我正在使用它的应用程序 - 我的FindRoots java堆分析器 - 与编译器理论无关.
澄清:我在这里谈论有向图.我所指的"根"实际上是具有最大可达性的节点.我已经更新了上面的文本,用"graph"替换了对"tree"的引用.我倾向于将它们视为树木,因为形状主要是树等.该图实际上是java堆中的对象,您可以想象它是合理的层次结构.我发现主导树在进行OOM泄漏分析时很有用,因为你感兴趣的是"是什么让这个物体保持活力？" 答案最终是它的统治者.支配树允许你<ahem>看到木头而不是树木.但有时很多垃圾漂浮在树顶,所以你有一个直接在它下面有数千个孩子的根.对于这样的情况,我想尝试计算根植于根的每个直接子节点(在原始图形中)的支配树,然后可以进入下一级别,依此类推.(我试着暂时不担心反向链接的可能性:)
我正在寻找一种类似于CLR中的红黑区间树的区间树算法,但它默认支持合并区间,因此从不存在任何重叠区间.
换句话说,如果您有一个包含两个区间[2,3]和[5,6]的树,并且您添加了区间[4,4],则结果将是仅包含一个区间[2,6]的树.
谢谢
更新:我正在考虑的用例是计算传递闭包.间隔集用于存储后继集,因为它们被发现非常紧凑.但是,如果你将区间集表示为链表,我发现在某些情况下它们会变得非常大,因此找到插入点所需的时间也是如此.因此我对间隔树感兴趣.还有很多将一棵树与另一棵树合并(即一组OR操作) - 如果两棵树都很大,那么使用两棵树的顺序走路而不是每个间隔的重复插入来创建新树可能更好.
我最近加入了一个包含大量代码的项目,我想开始通过调用图来记录和可视化一些流程,以便更好地理解所有内容如何组合在一起.这是我希望在理想工具中看到的内容:
这种工具的交互使用是关键,我不是在寻找Graphviz类型的解决方案,因为会有太多的混乱.形成整个图形的子集视图的能力将非常方便(可能具有不重要的混乱灰色).不需要从源代码自动生成,很乐意手动输入.
几乎像一张思维导图.
那有意义吗？如果您不了解这样的工具,您是否也认为它会有用？(以防我有一天决定去刮痒!)
鉴于以下计划:
import java.io.*;
import java.util.*;
public class GCTest {
public static void main(String[] args) throws Exception {
List cache = new ArrayList();
while (true) {
cache.add(new GCTest().run());
System.out.println("done");
}
}
private byte[] run() throws IOException {
Test test = new Test();
InputStream is = test.getInputStream();
ByteArrayOutputStream baos = new ByteArrayOutputStream();
byte[] buff = new byte[256];
int len = 0;
while (-1 != (len = is.read())) {
baos.write(buff, 0, len);
}
return baos.toByteArray();
}
private class Test {
private InputStream is; …