python - 根据输入/输出对节点进行排序

Question

我有一个节点系统，其中每个节点仅存储其输入和输出，而不存储其索引。这是一个简化的示例:

class Node1:
    requiredInputs = []

class Node2:
    requiredInputs = ["Node1"]

class Node3:
    requiredInputs = ["Node2"]

class Node4:
    requiredInputs = ["Node3", "Node2"]

现在我想对这些节点进行排序，以便在处理该节点时已经处理了所有输入。对于这个简单的例子，可能的顺序是 [Node1, Node2, Node3, Node4]。

我的第一个想法是使用蛮力来检查每个可能的组合。但是，对于更多的节点，这将非常慢。

什么是更有效的方法来做到这一点？我不需要实现，只需要一个基本的想法或算法。

Answer 1

您想要的是对节点进行拓扑排序。

http://en.wikipedia.org/wiki/Topological_sorting

非常基本的想法是为每个节点分配一个整数，该整数在开始时等于它具有的输出数。然后添加所有值为 0 的节点(即那些没有输出的)到将代表订单的列表。对于曾经附加到列表的每个节点，从与作为该节点输入的节点关联的值中减去一个。如果这些节点中的任何一个现在具有零值，也将它们添加到列表中。重复做。只要您没有循环，就可以保证最终过程终止，并且列表中的节点将以这样一种方式排序，即输入总是在输出之前。