| 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)))))))) |