Sort nodes based on inputs / outputs

Question

I have a node system where every node only stores its inputs and outputs, but not its index. Here is a simplified example:

class Node1:
    requiredInputs = []

class Node2:
    requiredInputs = ["Node1"]

class Node3:
    requiredInputs = ["Node2"]

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

Now I want to order that nodes, so that all inputs are already processed when processing that node. For this simple example, a possible order would be [Node1, Node2, Node3, Node4].

My first idea would be to use a brute force to check every possible combination. However, this will be very slow for a bigger number of nodes.

What would be a more efficient way to do this? I dont need an implementation, just a basic idea or algorithm.

Answer 1

What you want is to topologically sort the nodes.

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

The very basic idea would be to assign an integer to each node that is at the beginning equal to the number of outputs it has. Then add all the nodes with the value 0 (that is, those that have no outputs) to the list that will represent the order. For each node that is ever appended to the list, subtract one from the values associated with the nodes that are inputs to that node. If any of those nodes now have the value of zero, add them to the list as well. Repeat doing it. It is guaranteed that eventually the process terminates, as long as you don't have cycles, and that nodes in the list will be sorted in such a way that inputs always go before outputs.

Answer 2

Algorithm

Topological sort is indeed the way to go; Per your request, I will not write the full implementation.

Outline & notes

Types

First, you code store the requiredInputs as classes, not as strings. This will make the comparison way more elegant:

class Node1:
    requiredInputs = []

class Node2:
    requiredInputs = [Node1]

class Node3:
    requiredInputs = [Node2]

class Node4:
    requiredInputs = [Node3, Node2]

Input and output data structures

Then, you can place your nodes in two arrays, for input and output. This can be done in-place (using a single array), but it's rarely worth the trouble.

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

Here's the algorithm outline:

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

Expected result

When implemented, it should give:

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

Optimizations

There are quite a few ways to optimize or otherwise improve a topological sort. As before, I'll hint a few without disclosing any implementation.

• Pre-sorting the input array by some property
• Sorting in-place, with a single array
• Using a different data structure to represent the relations between nodes
• Adding more than one node to ordered_nodes at any iteration