**Note: **This is taken from the Chicken Wiki, where a more recent version could be available.

## 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 © 1995 Mikael Djurfeldt

## History

- 1.1
- compiler declarations [Kon Lovett]
- 1.0
- initial release