You are looking at historical revision 3883 of this page. It may differ significantly from its current revision.

Introduction

A simple topological sorting routine.

The algorithm is inspired by Cormen, Leiserson and Rivest (1990) `Introduction to Algorithms', chapter 23.

topological-sort

 [procedure] (topological-sort DAG PRED)

DAG is a list of sublists. The car of each sublist is a vertex. The cdr is the adjacency list of that vertex, i.e. a list of all vertices to which there exists an edge from the car vertex.

PRED is an equality predicate (like eq? or string=?).

Sort the directed acyclic graph DAG so that for every edge from vertex U to V, U will come before V in the resulting list of vertices.

Time complexity: O (|V| + |E|)

Example (from Cormen):

Prof. Bumstead topologically sorts his clothing when getting dressed. The first argument to topological-sort describes which garments he needs to put on before others. (For example, Prof Bumstead needs to put on his shirt before he puts on his tie or his belt.) topological-sort gives the correct order of dressing:

(topological-sort
  '((shirt tie belt)
    (tie jacket)
    (belt jacket)
    (watch)
    (pants shoes belt)
    (undershorts pants shoes)
    (socks shoes))
  eq?)

=>

(socks undershorts pants shoes watch shirt belt tie jacket)

License

This code is in the public domain.

Copyright (C) 1995 Mikael Djurfeldt

History

1.0
initial release