1

我有一个“节点”网络，每个节点都会产生“结果”。每个节点和结果都有一个唯一的名称/ID。结果用作每个节点的输入和输出。当一个节点的所有输入结果都可用时，它可以被执行。当节点完成执行时，其输出结果将可用。

例如：

input node output
       A    x
x      B    y,z
x,z    C    q

在上述网络中。节点 A 没有输入，可以先执行。然后 B 可以在结果 x 可用时执行。当 A 和 B 都完成时，C 可以执行，因为它取决于 A 和 B 的结果。结果也可以是最终产品，如本例中的 y，它不用作任何节点的输入。

网络可能要复杂得多。每个节点可以产生多个结果，并且它可以具有多个输入依赖项。

我希望能够选择一个结果，比如“q”并找出需要执行哪些节点才能到达那里。我想在更大的节点网络中为多个结果执行此操作。

我觉得这是一个常见的算法，但我没有这方面的经验。它不像树一样分层，因为依赖关系可以创建圆圈。从我读过的内容来看，我认为它一定是一种森林图。

无论如何，它必须是可遍历的。总是至少有一个节点可以首先执行，并且所有其他节点应该能够按照某种顺序执行，而不会造成两个节点相互等待完成的死锁。

用代码描述这个网络/它的节点的常用方法是什么，这种网络的正式名称是什么？

4

2 回答 2

1

您要查找的名称是'dependency graph'。

用于分解的算法称为“拓扑排序”（参见：http ://en.wikipedia.org/wiki/Topological_sorting ）

解决此类依赖关系的最著名工具之一称为make。

与您的示例对应的 Makefile 如下所示：

x :
    echo node A

y z : x
    echo node B

q   : x z
    echo node C

如您所见，语法与示例表中使用的语法几乎相同。唯一的主要区别是“列”的顺序是颠倒的——说“到达……我首先需要……”而不是“从……我可以去……”。

键入make <TARGET>您可以轻松验证它是否按照您希望的顺序解析节点。这里有一些例子：

make q
  * node A
  * node B
  * node C

make x
  * node A

make z
  * node A
  * node B

（为了使输出更漂亮，这是用于上面输出的版本：

x :
    @echo " * node A"

y z : x
    @echo " * node B"

q   : x z
    @echo " * node C"

)

于 2013-03-25T22:04:21.790 回答
0

除了只是一种图，听起来你想要的语义就像一个带有彩色标记的Petri 网。Petri 网的可达性分析是一个成熟的问题，文献中存在算法。也许维基百科的文章会给你一些想法，从那里开始。

于 2013-03-25T22:06:02.717 回答