依赖多图：具有重复边的图的拓扑排序和评估

Question

我有一个依赖图，其中一个节点需要前一个节点的两个副本才能满足。我想使用拓扑排序来获得评估顺序，但问题是拓扑排序忽略了平行/多边，而只是将其视为一种依赖关系。我的建模是否错误，或者我是否需要一个适用于多重图的特定拓扑排序？

Answer 1

这可以通过修改拓扑排序算法来完成。

\n\n

原始算法存储所有没有传入边的节点（S）的集合，主要步骤是从 S 中取出一个节点，将其从 S 中删除，然后从图中删除它的所有边，并检查是否还有其他没有传入的节点边缘。

\n\n

将其更改为：从 S 中取出一个节点，删除每个邻居的一个边实例，如果节点没有传出边，则将其从 S 中删除，检查是否有其他节点没有传入边。

\n\n

维基百科原始代码：

\n\n

L \xe2\x86\x90 Empty list that will contain the sorted elements\nS \xe2\x86\x90 Set of all nodes with no incoming edges\nwhile S is non-empty do\n    remove a node n from S\n    add n to tail of L\n    for each node m with an edge e from n to m do\n        remove edge e from the graph\n        if m has no other incoming edges then\n            insert m into S\n

\n\n

改变的算法：

\n\n

L \xe2\x86\x90 Empty list that will contain the sorted elements\nS \xe2\x86\x90 Set of all nodes with no incoming edges\nwhile S is non-empty do\n    take a node n from S\n    add n to tail of L\n    for each neighbouring node m of n\n        remove ONE edge (m,n) from the graph\n        if m has no other incoming edges then\n            insert m into S\n    if n doesn\'t have outgoing edges\n       remove n from S\n

\n