Commit | Line | Data |
---|---|---|
8fb58371 | 1 | ;;; GNU Guix --- Functional package management for GNU |
8463d134 | 2 | ;;; Copyright © 2015, 2016 Ludovic Courtès <ludo@gnu.org> |
642339dc | 3 | ;;; Copyright © 2016 Ricardo Wurmus <rekado@elephly.net> |
8fb58371 LC |
4 | ;;; |
5 | ;;; This file is part of GNU Guix. | |
6 | ;;; | |
7 | ;;; GNU Guix is free software; you can redistribute it and/or modify it | |
8 | ;;; under the terms of the GNU General Public License as published by | |
9 | ;;; the Free Software Foundation; either version 3 of the License, or (at | |
10 | ;;; your option) any later version. | |
11 | ;;; | |
12 | ;;; GNU Guix is distributed in the hope that it will be useful, but | |
13 | ;;; WITHOUT ANY WARRANTY; without even the implied warranty of | |
14 | ;;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
15 | ;;; GNU General Public License for more details. | |
16 | ;;; | |
17 | ;;; You should have received a copy of the GNU General Public License | |
18 | ;;; along with GNU Guix. If not, see <http://www.gnu.org/licenses/>. | |
19 | ||
20 | (define-module (guix graph) | |
21 | #:use-module (guix store) | |
22 | #:use-module (guix monads) | |
23 | #:use-module (guix records) | |
24 | #:use-module (guix sets) | |
4d93f312 | 25 | #:use-module (rnrs io ports) |
923d846c | 26 | #:use-module (srfi srfi-1) |
8fb58371 | 27 | #:use-module (srfi srfi-9) |
923d846c | 28 | #:use-module (srfi srfi-26) |
8fb58371 | 29 | #:use-module (ice-9 match) |
923d846c | 30 | #:use-module (ice-9 vlist) |
8fb58371 LC |
31 | #:export (node-type |
32 | node-type? | |
33 | node-type-identifier | |
34 | node-type-label | |
35 | node-type-edges | |
36 | node-type-convert | |
37 | node-type-name | |
38 | node-type-description | |
39 | ||
923d846c LC |
40 | node-edges |
41 | node-back-edges | |
623e4df4 | 42 | traverse/depth-first |
923d846c | 43 | node-transitive-edges |
e144e342 | 44 | node-reachable-count |
923d846c | 45 | |
642339dc | 46 | %graph-backends |
4d93f312 | 47 | %d3js-backend |
8fb58371 LC |
48 | %graphviz-backend |
49 | graph-backend? | |
50 | graph-backend | |
51377437 RW |
51 | graph-backend-name |
52 | graph-backend-description | |
8fb58371 LC |
53 | |
54 | export-graph)) | |
55 | ||
56 | ;;; Commentary: | |
57 | ;;; | |
58 | ;;; This module provides an abstract way to represent graphs and to manipulate | |
59 | ;;; them. It comes with several such representations for packages, | |
60 | ;;; derivations, and store items. It also provides a generic interface for | |
61 | ;;; exporting graphs in an external format, including a Graphviz | |
62 | ;;; implementation thereof. | |
63 | ;;; | |
64 | ;;; Code: | |
65 | ||
66 | \f | |
67 | ;;; | |
68 | ;;; Node types. | |
69 | ;;; | |
70 | ||
71 | (define-record-type* <node-type> node-type make-node-type | |
72 | node-type? | |
73 | (identifier node-type-identifier) ;node -> M identifier | |
74 | (label node-type-label) ;node -> string | |
75 | (edges node-type-edges) ;node -> M list of nodes | |
a773c314 | 76 | (convert node-type-convert ;any -> M list of nodes |
8fb58371 LC |
77 | (default (lift1 list %store-monad))) |
78 | (name node-type-name) ;string | |
79 | (description node-type-description)) ;string | |
80 | ||
923d846c LC |
81 | (define (%node-edges type nodes cons-edge) |
82 | (with-monad %store-monad | |
83 | (match type | |
84 | (($ <node-type> identifier label node-edges) | |
85 | (define (add-edge node edges) | |
86 | (>>= (node-edges node) | |
87 | (lambda (nodes) | |
88 | (return (fold (cut cons-edge node <> <>) | |
89 | edges nodes))))) | |
90 | ||
91 | (mlet %store-monad ((edges (foldm %store-monad | |
92 | add-edge vlist-null nodes))) | |
93 | (return (lambda (node) | |
94 | (reverse (vhash-foldq* cons '() node edges))))))))) | |
95 | ||
96 | (define (node-edges type nodes) | |
97 | "Return, as a monadic value, a one-argument procedure that, given a node of TYPE, | |
98 | returns its edges. NODES is taken to be the sinks of the global graph." | |
99 | (%node-edges type nodes | |
100 | (lambda (source target edges) | |
101 | (vhash-consq source target edges)))) | |
102 | ||
103 | (define (node-back-edges type nodes) | |
104 | "Return, as a monadic value, a one-argument procedure that, given a node of TYPE, | |
105 | returns its back edges. NODES is taken to be the sinks of the global graph." | |
106 | (%node-edges type nodes | |
107 | (lambda (source target edges) | |
108 | (vhash-consq target source edges)))) | |
109 | ||
623e4df4 LC |
110 | (define (traverse/depth-first proc seed nodes node-edges) |
111 | "Do a depth-first traversal of NODES along NODE-EDGES, calling PROC with | |
112 | each node and the current result, and visiting each reachable node exactly | |
113 | once. NODES must be a list of nodes, and NODE-EDGES must be a one-argument | |
114 | procedure as returned by 'node-edges' or 'node-back-edges'." | |
923d846c | 115 | (let loop ((nodes (append-map node-edges nodes)) |
623e4df4 | 116 | (result seed) |
923d846c LC |
117 | (visited (setq))) |
118 | (match nodes | |
119 | (() | |
120 | result) | |
121 | ((head . tail) | |
122 | (if (set-contains? visited head) | |
123 | (loop tail result visited) | |
124 | (let ((edges (node-edges head))) | |
125 | (loop (append edges tail) | |
623e4df4 | 126 | (proc head result) |
923d846c LC |
127 | (set-insert head visited)))))))) |
128 | ||
623e4df4 LC |
129 | (define (node-transitive-edges nodes node-edges) |
130 | "Return the list of nodes directly or indirectly connected to NODES | |
131 | according to the NODE-EDGES procedure. NODE-EDGES must be a one-argument | |
132 | procedure that, given a node, returns its list of direct dependents; it is | |
133 | typically returned by 'node-edges' or 'node-back-edges'." | |
134 | (traverse/depth-first cons '() nodes node-edges)) | |
135 | ||
e144e342 LC |
136 | (define (node-reachable-count nodes node-edges) |
137 | "Return the number of nodes reachable from NODES along NODE-EDGES." | |
138 | (traverse/depth-first (lambda (_ count) | |
139 | (+ 1 count)) | |
140 | 0 | |
141 | nodes node-edges)) | |
142 | ||
8fb58371 LC |
143 | \f |
144 | ;;; | |
145 | ;;; Graphviz export. | |
146 | ;;; | |
147 | ||
148 | (define-record-type <graph-backend> | |
51377437 | 149 | (graph-backend name description prologue epilogue node edge) |
8fb58371 | 150 | graph-backend? |
51377437 RW |
151 | (name graph-backend-name) |
152 | (description graph-backend-description) | |
153 | (prologue graph-backend-prologue) | |
154 | (epilogue graph-backend-epilogue) | |
155 | (node graph-backend-node) | |
156 | (edge graph-backend-edge)) | |
8fb58371 | 157 | |
8463d134 LC |
158 | (define %colors |
159 | ;; See colortbl.h in Graphviz. | |
160 | #("red" "magenta" "blue" "cyan3" "darkseagreen" | |
161 | "peachpuff4" "darkviolet" "dimgrey" "darkgoldenrod")) | |
162 | ||
163 | (define (pop-color hint) | |
164 | "Return a Graphviz color based on HINT, an arbitrary object." | |
165 | (let ((index (hash hint (vector-length %colors)))) | |
166 | (vector-ref %colors index))) | |
167 | ||
8fb58371 LC |
168 | (define (emit-prologue name port) |
169 | (format port "digraph \"Guix ~a\" {\n" | |
170 | name)) | |
171 | (define (emit-epilogue port) | |
172 | (display "\n}\n" port)) | |
5e60bef9 | 173 | (define (emit-node id label port) |
8fb58371 | 174 | (format port " \"~a\" [label = \"~a\", shape = box, fontname = Helvetica];~%" |
5e60bef9 | 175 | id label)) |
8fb58371 | 176 | (define (emit-edge id1 id2 port) |
8463d134 LC |
177 | (format port " \"~a\" -> \"~a\" [color = ~a];~%" |
178 | id1 id2 (pop-color id1))) | |
8fb58371 LC |
179 | |
180 | (define %graphviz-backend | |
51377437 RW |
181 | (graph-backend "graphviz" |
182 | "Generate graph in DOT format for use with Graphviz." | |
183 | emit-prologue emit-epilogue | |
8fb58371 LC |
184 | emit-node emit-edge)) |
185 | ||
642339dc | 186 | \f |
4d93f312 RW |
187 | ;;; |
188 | ;;; d3js export. | |
189 | ;;; | |
190 | ||
191 | (define (emit-d3js-prologue name port) | |
192 | (format port "\ | |
193 | <!DOCTYPE html> | |
194 | <html> | |
195 | <head> | |
196 | <meta charset=\"utf-8\"> | |
197 | <style> | |
198 | text { | |
199 | font: 10px sans-serif; | |
200 | pointer-events: none; | |
201 | } | |
202 | </style> | |
203 | <script type=\"text/javascript\" src=\"~a\"></script> | |
204 | </head> | |
205 | <body> | |
206 | <script type=\"text/javascript\"> | |
207 | var nodes = {}, | |
208 | nodeArray = [], | |
209 | links = []; | |
210 | " (search-path %load-path "d3.v3.js"))) | |
211 | ||
212 | (define (emit-d3js-epilogue port) | |
213 | (format port "</script><script type=\"text/javascript\" src=\"~a\"></script></body></html>" | |
214 | (search-path %load-path "graph.js"))) | |
215 | ||
5e60bef9 | 216 | (define (emit-d3js-node id label port) |
4d93f312 RW |
217 | (format port "\ |
218 | nodes[\"~a\"] = {\"id\": \"~a\", \"label\": \"~a\", \"index\": nodeArray.length}; | |
219 | nodeArray.push(nodes[\"~a\"]);~%" | |
5e60bef9 | 220 | id id label id)) |
4d93f312 RW |
221 | |
222 | (define (emit-d3js-edge id1 id2 port) | |
223 | (format port "links.push({\"source\": \"~a\", \"target\": \"~a\"});~%" | |
224 | id1 id2)) | |
225 | ||
226 | (define %d3js-backend | |
227 | (graph-backend "d3js" | |
228 | "Generate chord diagrams with d3js." | |
229 | emit-d3js-prologue emit-d3js-epilogue | |
230 | emit-d3js-node emit-d3js-edge)) | |
231 | ||
5899fafb RJ |
232 | |
233 | \f | |
234 | ;;; | |
235 | ;;; Cypher export. | |
236 | ;;; | |
237 | ||
238 | (define (emit-cypher-prologue name port) | |
239 | (format port "")) | |
240 | ||
241 | (define (emit-cypher-epilogue port) | |
242 | (format port "")) | |
243 | ||
5e60bef9 | 244 | (define (emit-cypher-node id label port) |
5899fafb | 245 | (format port "MERGE (p:Package { id: ~s }) SET p.name = ~s;~%" |
5e60bef9 | 246 | id label )) |
5899fafb RJ |
247 | |
248 | (define (emit-cypher-edge id1 id2 port) | |
249 | (format port "MERGE (a:Package { id: ~s });~%" id1) | |
250 | (format port "MERGE (b:Package { id: ~s });~%" id2) | |
251 | (format port "MATCH (a:Package { id: ~s }), (b:Package { id: ~s }) CREATE UNIQUE (a)-[:NEEDS]->(b);~%" | |
252 | id1 id2)) | |
253 | ||
254 | (define %cypher-backend | |
255 | (graph-backend "cypher" | |
256 | "Generate Cypher queries." | |
257 | emit-cypher-prologue emit-cypher-epilogue | |
258 | emit-cypher-node emit-cypher-edge)) | |
259 | ||
260 | ||
4d93f312 | 261 | \f |
642339dc RW |
262 | ;;; |
263 | ;;; Shared. | |
264 | ;;; | |
265 | ||
266 | (define %graph-backends | |
4d93f312 | 267 | (list %graphviz-backend |
5899fafb RJ |
268 | %d3js-backend |
269 | %cypher-backend)) | |
642339dc | 270 | |
8fb58371 LC |
271 | (define* (export-graph sinks port |
272 | #:key | |
273 | reverse-edges? node-type | |
274 | (backend %graphviz-backend)) | |
275 | "Write to PORT the representation of the DAG with the given SINKS, using the | |
276 | given BACKEND. Use NODE-TYPE to traverse the DAG. When REVERSE-EDGES? is | |
277 | true, draw reverse arrows." | |
278 | (match backend | |
51377437 | 279 | (($ <graph-backend> _ _ emit-prologue emit-epilogue emit-node emit-edge) |
8fb58371 LC |
280 | (emit-prologue (node-type-name node-type) port) |
281 | ||
282 | (match node-type | |
283 | (($ <node-type> node-identifier node-label node-edges) | |
284 | (let loop ((nodes sinks) | |
285 | (visited (set))) | |
286 | (match nodes | |
287 | (() | |
288 | (with-monad %store-monad | |
289 | (emit-epilogue port) | |
290 | (store-return #t))) | |
291 | ((head . tail) | |
292 | (mlet %store-monad ((id (node-identifier head))) | |
293 | (if (set-contains? visited id) | |
294 | (loop tail visited) | |
295 | (mlet* %store-monad ((dependencies (node-edges head)) | |
296 | (ids (mapm %store-monad | |
297 | node-identifier | |
298 | dependencies))) | |
5e60bef9 | 299 | (emit-node id (node-label head) port) |
8fb58371 LC |
300 | (for-each (lambda (dependency dependency-id) |
301 | (if reverse-edges? | |
302 | (emit-edge dependency-id id port) | |
303 | (emit-edge id dependency-id port))) | |
304 | dependencies ids) | |
305 | (loop (append dependencies tail) | |
306 | (set-insert id visited))))))))))))) | |
307 | ||
308 | ;;; graph.scm ends here |