基于输入/输出排序节点

Question

我有一个节点系统，每个节点只存储其输入和输出，而不是它的索引。这里是一个简化的例子：

class Node1:
    requiredInputs = []

class Node2:
    requiredInputs = ["Node1"]

class Node3:
    requiredInputs = ["Node2"]

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

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

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

有什么更有效的方法吗？我不需要实现，只需要基本的思路或算法。

- tobspr

---

这里使用有向图作为数据结构不是更好吗？ - James Mills

提示：拓扑排序 - thefourtheye

很遗憾，我无法修改输入结构。 - tobspr

因此，根据输入的数据结构创建一个新的数据结构基础。 - James Mills

向他人寻求提示而非完整实现是正解。 - Adam Matan

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添加多个节点

- Adam Matan

---

感谢您详细的回答！ :) 节点只是一个例子，所以我在那里使用了字符串 :) - tobspr

Answer 2

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

基本思路是给每个节点分配一个整数，一开始等于其输出数量。然后将所有值为 0 （即没有输出）的节点添加到代表顺序的列表中。对于每个附加到列表的节点，从输入到该节点的节点关联的值中减去 1。如果这些节点中的任何一个现在都有零值，则也将它们添加到列表中。重复此过程。只要不存在循环，就保证最终会终止该进程，并且列表中的节点将以使输入始终出现在输出之前的方式进行排序。

参考链接：http://en.wikipedia.org/wiki/Topological_sorting。

- Ishamael

---

谢谢，那正是我需要的提示！ :) - tobspr