# source:project/wiki/eggref/3/topological-sort@13621

Last change on this file since 13621 was 13621, checked in by sjamaan, 11 years ago

Move old chicken 3 eggs over to eggref/3

File size: 1.4 KB
Line
1[[tags: egg]]
2[[toc:]]
3
4=== Introduction
5
6A simple topological sorting routine.
7
8The algorithm is inspired by Cormen, Leiserson and Rivest (1990)
9`Introduction to Algorithms', chapter 23.
10
11=== topological-sort
12
13  [procedure] (topological-sort DAG PRED)
14
15{{DAG}} is a list of sublists.  The car of each sublist is a vertex.
16The cdr is the adjacency list of that vertex, i.e. a list of all
17vertices to which there exists an edge from the car vertex.
18
19{{PRED}} is an equality predicate (like {{eq?}} or {{string=?}}).
20
21Sort the directed acyclic graph DAG so that for every edge from vertex
22U to V, U will come before V in the resulting list of vertices.
23
24Time complexity: O (|V| + |E|)
25
26Example (from Cormen):
27
28Prof. Bumstead topologically sorts his clothing when getting dressed.
29The first argument to {{topological-sort}} describes which garments he
30needs to put on before others.  (For example, Prof Bumstead needs to
31put on his shirt before he puts on his tie or his belt.)
32{{topological-sort}} gives the correct order of dressing:
33
34<enscript highlight=scheme>
35(topological-sort
36  '((shirt tie belt)
37    (tie jacket)
38    (belt jacket)
39    (watch)
40    (pants shoes belt)
41    (undershorts pants shoes)
42    (socks shoes))
43  eq?)
44
45=>
46
47(socks undershorts pants shoes watch shirt belt tie jacket)
48</enscript>
49