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

`(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: