No.11062205 ViewReplyOriginalReport
Ok /sci/, I need your help with finding an efficient algorithm.

I have a directed acyclic graph and I need to find layers in this graph, kinda like how a neural network has layers. I have a list of nodes and a list of 2-element tuples, with each tuple representing a connection.

Now I should mention that it is possible for nodes from non-adjacent layers to be connected to each other.

All I want is a list of lists, with each internal list representing a layer, and containing all the nodes within that layer. That's it.

Here's what I'm doing right now. Using the connection list, I'm creating two dicts, one that contains all origins of the incoming connections to a node and the other containing all the destinations of the outgoing connections from a node. To get my first layer, I simply pick those nodes from the node list, that don't have a key in the incoming dict. I maintain a set of previously grouped nodes at all times, and I initialize this set with the nodes of the first layer.

Now, for any given layer that is not the first layer, I find the set of all the outgoing nodes of the previously visited nodes. Now, if there are connections between the nodes of this newly created set, I remove the ends of those connections from the set. This final set is the next layer of nodes of the graph. I remove these nodes from the ultimate list of nodes, and I repeat the process until the ultimate list has no nodes remaining.

Now, is there a better, more efficient way to do this?