1.4.2 Topological Sorting

Problem Input | Problem Output

INPUT                    OUTPUT


Input Description: A directed, acyclic graph G=(V,E) (also known as a partial order or poset).

Problem: Find a linear ordering of the vertices of V such that for each edge (i,j) \in E, vertex i is to the left of vertex j.

Excerpt from The Algorithm Design Manual: Topological sorting arises as a natural subproblem in most algorithms on directed acyclic graphs. Topological sorting orders the vertices and edges of a DAG in a simple and consistent way and hence plays the same role for DAGs that depth-first search does for general graphs.

Topological sorting can be used to schedule tasks under precedence constraints. Suppose we have a set of tasks to do, but certain tasks have to be performed before other tasks. These precedence constraints form a directed acyclic graph, and any topological sort (also known as a linear extension) defines an order to do these tasks such that each is performed only after all of its constraints are satisfied.

The best book available for this problem is Leda : A Platform for Combinatorial and Geometric Computing by Kurt Mehlhorn and Stefan Naher.


Implementations

  • LEDA - A Library of Efficient Data Types and Algorithms (C++) (rating 7)
  • Algorithms in C++ -- Sedgewick (C++) (rating 3)
  • Moret and Shapiro's Algorithms P to NP (Pascal) (rating 3)
  • The Stanford GraphBase (C) (rating 3)
  • Combinatorica (Mathematica) (rating 3)
  • Xtango and Polka Algorithm Animation Systems (C++) (rating 2)

    Related Problems

  • Bandwidth Reduction
  • Feedback Edge/Vertex Set
  • Job Scheduling
  • Sorting


    Previous Problem Next Problem

    View the graph for this file

    Bulletin Board
    About ``The Algorithm Design Manual''.
    Send us Mail
    The Stony Brook Algorithm Repository -- go to front page

    This page last modified on Wed Mar 07, 2001 .