## Topologically sort DAG into batches

Question

I'm looking for an algorithm to sort a DAG into batches of vertices, such that no vertices in a batch have an edge between them, and the batches are sorted in an order such that no vertex in a batch has an edge to a batch after it in the sorting order. I can't seem to come up with an efficient modification of a generic topological sort, because to discover what batch to put a vertex in, you must fill all batches before the one it belongs in. Effectively:

```
batches = []
while vertices:
batch = []
for v in vertices.copy():
for v' in v.edges:
if v' in vertices:
break
else:
batch.append(v)
vertices.remove(v)
batches.append(batch)
```

However, this algorithm is `O(n^2)`

for a reverse sorted 'linear' graph *with* a hash table for vertex lookup.

Sorry for the pythonic pseudocode.

Show source

## Answers ( 0 )