基于输入/输出对节点排序

Question

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

class Node1:
    requiredInputs = []

class Node2:
    requiredInputs = ["Node1"]

class Node3:
    requiredInputs = ["Node2"]

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

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

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

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

Answer 1

算法

拓扑排序确实是一种方法；根据您的要求，我不会编写完整的实现。你知道吗

大纲和注释

类型

首先，将requiredInputs代码存储为类，而不是字符串。这将使比较方式更加优雅：

class Node1:
    requiredInputs = []

class Node2:
    requiredInputs = [Node1]

class Node3:
    requiredInputs = [Node2]

class Node4:
    requiredInputs = [Node3, Node2]

输入和输出数据结构

然后，您可以将节点放置在两个数组中，用于输入和输出。这可以就地完成（使用单个数组），但很少值得这么麻烦。你知道吗

unordered_nodes = [Node4, Node3, Node2, Node1]
ordered_nodes = []

算法概要如下：

while there are unordered_nodes:
    for each node N in unordered_nodes:
        if the requiredInputs of N are already in ordered_nodes:
            add N to ordered_nodes
            remove N from unordered_nodes
            break

预期结果

实施时，应提供：

print ordered_nodes
[<class __main__.Node1 at 0x10a7a8bb0>, 
 <class __main__.Node2 at 0x10a7a83f8>, 
 <class __main__.Node3 at 0x10a7a80b8>, 
 <class __main__.Node4 at 0x10a7a8600>]

优化

有很多方法可以优化或改进拓扑排序。和前面一样，我将在不透露任何实现的情况下给出一些提示。你知道吗

• 按某些属性对输入数组进行预排序
• 使用单个数组进行就地排序
• 使用不同的数据结构来表示节点之间的关系
• 在任何迭代中向ordered_nodes添加多个节点

Answer 2

您需要的是对节点进行拓扑排序。你知道吗

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

最基本的想法是给每个节点分配一个整数，这个整数在开始时等于它的输出数。然后将值为0的所有节点（即没有输出的节点）添加到表示顺序的列表中。对于曾经附加到列表的每个节点，从与作为该节点输入的节点关联的值中减去一个。如果这些节点中的任何一个现在的值为零，那么也将它们添加到列表中。重复做。只要您没有循环，就可以保证进程最终会终止，并且列表中的节点将以这样一种方式排序，即输入总是先于输出。你知道吗