02/03: graph: Expose 'traverse/depth-first'.

[Ludovic Courtès]

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.