Feb-17-2021, 08:05 PM
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.
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)