1 | [[tags: egg]] |
---|

2 | [[toc:]] |
---|

3 | |
---|

4 | === Introduction |
---|

5 | |
---|

6 | A simple topological sorting routine. |
---|

7 | |
---|

8 | The 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. |
---|

16 | The cdr is the adjacency list of that vertex, i.e. a list of all |
---|

17 | vertices to which there exists an edge from the car vertex. |
---|

18 | |
---|

19 | {{PRED}} is an equality predicate (like {{eq?}} or {{string=?}}). |
---|

20 | |
---|

21 | Sort the directed acyclic graph DAG so that for every edge from vertex |
---|

22 | U to V, U will come before V in the resulting list of vertices. |
---|

23 | |
---|

24 | Time complexity: O (|V| + |E|) |
---|

25 | |
---|

26 | Example (from Cormen): |
---|

27 | |
---|

28 | Prof. Bumstead topologically sorts his clothing when getting dressed. |
---|

29 | The first argument to {{topological-sort}} describes which garments he |
---|

30 | needs to put on before others. (For example, Prof Bumstead needs to |
---|

31 | put 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 | |
---|

50 | === License |
---|

51 | |
---|

52 | This code is in the public domain. |
---|

53 | |
---|

54 | Copyright (C) 1995 Mikael Djurfeldt |
---|

55 | |
---|

56 | === History |
---|

57 | |
---|

58 | ; 1.1 : compiler declarations [Kon Lovett] |
---|

59 | ; 1.0 : initial release |
---|