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

Answers to Topologically sort DAG into batches ( 0 )

Leave a reply to - Topologically sort DAG into batches

◀ Go back