summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorLudovic Courtès <ludo@gnu.org>2016-05-23 22:31:59 +0200
committerLudovic Courtès <ludo@gnu.org>2016-05-24 00:06:01 +0200
commit623e4df42abd024e0a62ef0b30f9b550f37cba57 (patch)
tree58db9a64c84d7799e60cdef91aab25c2f7c04a13
parent9a6beb3b7ff3dad280b27a263869e233f3ac8336 (diff)
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.
-rw-r--r--guix/graph.scm22
1 files 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 @@
node-edges
node-back-edges
+ traverse/depth-first
node-transitive-edges
%graphviz-backend
@@ -99,13 +100,13 @@ returns its back edges. NODES is taken to be the sinks of the global graph."
(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 @@ typically returned by 'node-edges' or 'node-back-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.