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)