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

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 的节点（即没有输出的节点）添加到将表示顺序的列表中。对于曾经附加到列表中的每个节点，从与作为该节点输入的节点关联的值中减去一个。如果这些节点中的任何一个现在的值为零，则将它们也添加到列表中。重复做。只要您没有循环，就可以保证该过程最终终止，并且列表中的节点将以输入始终在输出之前的方式进行排序。

Answer 2

算法

拓扑排序确实是要走的路；根据您的要求，我不会写完整的实现。

大纲和注释

类型

首先，您将 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 添加多个节点

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

Sort nodes based on inputs / outputs

python

nodes

算法

大纲和注释

类型

输入和输出数据结构

预期结果

优化