我试图找到有向无环图的宽度......由任意排序的节点列表表示，甚至没有邻接列表。
该图/列表适用于类似 GNU Make 的并行工作流程管理器，该管理器使用文件作为执行顺序的标准。每个节点都有一个源文件和目标文件的列表。我们有一个哈希表，这样，给定文件名，就可以确定生成该文件的节点。这样，我们可以通过使用该表检查生成每个源文件的节点来找出节点的父节点。
这是我目前唯一拥有的能力，无需严重更改代码。代码已经公开使用了一段时间，我们最不想做的就是大幅改变结构并发布糟糕的版本。不，我们没有时间进行严格的测试（我处于学术环境中）。理想情况下，我们希望能够做到这一点，而不需要做任何比向节点添加字段更危险的事情。
我将发布一个社区维基答案，概述我当前的方法及其缺陷。如果有人想编辑它，或者将其用作起点，请随意。如果我可以做任何事情来澄清事情，我可以回答问题或发布代码（如果需要）。
Thanks!
编辑：对于任何关心的人，这将是用 C 语言编写的。是的，我知道我的伪代码是用一些非常糟糕的 Python 语言编写的。我有点希望语言并不重要。
我认为您在这里考虑的“宽度”并不是您真正想要的 - 宽度取决于您如何将级别分配给您有选择的每个节点。当您决定是将所有源分配到级别 0 还是将所有接收器分配到最大级别时，您注意到了这一点。
相反，您只需计算节点数并除以“关键路径长度”，即 dag 中的最长路径。这给出了图的平均并行度。它仅取决于图表本身，并且仍然可以指示图表的宽度。
要计算关键路径长度，只需执行您正在做的操作即可 - 关键路径长度是您最终分配的最大级别。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
