;;; GNU Guix --- Functional package management for GNU
-;;; Copyright © 2015, 2016 Ludovic Courtès <ludo@gnu.org>
+;;; Copyright © 2015-2016, 2020-2022 Ludovic Courtès <ludo@gnu.org>
;;; Copyright © 2016 Ricardo Wurmus <rekado@elephly.net>
;;;
;;; This file is part of GNU Guix.
#:use-module (guix monads)
#:use-module (guix records)
#:use-module (guix sets)
+ #:autoload (guix diagnostics) (formatted-message)
+ #:autoload (guix i18n) (G_)
#:use-module (rnrs io ports)
#:use-module (srfi srfi-1)
#:use-module (srfi srfi-9)
#:use-module (srfi srfi-26)
+ #:use-module (srfi srfi-34)
#:use-module (ice-9 match)
#:use-module (ice-9 vlist)
#:export (node-type
traverse/depth-first
node-transitive-edges
node-reachable-count
+ shortest-path
%graph-backends
%d3js-backend
%graphviz-backend
+ lookup-backend
+
graph-backend?
graph-backend
graph-backend-name
0
nodes node-edges))
+(define (shortest-path node1 node2 type)
+ "Return as a monadic value the shortest path, represented as a list, from
+NODE1 to NODE2 of the given TYPE. Return #f when there is no path."
+ (define node-edges
+ (node-type-edges type))
+
+ (define (find-shortest lst)
+ ;; Return the shortest path among LST, where each path is represented as a
+ ;; vlist.
+ (let loop ((lst lst)
+ (best +inf.0)
+ (shortest #f))
+ (match lst
+ (()
+ shortest)
+ ((head . tail)
+ (let ((len (vlist-length head)))
+ (if (< len best)
+ (loop tail len head)
+ (loop tail best shortest)))))))
+
+ (define (find-path node path paths)
+ ;; Return the a vhash that maps nodes to paths, with each path from the
+ ;; given node to NODE2.
+ (define (augment-paths child paths)
+ ;; When using %REFERENCE-NODE-TYPE, nodes can contain self references,
+ ;; hence this test.
+ (if (eq? child node)
+ (store-return paths)
+ (find-path child vlist-null paths)))
+
+ (cond ((eq? node node2)
+ (store-return (vhash-consq node (vlist-cons node path)
+ paths)))
+ ((vhash-assq node paths)
+ (store-return paths))
+ (else
+ ;; XXX: We could stop recursing if one if CHILDREN is NODE2, but in
+ ;; practice it's good enough.
+ (mlet* %store-monad ((children (node-edges node))
+ (paths (foldm %store-monad
+ augment-paths
+ paths
+ children)))
+ (define sub-paths
+ (filter-map (lambda (child)
+ (match (vhash-assq child paths)
+ (#f #f)
+ ((_ . path) path)))
+ children))
+
+ (match sub-paths
+ (()
+ (return (vhash-consq node #f paths)))
+ (lst
+ (return (vhash-consq node
+ (vlist-cons node (find-shortest sub-paths))
+ paths))))))))
+
+ (mlet %store-monad ((paths (find-path node1
+ (vlist-cons node1 vlist-null)
+ vlist-null)))
+ (return (match (vhash-assq node1 paths)
+ ((_ . #f) #f)
+ ((_ . path) (vlist->list path))))))
+
\f
;;;
;;; Graphviz export.
(define (emit-epilogue port)
(display "\n}\n" port))
(define (emit-node id label port)
- (format port " \"~a\" [label = \"~a\", shape = box, fontname = Helvetica];~%"
+ (format port " \"~a\" [label = \"~a\", shape = box, fontname = sans];~%"
id label))
(define (emit-edge id1 id2 port)
(format port " \"~a\" -> \"~a\" [color = ~a];~%"
var nodes = {},
nodeArray = [],
links = [];
-" (search-path %load-path "d3.v3.js")))
+" (search-path %load-path "guix/d3.v3.js")))
(define (emit-d3js-epilogue port)
(format port "</script><script type=\"text/javascript\" src=\"~a\"></script></body></html>"
- (search-path %load-path "graph.js")))
+ (search-path %load-path "guix/graph.js")))
(define (emit-d3js-node id label port)
(format port "\
%d3js-backend
%cypher-backend))
+(define (lookup-backend name)
+ "Return the graph backend called NAME. Raise an error if it is not found."
+ (or (find (lambda (backend)
+ (string=? (graph-backend-name backend) name))
+ %graph-backends)
+ (raise (formatted-message (G_ "~a: unknown graph backend") name))))
+
(define* (export-graph sinks port
#:key
- reverse-edges? node-type
+ reverse-edges? node-type (max-depth +inf.0)
(backend %graphviz-backend))
"Write to PORT the representation of the DAG with the given SINKS, using the
given BACKEND. Use NODE-TYPE to traverse the DAG. When REVERSE-EDGES? is
-true, draw reverse arrows."
+true, draw reverse arrows. Do not represent nodes whose distance to one of
+the SINKS is greater than MAX-DEPTH."
(match backend
(($ <graph-backend> _ _ emit-prologue emit-epilogue emit-node emit-edge)
(emit-prologue (node-type-name node-type) port)
(match node-type
(($ <node-type> node-identifier node-label node-edges)
(let loop ((nodes sinks)
+ (depths (make-list (length sinks) 0))
(visited (set)))
(match nodes
(()
(emit-epilogue port)
(store-return #t)))
((head . tail)
- (mlet %store-monad ((id (node-identifier head)))
- (if (set-contains? visited id)
- (loop tail visited)
- (mlet* %store-monad ((dependencies (node-edges head))
- (ids (mapm %store-monad
- node-identifier
- dependencies)))
- (emit-node id (node-label head) port)
- (for-each (lambda (dependency dependency-id)
- (if reverse-edges?
- (emit-edge dependency-id id port)
- (emit-edge id dependency-id port)))
- dependencies ids)
- (loop (append dependencies tail)
- (set-insert id visited)))))))))))))
+ (match depths
+ ((depth . depths)
+ (mlet %store-monad ((id (node-identifier head)))
+ (if (set-contains? visited id)
+ (loop tail depths visited)
+ (mlet* %store-monad ((dependencies
+ (if (= depth max-depth)
+ (return '())
+ (node-edges head)))
+ (ids
+ (mapm %store-monad
+ node-identifier
+ dependencies)))
+ (emit-node id (node-label head) port)
+ (for-each (lambda (dependency dependency-id)
+ (if reverse-edges?
+ (emit-edge dependency-id id port)
+ (emit-edge id dependency-id port)))
+ dependencies ids)
+ (loop (append dependencies tail)
+ (append (make-list (length dependencies)
+ (+ 1 depth))
+ depths)
+ (set-insert id visited)))))))))))))))
;;; graph.scm ends here
HCoop / jackhill / guix / guix.git / blobdiff