6.11 mischief/sort: Topological Sorting
| (require mischief/sort) | package: mischief-dev |
procedure
(topological-sort nodes neighbors [ #:cycle cycle]) → list? nodes : list? neighbors : (-> any/c list?)
cycle : (-> list? none/c) =
(lambda {xs} (error 'topological-sort "cycle detected: ~v" xs))
Topologically sorts the values in nodes, interpreted as a graph where
each node’s neighbors are determined by neighbors. If a cycle is
encountered, an error is raised using cycle.
Examples:
> (define nodes '(a b c d))
> (define neighbors (dict->procedure #:failure (const empty) (hash 'a '(b c) 'b '(d) 'c '(d)))) > (topological-sort nodes neighbors) '(d b c a)