Next: , Previous: , Up: Sorting and Searching   [Contents][Index]

#### 7.2.5 Topological Sort

`(require 'topological-sort)` or `(require 'tsort)`

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

Function: tsort dag pred
Function: topological-sort dag pred

where

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 one of `eq?`, `eqv?`, `equal?`, `=`, `char=?`, `char-ci=?`, `string=?`, or `string-ci=?`.

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 `tsort` 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.) `tsort` gives the correct order of dressing:

```(require 'tsort)
(tsort '((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)
```