Topological Sort with Grouping

Label all root nodes with a level value 0. Label all children with level value parent+1. If, a node is being revisited i.e it already has a level value assigned, check if the previously assigned value is lower than the new one. If so, update it with the higher value and propagate them to the descendents.

now, you have as many groups as there are unique level labels 0 ... K

I recently implemented this algorithm. I started with the approach you have shown, but it didn't scale to graphs of 20+ million nodes. The solution I ended up with is based on the approach detailed here.

You can think of it as computing the height of each node, and then the result is a group of each node at a given height.

Consider the graph:

A -> X

B -> X

X -> Y

X -> Z

So the desired output is (A,B), (X), (Y, Z)

The basic approach is to find everything with nothing using it(A,B in this example). All of these are at height 0.

Now remove A and B from the graph, find anything that now has nothing using it(now X in this example). So X is at height 1.

Remove X from the graph, find anything that now has nothing using it(now Y,Z in this example). so Y,Z are at height 2.

You can make an optimization by realizing the fact that you don't need to store bidirectional edges for everything or actually remove anything from your graph, you only need to know the number of things pointing to a node and the nodes you know are at the next height.

So for this example at the start:

• 0 things use 1
• 0 things use 2
• 2 things use X (1 and 2)
• 1 things use Y,Z (X)

When you visit a node, decrease the number of each of the nodes it points to, if that number goes to zero, you know that node is at the next height.