找到有向无环图的宽度......只有找到父母的能力 [英] Finding the width of a directed acyclic graph... with only the ability to find parents

问题描述

我试图找到一个有向无环图的宽度，如任意排序的节点列表所示，没有一个邻接列表。图表/列表适用于并行的GNU Make-like工作流管理器，它使用文件作为其执行顺序的标准。每个节点都有一个源文件和目标文件的列表。我们有一个散列表，以便给定文件名，可以确定产生它的节点。通过这种方式，我们可以通过检查使用此表生成每个源文件的节点来找出节点的父节点。

这是我在此的唯一能力点，而不会严重改变代码。代码已经公开使用了一段时间，我们想要做的最后一件事是显着改变结构并且发布不好。不，我们没有时间严格测试（我处于学术环境中）。理想情况下，我们希望我们能够做到这一点，而不是做任何比向节点添加字段更危险的事情。

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

谢谢！

<编辑：对于任何关心，这将在C中。是的，我知道我的伪代码是在一些可怕的拙劣的Python看起来像。我很希望这种语言并不重要。

解决方案

我认为你在这里考虑的宽度实际上并不是你想要的 - 宽度取决于你如何为每个有你选择的节点分配级别。您在决定是将所有来源分配到级别0还是将所有来源分配到最大级别时都注意到了这一点。

相反，您只需要计算节点数量和除以关键路径长度，这是dag中最长的路径。这给出了图的平均并行度。它只依赖于图形本身，它仍然给出了图形宽度的指示。

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

I'm trying to find the width of a directed acyclic graph... as represented by an arbitrarily ordered list of nodes, without even an adjacency list.

The graph/list is for a parallel GNU Make-like workflow manager that uses files as its criteria for execution order. Each node has a list of source files and target files. We have a hash table in place so that, given a file name, the node which produces it can be determined. In this way, we can figure out a node's parents by examining the nodes which generate each of its source files using this table.

That is the ONLY ability I have at this point, without changing the code severely. The code has been in public use for a while, and the last thing we want to do is to change the structure significantly and have a bad release. And no, we don't have time to test rigorously (I am in an academic environment). Ideally we're hoping we can do this without doing anything more dangerous than adding fields to the node.

I'll be posting a community-wiki answer outlining my current approach and its flaws. If anyone wants to edit that, or use it as a starting point, feel free. If there's anything I can do to clarify things, I can answer questions or post code if needed.

Thanks!

EDIT: For anyone who cares, this will be in C. Yes, I know my pseudocode is in some horribly botched Python look-alike. I'm sort of hoping the language doesn't really matter.

解决方案

I think the "width" you're considering here isn't really what you want - the width depends on how you assign levels to each node where you have some choice. You noticed this when you were deciding whether to assign all sources to level 0 or all sinks to the max level.

Instead, you just want to count the number of nodes and divide by the "critical path length", which is the longest path in the dag. This gives the average parallelism for the graph. It depends only on the graph itself, and it still gives you an indication of how wide the graph is.

To compute the critical path length, just do what you're doing - the critical path length is the maximum level you end up assigning.

这篇关于找到有向无环图的宽度......只有找到父母的能力的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！