只能查找父节点的情况下，如何找到有向无环图的宽度？

Question

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

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

这是我现在唯一能做到的能力，而不会严重改变代码。该代码已经在公共使用中一段时间了，我们最不想做的就是显著改变结构并发布糟糕的版本。不，我们没有时间进行严格测试（我在学术环境中）。理想情况下，我们希望能够在不做比添加节点更危险的事情的情况下完成此操作。

我将发布社区维基答案，概述我的当前方法及其缺陷。如果有人想编辑它或以此为起点，请随意。如果有什么我可以澄清的事情，我可以回答问题或发布代码。

谢谢！

编辑：对于任何关心的人，这将是C语言。是的，我知道我的伪代码是一些可怕的Python模仿品。我有点希望语言并不真的很重要。

- Platinum Azure

Answer 1

我认为你在考虑的“宽度”并不是你想要的-宽度取决于你如何为每个节点分配级别，你有一些选择。当你决定将所有源分配给级别0或将所有汇分配到最大级别时，你已经注意到了这一点。

相反，你只需要计算节点数并除以"关键路径长度"，即dag中最长的路径。这样会为图形提供平均并行性。它仅依赖于图形本身，并且仍然向你提供了有关图形宽度的指示。

要计算关键路径长度，只需按照你正在进行的操作进行-关键路径长度是你最终分配的最大级别。

- Keith Randall

---

嗯...我已经成功实现了我的算法。我不确定宽度是否是我真正想要的，但这是我被告知应该使用的。我会接受这个答案，因为它让我思考最多，如果再次遇到这种情况，我会记住这个答案。(值得考虑的是：在DAG中找到最长路径很困难，因为某些任务需要比其他任务更长时间来执行。因此，这个解决方案似乎至少和我的一样有缺陷。) - Platinum Azure

在带有节点权重（或边权重）的DAG中，最长路径很容易，可以使用Dijkstra算法或者像Il-Bhima建议的那样进行拓扑排序和一次遍历。 - Keith Randall

Answer 2

这是我（原作者Platinum Azure）到目前为止的工作。

准备/增强：

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

算法：

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. 为每个节点分配一个“反向深度”级别。通常按深度排序并将深度=0分配给没有父节点的节点。但是，我认为需要反转这个过程，使深度=0对应于叶子节点。此外，我们要确保在所有子节点“查看”它之前不会将任何节点添加到队列中（以确定其正确的“深度级别”）。

   max_level = 0
   while !Leaves.empty():
     l = Leaves.pop()
     for p in l.parents:
       --p.children_left
       if p.children_left == 0:
         /* 我们只想附加具有确定正确级别的父节点 */
         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)
   

---

这就是我目前的想法。有没有办法改进它？它一直是线性时间，但它有五到六个线性扫描，可能会有很多缓存未命中等问题。我不得不想知道是否有一种方法可以利用更好的数据结构来利用一些局部性--而不必改变节点增强以外的底层代码。

你有什么想法吗？

- Platinum Azure

Answer 3

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

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

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

- Il-Bhima