CODEWITHSUNDEEP
algorithmgraph-algorithmdirected-acyclic-graphstopological-sort
Mo B.
Mo B.

Reputation: 5827

Topological sorting of a directed acyclic graph into stages

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

Upvotes: 3

Views: 900

Answers (2)

Rocco
Rocco

Reputation: 1118

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:

  2. Initialize the next set `S_n+1`
  3. 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`
  4. 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.

Upvotes: 3

David Eisenstat
David Eisenstat

Reputation: 65508

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.

Upvotes: 2

Related Questions