3

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]

enter image description here

2 Answers 2

3

Consider this variation of the canonical Kahn's algorithm:

  1. Start with a set `S_0` containing all nodes with no incoming edges
  2. Starting with n = 0:

  3. Initialize the next set `S_n+1`
  4. For each `n` in `S_n`:
    1. For all successors `d` of `n`, remove the edge `n -> d`
    2. If `d` has no other incoming edges add it to `S_n+1`
  5. If `S_n+1` is not empty, increase pass to n+1 and repeat from 2.

The list of S_0 ... S_k sets contains the result.

Sign up to request clarification or add additional context in comments.

2 Comments

I like this solution because it has optimal complexity, avoids recursion and unnecessary auxiliary bookkeeping.
A simple implementation, analogous to the solution proposed here, can be found in this SO post.
2

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.

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.