![]() |
Sorting problem - Printable Version +- Python Forum (https://python-forum.io) +-- Forum: Python Coding (https://python-forum.io/forum-7.html) +--- Forum: General Coding Help (https://python-forum.io/forum-8.html) +--- Thread: Sorting problem (/thread-32555.html) |
Sorting problem - deanhystad - Feb-17-2021 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) RE: Sorting problem - Gribouillis - Feb-17-2021 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. RE: Sorting problem - deanhystad - Feb-17-2021 Thanks. Just the guidance I was hoping for. |