如果节点的所有后代和祖先都称为平面列表，则重建 DAG

Question

我遇到的问题与许多关于 DAG 的问题完全不同，因此很难找到答案。这可能意味着它非常简单。

背景：我必须通过解析状态文件在 Python 中构建 Terraform DAG。已知该图是非循环的，并且在我的实现中所有节点都连接到一个根。所有节点将其祖先的完整列表存储为平面列表。

所以问题不在于具体的编程实现，而在于我需要为此使用的算法。我一直在为自己使用不同的示例图，不能肯定地说它们涵盖了所有潜在的问题，但我发现了一些即使在那里也让我难过的问题。

它们基本上都归结为决定两个节点之间是否有直接的东西。

示例。

                      Forward ("deps of")       Reverse ("depends on")
g --> a <-------.     a = []                    a = [bcdefghi]
^     ^^        |     b = [aefi]                b = [c]
|     |  \      |     c = [abdfi]               c = []
h     |   \     |     d = [afi]                 d = [c]
      b-> e     |     e = [afi]                 e = [b]
      ^   |     |     f = [ai]                  f = [bcde]
      |   v     |     g = [a]                   g = [h]
      c   f --> i     h = [ag]                  h = []
      |   ^           i = [a]                   i = [bcdef]
      v   |
      d---'

只有右边两列，如何推导出左边的DAG？是否有我不知道的标准算法？

（我真诚地希望我没有在图表或列表中犯任何令人困惑的错误，但我现在盯着这些东西看得太久了。）

Answer 1

在您的示例中，您可以添加一条从 h 到 a 的边。它会改变图形（同时保持它是一个 DAG），但它不会改变这些列中的任何一个。

任务无法完成。

如果节点的所有后代和祖先都称为平面列表，则重建 DAG

Rebuilding a DAG if all of a node's descendants and ancestors are known as a flat list

graph-theory