You can edit this page using wiki syntax for markup.

Article contents:== Outdated egg! This is an egg for CHICKEN 3, the unsupported old release. You're almost certainly looking for [[/eggref/4/topological-sort|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 [[https://wiki.call-cc.org/chicken-projects/egg-index-4.html|egg index]]. Otherwise, please consider porting this egg to the current version of CHICKEN. [[tags: egg]] [[toc:]] === 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: <enscript highlight=scheme> (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) </enscript> === License This code is in the public domain. Copyright (C) 1995 Mikael Djurfeldt === History ; 1.1 : compiler declarations [Kon Lovett] ; 1.0 : initial release Description of your changes:

I would like to authenticate

Spam control

What do you get when you add 22 to 20?