Topologically sort DAG into batches


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:

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
| sorting   | python   | graph   | algorithm   2016-11-16 22:11 0 Answers

Answers ( 0 )

◀ Go back