| 1 |
;;; |
| 2 |
;;; toposort.scm - topological sorting |
| 3 |
;;; |
| 4 |
;;; The original code was enhanced and became srfi-234. We keep this |
| 5 |
;;; as an adapter to srfi-234 for the backward compatibility. |
| 6 |
;;; Since the srfi-234 reference implementation refers to this file, |
| 7 |
;;; we keep the original code below, within the block comment. |
| 8 |
;;; |
| 9 |
|
| 10 |
(define-module util.toposort |
| 11 |
(use srfi.234 :rename ((topological-sort srfi-234:topological-sort))) |
| 12 |
(export topological-sort)) |
| 13 |
(select-module util.toposort) |
| 14 |
|
| 15 |
(define (topological-sort nodes :optional (eq eqv?)) |
| 16 |
(or (srfi-234:topological-sort nodes eq) |
| 17 |
(error "graph has circular dependency"))) |
| 18 |
|
| 19 |
#| |
| 20 |
|
| 21 |
;; The algorithm is loosely based on Algorithm T in TAOCP section 2.2.3. |
| 22 |
|
| 23 |
(define-module util.toposort |
| 24 |
(use scheme.list) |
| 25 |
(export topological-sort) |
| 26 |
) |
| 27 |
(select-module util.toposort) |
| 28 |
|
| 29 |
;; (topological-sort nodes &optional =) |
| 30 |
;; |
| 31 |
;; nodes : a list of (<from> <to0> <to1> ...) |
| 32 |
|
| 33 |
(define (topological-sort nodes :optional (eq eqv?)) |
| 34 |
(define table (map (^n (cons (car n) 0)) nodes)) |
| 35 |
(define queue '()) |
| 36 |
(define result '()) |
| 37 |
|
| 38 |
;; set up - compute number of nodes that each node depends on. |
| 39 |
(define (set-up) |
| 40 |
(dolist [node nodes] |
| 41 |
(dolist [to (cdr node)] |
| 42 |
(if-let1 p (assoc to table eq) |
| 43 |
(inc! (cdr p)) |
| 44 |
(push! table (cons to 1)))))) |
| 45 |
|
| 46 |
;; traverse |
| 47 |
(define (traverse) |
| 48 |
(unless (null? queue) |
| 49 |
(let1 n0 (assoc (pop! queue) nodes eq) |
| 50 |
(when n0 |
| 51 |
(dolist [to (cdr n0)] |
| 52 |
(and-let1 p (assoc to table eq) |
| 53 |
(let1 cnt (- (cdr p) 1) |
| 54 |
(when (= cnt 0) |
| 55 |
(push! result to) |
| 56 |
(push! queue to)) |
| 57 |
(set! (cdr p) cnt))))) |
| 58 |
(traverse)))) |
| 59 |
|
| 60 |
(set-up) |
| 61 |
(set! queue (append-map (^p (if (= (cdr p) 0) (list (car p)) '())) table)) |
| 62 |
(set! result queue) |
| 63 |
(traverse) |
| 64 |
(let1 rest (filter (^e (not (zero? (cdr e)))) table) |
| 65 |
(unless (null? rest) |
| 66 |
(error "graph has circular dependency" (map car rest)))) |
| 67 |
(reverse result)) |
| 68 |
|
| 69 |
|# |