You are looking at historical revision 3915 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.1
- compiler declarations [Kon Lovett]
- 1.0
- initial release