Debian Codegraph @

lib/srfi/234.scm

raw
1 ;;; SPDX-FileCopyrightText: 2024 Shiro Kawai, John Cowan, Arne Babenhauserheide
2 ;;; SPDX-License-Identifier: MIT
3
4 ;;; Code adapted from gauche https://github.com/shirok/Gauche/blob/master/lib/util/toposort.scm :
5 ;;;
6 ;;; srfi-234.scm - topological sorting
7 ;;;
8 ;;; Written by Shiro Kawai ([email protected]) 2001
9 ;;; Arne Babenhauserheide 2023--2024
10 ;;; Public Domain.
11
12 (define-module srfi.234
13 (export topological-sort topological-sort/details
14 edgelist->graph edgelist/inverted->graph
15 graph->edgelist graph->edgelist/inverted
16 connected-components)
17 )
18 (select-module srfi.234)
19
20
21 (define topological-sort
22 (case-lambda
23 ((graph) (topological-sort-impl graph equal? #f))
24 ((graph eq) (topological-sort-impl graph eq #f))
25 ((graph eq nodes) (topological-sort-impl graph eq nodes))))
26
27 (define topological-sort/details
28 (case-lambda
29 ((graph) (topological-sort-impl/details graph equal? #f))
30 ((graph eq) (topological-sort-impl/details graph eq #f))
31 ((graph eq nodes) (topological-sort-impl/details graph eq nodes))))
32
33 (define (topological-sort-impl graph eq nodes)
34 (let-values (((v0 v1 v2)
35 (topological-sort-impl/details graph eq nodes)))
36 v0))
37
38 (define (topological-sort-impl/details graph eq nodes)
39 (define table (map (lambda (n)
40 (cons (car n) 0))
41 graph))
42 (define queue '())
43 (define result '())
44
45 ;; set up - compute number of nodes that each node depends on.
46 (define (set-up)
47 (for-each
48 (lambda (node)
49 (for-each
50 (lambda (to)
51 (define p (assoc to table eq))
52 (if p
53 (set-cdr! p (+ 1 (cdr p)))
54 (set! table (cons
55 (cons to 1)
56 table))))
57 (cdr node)))
58 graph))
59
60 ;; traverse
61 (define (traverse)
62 (unless (null? queue)
63 (let ((n0 (assoc (car queue) graph eq)))
64 (set! queue (cdr queue))
65 (when n0
66 (for-each
67 (lambda (to)
68 (define p (assoc to table eq))
69 (when p
70 (let ((cnt (- (cdr p) 1)))
71 (when (= cnt 0)
72 (set! result (cons to result))
73 (set! queue (cons to queue)))
74 (set-cdr! p cnt))))
75 (cdr n0)))
76 (traverse))))
77
78 (set-up)
79 (set! queue
80 (apply append
81 (map
82 (lambda (p)
83 (if (= (cdr p) 0)
84 (list (car p))
85 '()))
86 table)))
87 (set! result queue)
88 (traverse)
89 (let ((rest (filter (lambda (e)
90 (not (zero? (cdr e))))
91 table)))
92 (if (null? rest)
93 (values
94 (if nodes
95 ;; replace indizes by node values
96 (let loop ((res '()) (result result))
97 (if (null? result)
98 res
99 (loop (cons (vector-ref nodes (car result)) res)
100 (cdr result))))
101 (reverse result))
102 #f #f)
103 (values #f "graph has circular dependency" (map car rest)))))
104
105 ;; Calculate the connected components from a graph of in-neighbors
106 ;; implements Kosaraju's algorithm: https://en.wikipedia.org/wiki/Kosaraju%27s_algorithm
107 (define (connected-components graph)
108 ;; graph of out-neighbors
109 (define graph/inverted (edgelist->graph (graph->edgelist/inverted graph)))
110 ;; for simplicity this uses a list of nodes to query for membership. This is expensive.
111 (define visited '())
112 (define vertex-list '())
113 ;; create vertex-list sorted with outbound elements first
114 (define (visit! node)
115 (cond ((member node visited) '())
116 (else
117 ;; mark as visited before traversing
118 (set! visited (cons node visited))
119 ;; this uses the graph: the outbound connections
120 (let ((node-in-graph (assoc node graph)))
121 (when node-in-graph
122 (for-each visit! (cdr node-in-graph))))
123 ;; add to list after traversing
124 (set! vertex-list (cons node vertex-list)))))
125 ;; for simplicity this uses a list of nodes to query for membership. This is expensive.
126 (define in-component '())
127 (define components '())
128 ;; assign nodes to their components
129 (define (assign! u root)
130 (unless (member u in-component)
131 (set! in-component (cons u in-component))
132 (set! components (cons (cons u (car components)) (cdr components)))
133 ;; this uses the graph/inverted: the inbound connections
134 (let ((node-in-graph (assoc u graph/inverted)))
135 (when node-in-graph
136 (for-each (cut assign! <> root) (cdr node-in-graph))))))
137 (define (assign-as-component! u)
138 (unless (member u in-component)
139 (set! components (cons '() components))
140 (assign! u u)))
141 ;; We visit all vertices. The next expression may call visit! on
142 ;; the same node more than once, but second time and after is no-op.
143 (for-each (lambda (g) (for-each visit! g)) graph)
144 (for-each assign-as-component! vertex-list)
145 components)
146
147 ;; convert an edgelist '((a b) (a c) (b e)) to a graph '((a b c) (b e))
148 (define edgelist->graph
149 (case-lambda
150 ((edgelist) (edgelist->graph-impl edgelist assoc))
151 ((edgelist asc) (edgelist->graph-impl edgelist asc))))
152 (define (edgelist->graph-impl edgelist asc)
153 (let loop ((graph '()) (edges edgelist))
154 (cond
155 ((null? edges) (reverse! graph))
156 ((asc (car (car edges)) graph)
157 (let* ((edge (car edges))
158 (left (car edge))
159 (graph-entry (asc left graph))
160 (right (car (cdr edge))))
161 ;; adjust the right-most cdr
162 (let lp ((entry graph-entry))
163 (if (null? (cdr entry))
164 (set-cdr! entry (list right))
165 (lp (cdr entry))))
166 (loop graph (cdr edges))))
167 ;; use apply list to break up immutable pairs
168 (else (loop (cons (apply list (car edges)) graph) (cdr edges))))))
169
170 ;; convert an inverted edgelist '((b a) (c a) (e b)) to a graph '((a b c) (b e))
171 (define edgelist/inverted->graph
172 (case-lambda
173 ((edgelist) (edgelist/inverted->graph-impl edgelist assoc))
174 ((edgelist asc) (edgelist/inverted->graph-impl edgelist asc))))
175 (define (edgelist/inverted->graph-impl edgelist asc)
176 (let loop ((graph '()) (edges edgelist))
177 (cond
178 ((null? edges) (reverse! graph))
179 ((asc (car (cdr (car edges))) graph)
180 (let* ((edge (car edges))
181 (left (car (cdr edge)))
182 (graph-entry (asc left graph))
183 (right (car edge)))
184 ;; adjust the right-most cdr
185 (let lp ((entry graph-entry))
186 (if (null? (cdr entry))
187 (set-cdr! entry (list right))
188 (lp (cdr entry))))
189 (loop graph (cdr edges))))
190 ;; reverse instead of reverse! to avoid immutable lists
191 (else (loop (cons (reverse (car edges)) graph) (cdr edges))))))
192
193 (define (graph->edgelist graph)
194 (graph->edgelist/base graph (lambda (top) (list (car top) (car (cdr top))))))
195
196 (define (graph->edgelist/inverted graph)
197 (graph->edgelist/base graph (lambda (top) (list (car (cdr top)) (car top)))))
198
199 (define (graph->edgelist/base graph top-to-edge-fun)
200 (let loop ((edgelist '()) (graph graph))
201 (cond ((null? graph)
202 (reverse! edgelist))
203 ((null? (car graph))
204 (loop edgelist (cdr graph)))
205 ((null? (cdr (car graph)))
206 (loop edgelist (cdr graph)))
207 (else
208 (let* ((top (car graph))
209 (edge (top-to-edge-fun top))
210 (rest (cdr (cdr top))))
211 (loop (cons edge edgelist)
212 (cons (cons (car top) rest) (cdr graph))))))))