From 623e4df42abd024e0a62ef0b30f9b550f37cba57 Mon Sep 17 00:00:00 2001 From: Ludovic Courtès Date: Mon, 23 May 2016 22:31:59 +0200 Subject: graph: Expose 'traverse/depth-first'. * guix/graph.scm (traverse/depth-first): New procedure, based on code formerly in 'node-transitive-edges'. (node-transitive-edges): Rewrite in terms of it. --- guix/graph.scm | 22 +++++++++++++++------- 1 file changed, 15 insertions(+), 7 deletions(-) diff --git a/guix/graph.scm b/guix/graph.scm index ad93403a1e..af589c5c67 100644 --- a/guix/graph.scm +++ b/guix/graph.scm @@ -37,6 +37,7 @@ (define-module (guix graph) node-edges node-back-edges + traverse/depth-first node-transitive-edges %graphviz-backend @@ -99,13 +100,13 @@ (define (node-back-edges type nodes) (lambda (source target edges) (vhash-consq target source edges)))) -(define (node-transitive-edges nodes node-edges) - "Return the list of nodes directly or indirectly connected to NODES -according to the NODE-EDGES procedure. NODE-EDGES must be a one-argument -procedure that, given a node, returns its list of direct dependents; it is -typically returned by 'node-edges' or 'node-back-edges'." +(define (traverse/depth-first proc seed nodes node-edges) + "Do a depth-first traversal of NODES along NODE-EDGES, calling PROC with +each node and the current result, and visiting each reachable node exactly +once. NODES must be a list of nodes, and NODE-EDGES must be a one-argument +procedure as returned by 'node-edges' or 'node-back-edges'." (let loop ((nodes (append-map node-edges nodes)) - (result '()) + (result seed) (visited (setq))) (match nodes (() @@ -115,9 +116,16 @@ (define (node-transitive-edges nodes node-edges) (loop tail result visited) (let ((edges (node-edges head))) (loop (append edges tail) - (cons head result) + (proc head result) (set-insert head visited)))))))) +(define (node-transitive-edges nodes node-edges) + "Return the list of nodes directly or indirectly connected to NODES +according to the NODE-EDGES procedure. NODE-EDGES must be a one-argument +procedure that, given a node, returns its list of direct dependents; it is +typically returned by 'node-edges' or 'node-back-edges'." + (traverse/depth-first cons '() nodes node-edges)) + ;;; ;;; Graphviz export. -- cgit v1.2.3