Topological sorting of a directed acyclic graph into stages

Question

Is there an algorithm that, given an unweighted directed acyclic graph, sorts all nodes into a list of sets of nodes such that

1. the topological order is preserved (i.e., for all edges u->v, v occurs in a set further down the list than u) and
2. the length of the list is minimal.

Is there a name for this problem?

Example

A possible sort for the graph below would be

[1], [2, 3], [4, 5], [6, 7]

An alternative solution would be

[1], [2, 3], [4], [5, 6, 7]

Answer 1

Define the stage index of each node to be zero if it has no predecessors, or one plus the max stage index of its predecessors. Put each node in the indicated stage.

The stage indices can be evaluated efficiently in topological order, making this an easy extension to your favorite topological sorting algorithm.

Answer 2

Consider this variation of the canonical Kahn's algorithm:

1. Start with a set S0 containing all nodes with no incoming edges
2. Initialize the next set Sn+1
3. Iterate over Sn, for each node N:
1. For all nodes D with an incoming edge from N, remove the edge
2. If D has no other incoming edges add it to Sn+1
4. If Sn+1 is not empty, increase pass to n+1 and repeat from 2.

The list of S0 ... Sk sets contains the result.