[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
02/03: graph: Expose 'traverse/depth-first'.
From: |
Ludovic Courtès |
Subject: |
02/03: graph: Expose 'traverse/depth-first'. |
Date: |
Mon, 23 May 2016 22:06:20 +0000 (UTC) |
civodul pushed a commit to branch master
in repository guix.
commit 623e4df42abd024e0a62ef0b30f9b550f37cba57
Author: Ludovic CourtÃ¨s <address@hidden>
Date: Mon May 23 22:31:59 2016 +0200
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 ad93403..af589c5 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.