使用Python实现卡恩拓扑排序算法

Kahn 在 62 中提出了一个算法拓扑排序任何 DAG（有向无环图），从维基百科复制的伪代码：

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  # This is a DESTRUCTIVE step!
        if m has no other incoming edges then
            insert m into S if graph has edges then
    return error (graph has at least one cycle) else 
    return L (a topologically sorted order)

我需要使用 IPython3 来实现它，并使用以下 DAG 实现：

class Node(object):
    def __init__(self, name, parents):
        assert isinstance(name, str)
        assert all(isinstance(_, RandomVariable) for _ in parents)
        self.name, self.parents = name, parents

where name是节点的标签，parents存储其所有父节点。那么DAG类的实现如下：

class DAG(object):
    def __init__(self, *nodes):
        assert all(isinstance(_, Node) for _ in nodes)
        self.nodes = nodes

（DAG 实现是固定的，无需改进。）然后我需要将卡恩算法实现为函数top_order它接受一个 DAG 实例并返回一个类似于(node_1, node_2, ..., node_n)。主要的问题是，该算法具有破坏性，因为它的步骤之一是remove edge e from the graph（第 5 行）这将删除 的一名成员m.parents。然而，我必须保持 DAG 实例完好无损.

到目前为止我能想到的一种方法是创建一个deep获取DAG实例的副本（即使是浅副本也无法完成这项工作，因为算法仍然通过引用破坏原始实例），并对这个副本执行破坏性算法，然后得到这个节点名称的正确顺序复制（假设节点之间不存在命名冲突），然后使用此名称顺序来推断原始实例的节点的正确顺序，大致如下：

def top_order(network):
    '''takes in a DAG, prints and returns a topological ordering.'''
    assert type(network) == DAG
    temp = copy.deepcopy(network) # to leave the original instance intact

    ordering_name = []
    roots = [node for node in temp.nodes if not node.parents]
    while roots:
        n_node = roots[0]
        del roots[0]
        ordering_name.append(n_node.name)
        for m_node in temp.nodes:
            if n_node in m_node.parents:
                temp_list = list(m_node.parents)
                temp_list.remove(n_node)
                m_node.parents = tuple(temp_list)
                if not m_node.parents:
                    roots.append(m_node)

    print(ordering_name) # print ordering by name

    # gets ordering of nodes of the original instance
    ordering = []
    for name in ordering_name:
        for node in network.nodes:
            if node.name == name:
                ordering.append(node)

    return tuple(ordering)

两个问题：第一，什么时候network巨大时深拷贝会消耗资源；其次，我想要改进我的嵌套for循环获取原始实例的顺序。 （对于第二个我认为类似sorted方法等突然出现在我的脑海中。）

有什么建议吗？

我将建议一种不那么字面意义的算法实现：你根本不需要操作 DAG，你只需要操作信息about有向无环图。该算法需要的唯一“有趣”的东西是从节点到其子节点的映射（与 DAG 实际存储的相反），以及每个节点的父节点数量的计数。

这些很容易计算，并且可以使用字典将此信息与节点名称相关联（假设所有名称都是不同的 - 如果不是，您可以使用更多代码来发明唯一的名称）。

那么这应该有效：

def topsort(dag):
    name2node = {node.name: node for node in dag.nodes}
    # map name to number of predecessors (parents)
    name2npreds = {}
    # map name to list of successors (children)
    name2succs = {name: [] for name in name2node}

    for node in dag.nodes:
        thisname = node.name
        name2npreds[thisname] = len(node.parents)
        for p in node.parents:
            name2succs[p.name].append(thisname)

    result = [n for n, npreds in name2npreds.items() if npreds == 0]
    for p in result:
        for c in name2succs[p]:
            npreds = name2npreds[c]
            assert npreds
            npreds -= 1
            name2npreds[c] = npreds
            if npreds == 0:
                result.append(c)

    if len(result) < len(name2node):
        raise ValueError("no topsort - cycle")
    return tuple(name2node[p] for p in result)

这里有一个微妙的点：外循环附加到result while它正在迭代result。这是故意的。效果是每个元素result无论元素是否在初始元素中，外循环都会只处理一次result或稍后添加。

请注意，虽然输入DAG and Nodes 被遍历，其中没有任何内容被改变。