找到有向无环图的宽度…只有找到父图的能力

我认为您在这里考虑的“宽度”并不是您真正想要的-宽度取决于您如何将级别分配给每个节点,在每个节点上您有一些选择。在决定是将所有源分配给级别0还是将所有汇分配给最大级别时,您注意到了这一点。

相反,您只需要计算节点数,然后除以“关键路径长度”,这是DAG中最长的路径。这给出了图形的平均并行度。它只取决于图形本身,并且它仍然可以指示图形的宽度。

要计算关键路径长度,只需做你正在做的事情-关键路径长度是你最终分配的最大级别。

在我看来,当你在进行这种最后一分钟的开发时,最好将新的结构与你已经使用的结构分开。在这一点上,如果时间紧迫,我会寻求一个更简单的解决方案。

1. 使用父数据为图形创建邻接矩阵(应该很容易)
2. 使用此矩阵执行拓扑排序。(如果时间紧迫,甚至可以使用tsort)
3. 现在已经有了拓扑排序,创建一个数组级别,每个节点一个元素。
4. 对于每个节点:
   • 如果节点没有父节点,请将其级别设置为0
   • 否则将其设置为其父级+1的最低级别。
5. 找到最大水平宽度。

问题是,正如基思·兰德尔所问,这是你需要的正确测量方法吗?

这是我(白金天青,原作者)迄今为止所拥有的。

准备/扩充:

• 将“子”字段添加到链接列表(“DAG”)节点
• 将“level”字段添加到“dag”节点
• 将“children_left”字段添加到“dag”节点。这用于确保在检查父对象之前检查所有子对象(在算法的后期)。

算法:

1. 查找所有节点的直接子节点数;另外,通过将children==0的节点添加到list来确定leaves。

   for l in L:
     l.children = 0
   
   
   for l in L:
     l.level = 0
     for p in l.parents:
       ++p.children
   
   Leaves = []
   for l in L:
     l.children_left = l.children
     if l.children == 0:
       Leaves.append(l)
   

2. 为每个节点指定一个“反向深度”级别。通常按深度,我指的是拓扑排序,并将深度=0分配给没有父节点的节点。但是,我想我需要把这个颠倒过来,深度=0对应于叶子。另外,我们要确保在没有所有子节点先“查看”它(以确定其适当的“深度级别”)的情况下,没有节点添加到队列中。

   max_level = 0
   while !Leaves.empty():
     l = Leaves.pop()
     for p in l.parents:
       --p.children_left
       if p.children_left == 0:
         /* we only want to append parents with for sure correct level */
         Leaves.append(p)
       p.level = Max(p.level, l.level + 1)
       if p.level > max_level:
         max_level = p.level
   

3. 现在每个节点都有一个级别,只需创建一个数组,然后再次遍历列表来计算每个级别中的节点数。

   level_count = new int[max_level+1]
   for l in L:
     ++level_count[l.level]
   
   width = Max(level_count)
   

所以到目前为止我就是这么想的。有办法改进吗?一路上都是线性时间,但有五六次线性扫描,可能会有很多缓存未命中等等。我想知道是否没有一种方法可以利用具有更好数据结构的某个局部性,而不必实际更改节点扩展以外的底层代码。

有什么想法吗?