From 623e4df42abd024e0a62ef0b30f9b550f37cba57 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Ludovic=20Court=C3=A8s?= <ludo@gnu.org>
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(-)

(limited to 'guix/graph.scm')

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.
-- 
cgit v1.2.3