1 files changed, 23 insertions, 7 deletions
diff --git a/guix/graph.scm b/guix/graph.scm
index ad93403a1e..735d340c2c 100644
--- a/guix/graph.scm
+++ b/guix/graph.scm
@@ -37,7 +37,9 @@
 
             node-edges
             node-back-edges
+            traverse/depth-first
             node-transitive-edges
+            node-reachable-count
 
             %graphviz-backend
             graph-backend?
@@ -99,13 +101,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 +117,23 @@ 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))
+
+(define (node-reachable-count nodes node-edges)
+  "Return the number of nodes reachable from NODES along NODE-EDGES."
+  (traverse/depth-first (lambda (_ count)
+                          (+ 1 count))
+                        0
+                        nodes node-edges))
+
 
 ;;;
 ;;; Graphviz export.