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

Question

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

Answer 1

It can be done with modification of topological sort algorithm.

Original algorithm stores set of all nodes with no incoming edges (S), and main step is to take one node from S, removes it from S, and remove all of it's edges from graph and check are there other nodes without incoming edges.

Changing that to: take one node from S, remove one instance of edge to each neighbour, if node doesn't have outgoing edges remove it from S, check are there other nodes without incoming edges.

Code of original from 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

Changed algorithm:

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