Debian Codegraph @

lib/util/toposort.scm

raw
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 |#