Debian Codegraph @

test/include/srfi-234-test.scm

raw
1 ;;; SPDX-FileCopyrightText: 2024 Shiro Kawai, John Cowan, Arne Babenhauserheide
2 ;;; SPDX-License-Identifier: MIT
3
4 (cond-expand
5 (guile
6 (import (scheme base)
7 (srfi 234)
8 (srfi 1)
9 (srfi srfi-64)))
10 (chibi
11 (import (scheme base)
12 (srfi 234)
13 (srfi 1)
14 (srfi 11) ;; let-values
15 (rename (except (chibi test) test-equal)
16 (test test-equal))))
17 (chicken
18 (load "srfi/srfi-234.so")
19 (import (scheme base)
20 (srfi 234)
21 (srfi 1)
22 (srfi 64)))
23 (else
24 (import (scheme base)
25 (srfi 234)
26 (srfi 1)
27 (srfi 64))))
28
29
30 (test-begin "srfi-234")
31
32 (test-equal
33 '(a b d c)
34 (topological-sort '((a b c)
35 (b d)
36 (c)
37 (d c))))
38
39 ;; details: multiple values
40 (test-equal
41 '((a b d c) #f #f)
42 (let-values
43 (((v0 v1 v2)
44 (topological-sort/details '((a b c)
45 (b d)
46 (c)
47 (d c)))))
48 (list v0 v1 v2)))
49
50 ;; cycle
51 (test-equal
52 #f
53 (topological-sort '((a b)
54 (b a))))
55
56 ;; cycle error details
57 (test-equal
58 '(#f "graph has circular dependency" (a b))
59 (let-values
60 (((v0 v1 v2)
61 (topological-sort/details '((a b)
62 (b a)))))
63 (list v0 v1 v2)))
64
65 (test-equal
66 '("a" "b" "d" "c")
67 (topological-sort '(("a" "b" "c")
68 ("b" "d")
69 ("c")
70 ("d" "c"))
71 string=?))
72
73 (test-equal
74 '((a b c) (b e))
75 (edgelist->graph '((a b) (a c) (b e))))
76
77 (test-equal
78 '((a b) (a c) (b e))
79 (graph->edgelist '((a b c) (b e))))
80
81 (test-equal
82 '((a b c) (b e))
83 (edgelist/inverted->graph '((b a) (c a) (e b))))
84
85 (test-equal
86 '((b a) (c a) (e b))
87 (graph->edgelist/inverted '((a b c) (b e))))
88
89 (test-equal
90 '((0 1) (1 2) (2 0) (3 1 2 4) (4 3 5) (5 2 6) (6 5) (7 4 6 7))
91 (edgelist->graph '((0 1)
92 (1 2)
93 (2 0)
94 (3 1) (3 2) (3 4)
95 (4 3) (4 5)
96 (5 2) (5 6)
97 (6 5)
98 (7 4) (7 6) (7 7))))
99
100 (test-equal
101 '((1 0 3) (2 1 3 5) (0 2) (4 3 7) (3 4) (5 4 6) (6 5 7) (7 7))
102 (edgelist/inverted->graph '((0 1)
103 (1 2)
104 (2 0)
105 (3 1) (3 2) (3 4)
106 (4 3) (4 5)
107 (5 2) (5 6)
108 (6 5)
109 (7 4) (7 6) (7 7))))
110
111 (test-assert
112 (lset= (lambda (a b) (lset= eqv? a b))
113 '((1) (2))
114 (connected-components '((1 2)))))
115
116 (test-assert
117 (lset= (lambda (a b) (lset= eqv? a b))
118 '((1 2))
119 (connected-components '((1 2) (2 1)))))
120
121 (test-assert
122 (lset= (lambda (a b) (lset= eqv? a b))
123 '((1 2) (3 4))
124 (connected-components '((1 2 3 4)
125 (2 1 3)
126 (3 4)
127 (4 3)))))
128
129 (test-assert
130 (lset= (lambda (a b) (lset= eqv? a b))
131 '((1) (2) (3) (4))
132 (connected-components '((1 2 3 4)
133 (2 3)
134 (3 4)))))
135
136 (test-assert
137 (lset= (lambda (a b) (lset= eqv? a b))
138 '((2 0 1) (6 5) (3 4) (7))
139 (connected-components
140 (edgelist->graph '((0 1)
141 (1 2)
142 (2 0)
143 (3 1) (3 2) (3 4)
144 (4 3) (4 5)
145 (5 2) (5 6)
146 (6 5)
147 (7 4) (7 6) (7 7))))))
148
149 (define (permutations edgelist)
150 (if (null? edgelist) '(())
151 (apply append
152 (map (lambda (edge)
153 (map (lambda (permutation)
154 (cons edge permutation))
155 (permutations (delete edge edgelist))))
156 edgelist))))
157
158 (test-equal #t
159 (every (lambda (edgelist)
160 (let* ((graph (edgelist->graph edgelist))
161 (order (topological-sort graph equal?)))
162 (cond
163 ((equal? order '(top left right bottom)) #t)
164 ((equal? order '(top right left bottom)) #t)
165 (else order))))
166 (permutations '((top left) (top right) (left bottom) (right bottom)))))
167
168 (test-equal '(libnewsboat regex-rs strprintf)
169 (topological-sort (edgelist->graph '((libnewsboat strprintf) (libnewsboat regex-rs) (regex-rs strprintf)))))
170
171 (test-end)