Outdated egg!

This is an egg for CHICKEN 3, the unsupported old release. You're almost certainly looking for the CHICKEN 4 version of this egg, if it exists.

If it does not exist, there may be equivalent functionality provided by another egg; have a look at the egg index. Otherwise, please consider porting this egg to the current version of CHICKEN.

Outdated egg!

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.

History

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