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.