graph - 依赖多图 : Topological Sort and evaluation of graphs with duplicate edges

Question

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

Answer 1

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

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

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

原码来自 Wikipedia :

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

改变算法:

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