有向无环图的人类可读文本表示
A human-readable textual representation of a Directed Acycling Graph
一棵树有一堆人类和机器可读的文本表示——例如嵌套列表（以各种表示形式——例如 JSON 和 YAML）和 XML。结合缩进，它们使想象结果结构变得非常容易。
但我没有看到 Directed Acyclic Graph 具有相同级别的可读性。它是比树更通用的数据结构，因此不能使用上述格式（无论如何逐字）。
- 我见过的所有人类可读的表示都是图形化的
- 原始文本表示将列出所有节点及其连接——如果有多个节点，则很难想象图形
我想到的应用程序是各种流程图——例如自然而然地出现在各种规划任务中。
为了限制问题的范围，我主要要求的是标准解决方案，或者至少是生产就绪的并且在某些实践领域被证明有效。如果有 none，任何通过某种同行评审的实验命题（例如在已发表的科学论文中提出的）都必须这样做。
git log --graph 表示以文本方式提交的有向图。 （在 Git 中，多个提交可以从单个提交中分支出来，并且两个提交可以合并为一个新提交，从旧提交到新提交的时间可以是一个方向。所以它是一个没有循环的有向图）
--format...%p 包括父提交，因此它可能被认为是机器可读的。例如
git log --graph --abbrev-commit --decorate --format=format:'%h - %aD %p %s'
会显示如下内容：
* 585a502 - Mon, 23 Jul 2012 19:13:28 +0100 1ce012a 00b3327 Merge github.com:orangeduck/CPlus
|\
| * 00b3327 - Mon, 23 Jul 2012 07:38:16 -0700 9a24ec6 5c5b6e2 Merge pull request #4 from felipecruz/feature/create_tests_dir
| |\
| | * 5c5b6e2 - Mon, 23 Jul 2012 10:04:07 -0300 11fb96d move tests to tests dir
| | * 11fb96d - Sun, 22 Jul 2012 18:19:51 -0300 9a24ec6 fix variable name in Strind_Discard
| |/
* | 1ce012a - Mon, 23 Jul 2012 19:13:05 +0100 9a24ec6 Array instances Push. Used memmove for dynamic container manipulation.
|/
* 9a24ec6 - Sun, 22 Jul 2012 14:02:24 +0100 b41f9c2 Better documented source
* b41f9c2 - Sun, 22 Jul 2012 12:50:13 +0100 2f4b862 Assign class. Added WIP Array Type.
其中 * - 伪图形中的节点、线和随后的提交 - 方向从较早（底部）到较新（顶部）的边缘
更新
非平面 DAG 在这里看起来笨拙得多。非平面示例，与维基百科中的 this 示例相同：
* 094f405 - Thu, 19 Sep 2019 03:51:50 +0300 ab942ca 76ee1ad X, Y, Z
|\
| * 76ee1ad - Thu, 19 Sep 2019 03:49:49 +0300 b1ea78b 8d32234 Y, Z
| |\
* | \ ab942ca - Thu, 19 Sep 2019 03:51:17 +0300 b20cf0b 7f714d9 XY, XZ
|\ \ \
| * \ \ 7f714d9 - Thu, 19 Sep 2019 03:49:05 +0300 b84010c 8d32234 X, Z
| |\ \ \
| | | |/
| | |/|
| | * | 8d32234 - Thu, 19 Sep 2019 03:45:18 +0300 6927afa Z
* | | | b20cf0b - Thu, 19 Sep 2019 03:47:04 +0300 b84010c b1ea78b X, Y
|\ \ \ \
| |/ / /
|/| | /
| | |/
| |/|
| * | b1ea78b - Thu, 19 Sep 2019 03:44:40 +0300 6927afa Y
| |/
* | b84010c - Thu, 19 Sep 2019 03:43:53 +0300 6927afa X
|/
* 6927afa - Thu, 19 Sep 2019 03:31:01 +0300 4bf9923 #4
还有很多 markdowns 支持有向图，例如this one（谷歌搜索的第一个）
图形的一个很好的文本表示是 dot language from graphviz。语法是易于阅读的关系描述。
请注意，graphviz 背后的核心思想不是从图表开始描述它，而是不知道图表是什么样子，从你知道的开始，然后让 graphviz 生成图给你。由于这个设计目标 graphviz 没有任何手动放置节点的功能 - 它会根据您 select.
的算法自动绘制节点
这是使用 graphviz 的示例：
Assume you want to draw an org chart of a company. You don't know what the graphs look like yet but you know who reports to who. You can describe the company as follows:
digraph {
CEO -> Board_of_Directors
CTO -> CEO
CFO -> CEO
COO -> CEO
DevLead -> CTO
DevTeam -> DevLead
DevOps -> CTO
Head_of_Accounting -> CFO
Accountants -> Head_of_Accounting
Procurement -> Head_of_Accounting
Procurement -> COO
Logistics -> COO
Tech_support -> CTO
Tech_support -> COO
}
运行 这与 dot 算法将生成以下图表：
Graphviz 确实具有复杂的节点和边描述功能，例如定义节点的形状、边的标签等。但是添加此类细节通常会稍微降低图形的可读性，因为现在大部分代码看起来像样式定义而不是节点之间的关系。不过，我认为图形定义本身相当清晰。与任何语言一样，它旨在用于解决人类问题（在这种情况下，如果您知道状态和转换，则弄清楚图形的样子）并且必须至少在某种程度上可用于其预期用途。
在形式语言和自动机理论中，最重要的结果之一是确定性有限自动机和（形式）正则表达式之间的等价性。 DFA 只是带有一些额外信息的标记有向图。我提出以下建议：（1）考虑 DAG 中的所有状态都接受（2）用该弧开始的顶点的标签标记每个弧（3）为这个 DFA 产生一个正则表达式（选择拓扑最小状态作为不同 DFA 的起始状态）。首先，您需要对顶点进行拓扑排序，然后为每个连接的组件创建一个 DFA/regular 表达式对。
示例：节点 A 转到节点 B 和 C，B 转到 D 和 E，C 转到 E 和 F。
拓扑排序发现按标签字母顺序排列的顶点已经排序：A、B、C、D、E。从拓扑最小节点A开始有一个连通分量。
在标记圆弧后通过算法可能会给你一个像 A(B(D+E)+C(E+F)) 这样的正则表达式。
请注意，由于图形是无环的，因此您永远不需要 Kleene 闭包符号 asterisk/star。如果有兴趣，可以详细说明这个答案。
编辑：一些详细说明。
评论中指出，上述正则表达式中存在一些重复。这是真实的。然而，这可能不会变成灾难性的重复：我们可以避免重复子图，至少在某种程度上是这样。例如，假设在上面的例子中有一个长子图，其拓扑最小节点 E。假设它有可接受的正则表达式 r。那么我们可以将上面的正则表达式调整为：A((B+C)Er + BD + CF)。仍然存在重复，现在在 B 和 C 而不是 E 之间，但是由于子图具有拓扑最小节点 E，这仍然是更简洁的表示。
最小化通用正则表达式是 PSPACE 完全的。但是，我不知道这个界限是否适用于最小化从图是 DAG 的 DFA 生成的正则表达式。正如评论正确指出的那样，DFA 和 RE 的常规理论处理比 DAG 更复杂的一般有向图。完全有可能没有 Kleene 星号的正则表达式比有 Kleene 星号的正则表达式更容易最小化。这可能是一个值得单独提出的问题，可能在 cs.stackexchange.com.
表示 DFA 的另一种常用方法是使用常规语法。这本质上等同于简单地列出对应于 DFA 状态图中弧的有序节点对。
EDIT2：一个例子
另一个答案有这个例子：
A->B
A->C
A->D
B->E
B->F
C->E
C->G
D->F
D->G
E->H
F->H
G->H
我怀疑此处描述的几乎最小的正则表达式大致如下：A(B(E+F)+C(E+G)+D(F+G))H。我们的表示比较如下：
- 等价语法中有 24 个符号，但正则表达式中有 11 个符号
- 12 个等价语法运算符，但 8 个正则表达式运算符
- 36 vs 19 个令牌
很难与可见性图表进行比较，因为表示方式如此不同，但正则表达式显然使用了更少的符号总数（如果我们计算符号的话）。
EDIT 3：又提出了一个例子，如下：
a -> b
a -> c
a -> d
b -> c
b -> e
c -> f
d -> e
d -> f
d -> g
e -> f
e -> h
f -> i
g -> h
g -> i
h -> i
我可以手工想出的最简洁的正则表达式（第二次猜测，没有方法论）是这样的：a((b+d)e(f+h)+(bc+c+d)f+ dg(h+#))i 。请注意，# 不是通常的正式正则表达式语法的一部分，它表示空正则表达式，即它生成由空字符串组成的语言。这是一种方便的方式，可以更好地进行最小化，并且不会增加计算能力，只会增加表达能力。如果你不喜欢它，你可以用 dgh + dh 代替，它只长一个符号。这种表示仍然是原始语法大小的一半左右。实际上，语法和可见性图的比较是相似的w.r.t。最后一个例子的那些。
编辑 4：我现在将扩展上一个示例中的表达式，以表明它是通过 DAG 的不相交路径并集的分解表示。
a((b+d)e(f+h)+(bc+c+d)f+dg(h+#))i
a((b+d)e(f+h)+(bc+c+d)f+dgh+dg)i
a((b+d)ef+(b+d)eh+(bc+c+d)f+dgh+dg)i
a(bef+def+beh+deh+(bc+c+d)f+dgh+dg)i
a(bef+def+beh+deh+bcf+cf+df+dgh+dg)i
abefi+adefi+abehi+adehi+abcfi+acfi+adfi+adghi+adgi
这是可见性表示的简单变体。请参阅：平面正交和折线
绘图算法 部分：7.2.3 可见性表示
A -> B
A -> C
A -> E
B -> D
B -> F
C -> D
C -> G
D -> H
E -> F
E -> G
E -> G
F -> H
G--------G--------G
| | |
| H--H--H |
| | | |
| F---F D---D |
| | | | | |
E-E B--B--B C-C
| | |
A------A------A
这里是this
A -> B
A -> C
A -> D
B -> E
B -> F
C -> E
C -> G
D -> F
D -> G
E -> H
F -> H
G -> H
)|(表示桥接，无连接。
H--H--H
| | |
E-------E | G----G--G
| | | | |
| F---)|(-F-)|(---F |
| | | | | |
B--B C--C--C D--D
| | |
A----------A----------A
来自：Orthogonal Graph Drawing with Constraints图3.4(a)
a -> b
a -> c
a -> d
b -> c
b -> e
c -> f
d -> e
d -> f
d -> g
e -> f
e -> h
f -> i
g -> h
g -> i
h -> i
i---i-------i
| | |
f---f---f h---h |
| | | | | |
| | e---e g---g
| | | | |
| d---d--)|(--d
| | |
c---c | |
| | | |
| b-------b |
| | |
a---a-----------a
我将使用 带有锚点的 YAML 嵌套列表。 （这相当于 XML 与实体，但后者有更多的噪音。）
（我已经在考虑了，但想知道是否发明了更好的东西。看起来还没有。但最重要的是，@Patrick87 正式表明它是一个足够的代表。）
相当于如果我用缩进替换合成和没有缩进的联合；并且当节点被多次引用时，锚点允许消除节点下子图的重复。
例如@GuyCoder 的例子
A->B
A->C
A->D
B->E
B->F
C->E
C->G
D->F
D->G
E->H
F->H
G->H
对应A(B(E+F)+C(E+G)+D(F+G))H ≡ A(B(EH+FH)+C(EH+GH)+D(FH+GH))
将是
- A
- B
- &E E
- &H H
- &F F
- *H
- C
- *E
- &G G
- *H
- D
- *F
- *G
（为了统一起见，如果生成它，每个原始节点都可以作为锚点。）
我不在乎图表是否是平面的，因为任何交叉链接都不是 "drawn"。
作为奖励，它允许指定附加到每个节点的数据，作为以节点为根的散列table。 （虽然超过了一定的大小，但分开放置数据可能会更清晰。）
一棵树有一堆人类和机器可读的文本表示——例如嵌套列表（以各种表示形式——例如 JSON 和 YAML）和 XML。结合缩进，它们使想象结果结构变得非常容易。
但我没有看到 Directed Acyclic Graph 具有相同级别的可读性。它是比树更通用的数据结构，因此不能使用上述格式（无论如何逐字）。
- 我见过的所有人类可读的表示都是图形化的
- 原始文本表示将列出所有节点及其连接——如果有多个节点，则很难想象图形
我想到的应用程序是各种流程图——例如自然而然地出现在各种规划任务中。
为了限制问题的范围，我主要要求的是标准解决方案，或者至少是生产就绪的并且在某些实践领域被证明有效。如果有 none，任何通过某种同行评审的实验命题（例如在已发表的科学论文中提出的）都必须这样做。
git log --graph 表示以文本方式提交的有向图。 （在 Git 中，多个提交可以从单个提交中分支出来，并且两个提交可以合并为一个新提交，从旧提交到新提交的时间可以是一个方向。所以它是一个没有循环的有向图）
--format...%p 包括父提交，因此它可能被认为是机器可读的。例如
git log --graph --abbrev-commit --decorate --format=format:'%h - %aD %p %s'
会显示如下内容：
* 585a502 - Mon, 23 Jul 2012 19:13:28 +0100 1ce012a 00b3327 Merge github.com:orangeduck/CPlus
|\
| * 00b3327 - Mon, 23 Jul 2012 07:38:16 -0700 9a24ec6 5c5b6e2 Merge pull request #4 from felipecruz/feature/create_tests_dir
| |\
| | * 5c5b6e2 - Mon, 23 Jul 2012 10:04:07 -0300 11fb96d move tests to tests dir
| | * 11fb96d - Sun, 22 Jul 2012 18:19:51 -0300 9a24ec6 fix variable name in Strind_Discard
| |/
* | 1ce012a - Mon, 23 Jul 2012 19:13:05 +0100 9a24ec6 Array instances Push. Used memmove for dynamic container manipulation.
|/
* 9a24ec6 - Sun, 22 Jul 2012 14:02:24 +0100 b41f9c2 Better documented source
* b41f9c2 - Sun, 22 Jul 2012 12:50:13 +0100 2f4b862 Assign class. Added WIP Array Type.
其中 * - 伪图形中的节点、线和随后的提交 - 方向从较早（底部）到较新（顶部）的边缘
更新
非平面 DAG 在这里看起来笨拙得多。非平面示例，与维基百科中的 this 示例相同：
* 094f405 - Thu, 19 Sep 2019 03:51:50 +0300 ab942ca 76ee1ad X, Y, Z
|\
| * 76ee1ad - Thu, 19 Sep 2019 03:49:49 +0300 b1ea78b 8d32234 Y, Z
| |\
* | \ ab942ca - Thu, 19 Sep 2019 03:51:17 +0300 b20cf0b 7f714d9 XY, XZ
|\ \ \
| * \ \ 7f714d9 - Thu, 19 Sep 2019 03:49:05 +0300 b84010c 8d32234 X, Z
| |\ \ \
| | | |/
| | |/|
| | * | 8d32234 - Thu, 19 Sep 2019 03:45:18 +0300 6927afa Z
* | | | b20cf0b - Thu, 19 Sep 2019 03:47:04 +0300 b84010c b1ea78b X, Y
|\ \ \ \
| |/ / /
|/| | /
| | |/
| |/|
| * | b1ea78b - Thu, 19 Sep 2019 03:44:40 +0300 6927afa Y
| |/
* | b84010c - Thu, 19 Sep 2019 03:43:53 +0300 6927afa X
|/
* 6927afa - Thu, 19 Sep 2019 03:31:01 +0300 4bf9923 #4
还有很多 markdowns 支持有向图，例如this one（谷歌搜索的第一个）
图形的一个很好的文本表示是 dot language from graphviz。语法是易于阅读的关系描述。
请注意，graphviz 背后的核心思想不是从图表开始描述它，而是不知道图表是什么样子，从你知道的开始，然后让 graphviz 生成图给你。由于这个设计目标 graphviz 没有任何手动放置节点的功能 - 它会根据您 select.
这是使用 graphviz 的示例：
Assume you want to draw an org chart of a company. You don't know what the graphs look like yet but you know who reports to who. You can describe the company as follows:
digraph {
CEO -> Board_of_Directors
CTO -> CEO
CFO -> CEO
COO -> CEO
DevLead -> CTO
DevTeam -> DevLead
DevOps -> CTO
Head_of_Accounting -> CFO
Accountants -> Head_of_Accounting
Procurement -> Head_of_Accounting
Procurement -> COO
Logistics -> COO
Tech_support -> CTO
Tech_support -> COO
}
运行 这与 dot 算法将生成以下图表：
Graphviz 确实具有复杂的节点和边描述功能，例如定义节点的形状、边的标签等。但是添加此类细节通常会稍微降低图形的可读性，因为现在大部分代码看起来像样式定义而不是节点之间的关系。不过，我认为图形定义本身相当清晰。与任何语言一样，它旨在用于解决人类问题（在这种情况下，如果您知道状态和转换，则弄清楚图形的样子）并且必须至少在某种程度上可用于其预期用途。
在形式语言和自动机理论中，最重要的结果之一是确定性有限自动机和（形式）正则表达式之间的等价性。 DFA 只是带有一些额外信息的标记有向图。我提出以下建议：（1）考虑 DAG 中的所有状态都接受（2）用该弧开始的顶点的标签标记每个弧（3）为这个 DFA 产生一个正则表达式（选择拓扑最小状态作为不同 DFA 的起始状态）。首先，您需要对顶点进行拓扑排序，然后为每个连接的组件创建一个 DFA/regular 表达式对。
示例：节点 A 转到节点 B 和 C，B 转到 D 和 E，C 转到 E 和 F。
拓扑排序发现按标签字母顺序排列的顶点已经排序：A、B、C、D、E。从拓扑最小节点A开始有一个连通分量。
在标记圆弧后通过算法可能会给你一个像 A(B(D+E)+C(E+F)) 这样的正则表达式。
请注意，由于图形是无环的，因此您永远不需要 Kleene 闭包符号 asterisk/star。如果有兴趣，可以详细说明这个答案。
编辑：一些详细说明。
评论中指出，上述正则表达式中存在一些重复。这是真实的。然而，这可能不会变成灾难性的重复：我们可以避免重复子图，至少在某种程度上是这样。例如，假设在上面的例子中有一个长子图，其拓扑最小节点 E。假设它有可接受的正则表达式 r。那么我们可以将上面的正则表达式调整为：A((B+C)Er + BD + CF)。仍然存在重复，现在在 B 和 C 而不是 E 之间，但是由于子图具有拓扑最小节点 E，这仍然是更简洁的表示。
最小化通用正则表达式是 PSPACE 完全的。但是，我不知道这个界限是否适用于最小化从图是 DAG 的 DFA 生成的正则表达式。正如评论正确指出的那样，DFA 和 RE 的常规理论处理比 DAG 更复杂的一般有向图。完全有可能没有 Kleene 星号的正则表达式比有 Kleene 星号的正则表达式更容易最小化。这可能是一个值得单独提出的问题，可能在 cs.stackexchange.com.
表示 DFA 的另一种常用方法是使用常规语法。这本质上等同于简单地列出对应于 DFA 状态图中弧的有序节点对。
EDIT2：一个例子
另一个答案有这个例子：
A->B
A->C
A->D
B->E
B->F
C->E
C->G
D->F
D->G
E->H
F->H
G->H
我怀疑此处描述的几乎最小的正则表达式大致如下：A(B(E+F)+C(E+G)+D(F+G))H。我们的表示比较如下：
- 等价语法中有 24 个符号，但正则表达式中有 11 个符号
- 12 个等价语法运算符，但 8 个正则表达式运算符
- 36 vs 19 个令牌
很难与可见性图表进行比较，因为表示方式如此不同，但正则表达式显然使用了更少的符号总数（如果我们计算符号的话）。
EDIT 3：又提出了一个例子，如下：
a -> b
a -> c
a -> d
b -> c
b -> e
c -> f
d -> e
d -> f
d -> g
e -> f
e -> h
f -> i
g -> h
g -> i
h -> i
我可以手工想出的最简洁的正则表达式（第二次猜测，没有方法论）是这样的：a((b+d)e(f+h)+(bc+c+d)f+ dg(h+#))i 。请注意，# 不是通常的正式正则表达式语法的一部分，它表示空正则表达式，即它生成由空字符串组成的语言。这是一种方便的方式，可以更好地进行最小化，并且不会增加计算能力，只会增加表达能力。如果你不喜欢它，你可以用 dgh + dh 代替，它只长一个符号。这种表示仍然是原始语法大小的一半左右。实际上，语法和可见性图的比较是相似的w.r.t。最后一个例子的那些。
编辑 4：我现在将扩展上一个示例中的表达式，以表明它是通过 DAG 的不相交路径并集的分解表示。
a((b+d)e(f+h)+(bc+c+d)f+dg(h+#))i
a((b+d)e(f+h)+(bc+c+d)f+dgh+dg)i
a((b+d)ef+(b+d)eh+(bc+c+d)f+dgh+dg)i
a(bef+def+beh+deh+(bc+c+d)f+dgh+dg)i
a(bef+def+beh+deh+bcf+cf+df+dgh+dg)i
abefi+adefi+abehi+adehi+abcfi+acfi+adfi+adghi+adgi
这是可见性表示的简单变体。请参阅：平面正交和折线 绘图算法 部分：7.2.3 可见性表示
A -> B
A -> C
A -> E
B -> D
B -> F
C -> D
C -> G
D -> H
E -> F
E -> G
E -> G
F -> H
G--------G--------G
| | |
| H--H--H |
| | | |
| F---F D---D |
| | | | | |
E-E B--B--B C-C
| | |
A------A------A
这里是this
A -> B
A -> C
A -> D
B -> E
B -> F
C -> E
C -> G
D -> F
D -> G
E -> H
F -> H
G -> H
)|(表示桥接，无连接。
H--H--H
| | |
E-------E | G----G--G
| | | | |
| F---)|(-F-)|(---F |
| | | | | |
B--B C--C--C D--D
| | |
A----------A----------A
来自：Orthogonal Graph Drawing with Constraints图3.4(a)
a -> b
a -> c
a -> d
b -> c
b -> e
c -> f
d -> e
d -> f
d -> g
e -> f
e -> h
f -> i
g -> h
g -> i
h -> i
i---i-------i
| | |
f---f---f h---h |
| | | | | |
| | e---e g---g
| | | | |
| d---d--)|(--d
| | |
c---c | |
| | | |
| b-------b |
| | |
a---a-----------a
我将使用 带有锚点的 YAML 嵌套列表。 （这相当于 XML 与实体，但后者有更多的噪音。）
（我已经在考虑了，但想知道是否发明了更好的东西。看起来还没有。但最重要的是，@Patrick87 正式表明它是一个足够的代表。）
相当于
例如@GuyCoder 的例子
A->B A->C A->D B->E B->F C->E C->G D->F D->G E->H F->H G->H
对应A(B(E+F)+C(E+G)+D(F+G))H ≡ A(B(EH+FH)+C(EH+GH)+D(FH+GH))
将是
- A
- B
- &E E
- &H H
- &F F
- *H
- C
- *E
- &G G
- *H
- D
- *F
- *G
（为了统一起见，如果生成它，每个原始节点都可以作为锚点。）
我不在乎图表是否是平面的，因为任何交叉链接都不是 "drawn"。
作为奖励，它允许指定附加到每个节点的数据，作为以节点为根的散列table。 （虽然超过了一定的大小，但分开放置数据可能会更清晰。）