Sorting problem

[deanhystad]

I am trying to sort by dependency. I get the feeling this is a solved problem, so before digging in I thought I'd ask here if anyone can point me at a solution.

Description
I have Node objects with dependencies. Node.inp is a list of nodes the node depends on. Node.out is a list of nodes that depend on node. I want to sort a list of nodes so all the nodes in node.inp appear before the node in the list.

I wrote a little program that creates a list of nodes and calls a sort function. Currently the function is a stub, but I think the code does a better job describing the dependencies than my explanation.

import random

class Node:
    instances = [] # List of all Node objects

    def __init__(self):
        self.id = len(self.instances)
        self.inp = []  #Nodes I depend on
        self.out = []  #Nodes that depend on me
        self.instances.append(self)

    def connect(self, node):
        """Create a dependency.  node depends on me"""
        self.out.append(node)
        node.inp.append(self)

    def __repr__(self):
        out = ','.join([str(x.id) for x in self.out])
        return f'(Node {self.id}:{out})'

def dependency_sort(nodes):
   """Sort nodes so all dependencies (node.inp) appear before
   node in the list.
   """
   # TBD
   return nodes

def verify(nodes):
    """Test if any nodes are out of order"""
    for i, node in enumerate(nodes):
        for out in node.out:
            if out in nodes[:i]:
                print(f'Node {node.id} references Node {out.id}')

# Create some nodes
for _ in range(5):
    Node()
nodes = Node.instances

# Create some random dependencies
random_order = random.sample(nodes, k=len(nodes))
prev = None
for node in random_order:
    if prev:
        prev.connect(node)
    prev = node

# Sort nodes by dependency
sorted_nodes = dependency_sort(nodes)

print('Original', nodes, '\n')
print('Desired ', random_order, '\n')
print('Sorted  ', sorted_nodes, '\n')

verify(sorted_nodes)

[Gribouillis]

I think you are implementing a topological sorting algorithm. It is a well known problem with many Python implementations. If you are ready to use a graph library such as networkx, it already contains a function for this. You could also have a look in some pypi modules such as toposort for example.

[deanhystad]

Thanks. Just the guidance I was hoping for.