3

我试图找到一个有向无环图的宽度......由一个任意排序的节点列表表示，甚至没有邻接列表。

图形/列表用于类似 GNU Make 的并行工作流管理器，它使用文件作为执行顺序的标准。每个节点都有一个源文件和目标文件列表。我们有一个哈希表，因此，给定一个文件名，可以确定生成它的节点。这样，我们可以通过使用该表检查生成每个源文件的节点来确定节点的父节点。

这是我在这一点上唯一的能力，没有严重改变代码。该代码已经公开使用了一段时间，我们最不想做的就是显着改变结构并发布一个糟糕的版本。不，我们没有时间进行严格的测试（我在学术环境中）。理想情况下，我们希望我们可以做到这一点，而不会做任何比向节点添加字段更危险的事情。

我将发布一个社区 wiki 答案，概述我当前的方法及其缺陷。如果有人想编辑它，或将其用作起点，请随意。如果我可以做任何事情来澄清事情，我可以在需要时回答问题或发布代码。

谢谢！

编辑：对于任何关心的人，这将在 C 中。是的，我知道我的伪代码在一些非常糟糕的 Python 外观中。我有点希望语言并不重要。

4

3 回答 3

3

我认为您在这里考虑的“宽度”并不是您真正想要的 - 宽度取决于您如何将级别分配给您可以选择的每个节点。当您决定是否将所有源分配到级别 0 或将所有接收器分配到最大级别时，您会注意到这一点。

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

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

于 2010-05-08T15:20:14.300 回答
1

这是我（Platinum Azure，原作者）到目前为止所拥有的。

准备/增强：

  • 将“children”字段添加到链表（“DAG”）节点
  • 将“级别”字段添加到“DAG”节点
  • 将“children_left”字段添加到“DAG”节点。这用于确保在检查父级之前检查所有子级（在算法的后期阶段）。

算法：

  1. 查找所有节点的直接子节点数；此外，通过将 children==0 的节点添加到列表来确定叶子。

    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. 为每个节点分配一个“反向深度”级别。通常通过深度，我的意思是拓扑排序并将 depth=0 分配给没有父节点的节点。但是，我想我需要扭转这一点，depth=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)

所以这就是我到目前为止的想法。有没有办法改进它？一直都是线性时间，但它有五六次线性扫描，可能会有很多缓存未命中等。我不得不怀疑是否没有一种方法可以利用更好的数据结构来利用某些局部性——除了节点增强之外，实际上不需要更改底层代码。

有什么想法吗？

于 2010-05-07T18:29:13.287 回答
1

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

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

正如 Keith Randall 所问的那样，这个问题是您需要的正确测量吗？

于 2010-05-08T15:50:19.267 回答