# HG changeset patch
# User Steve Losh <steve@stevelosh.com>
# Date 1479656327 0
# Node ID 516585a909d096895330ff634f0eb06c63b4a9f8
# Parent  f5d201dead81cfe387b18c9342ade90b3cf33044
Add `emptyp`, export `roots` and `leafs`

diff -r f5d201dead81 -r 516585a909d0 docs/03-reference.markdown
--- a/docs/03-reference.markdown	Tue Nov 08 14:11:17 2016 +0000
+++ b/docs/03-reference.markdown	Sun Nov 20 15:38:47 2016 +0000
@@ -78,6 +78,12 @@
 
   
 
+### `EMPTYP` (function)
+
+    (EMPTYP DIGRAPH)
+
+Return `t` if `digraph` has no vertices or edges, `nil` otherwise.
+
 ### `INSERT-EDGE` (function)
 
     (INSERT-EDGE DIGRAPH PREDECESSOR SUCCESSOR)
@@ -102,6 +108,18 @@
 
   
 
+### `LEAFS` (function)
+
+    (LEAFS DIGRAPH)
+
+Return all leaf vertices in `digraph`.
+
+  This is currently O(vertices).
+
+  A root is a vertex with no outgoing edges (i.e. out-degree 0).
+
+  
+
 ### `MAKE-DIGRAPH` (function)
 
     (MAKE-DIGRAPH &KEY INITIAL-VERTICES (TEST #'EQL) (HASH-FUNCTION NIL))
@@ -278,6 +296,18 @@
 
   
 
+### `ROOTS` (function)
+
+    (ROOTS DIGRAPH)
+
+Return all root vertices in `digraph`.
+
+  This is currently O(vertices).
+
+  A root is a vertex with no incoming edges (i.e. in-degree 0).
+
+  
+
 ### `SUCCESSORS` (function)
 
     (SUCCESSORS DIGRAPH VERTEX)
diff -r f5d201dead81 -r 516585a909d0 package.lisp
--- a/package.lisp	Tue Nov 08 14:11:17 2016 +0000
+++ b/package.lisp	Sun Nov 20 15:38:47 2016 +0000
@@ -4,9 +4,14 @@
     :digraph
     :make-digraph
 
+    :emptyp
+
     :vertices
     :edges
 
+    :roots
+    :leafs
+
     :predecessors
     :successors
     :neighbors
diff -r f5d201dead81 -r 516585a909d0 src/directed-graph.lisp
--- a/src/directed-graph.lisp	Tue Nov 08 14:11:17 2016 +0000
+++ b/src/directed-graph.lisp	Sun Nov 20 15:38:47 2016 +0000
@@ -1,7 +1,5 @@
 (in-package :digraph)
 
-
-
 ;;;; Utils --------------------------------------------------------------------
 (defun make-hash-table-portably (&key (size 0) test hash-function)
   ;; Only try to pass :hash-function if we were given it, so we don't explode in
@@ -72,6 +70,11 @@
 
 
 ;;;; Basic API ----------------------------------------------------------------
+(defun emptyp (digraph)
+  "Return `t` if `digraph` has no vertices or edges, `nil` otherwise."
+  (zerop (hash-table-count (digraph-nodes digraph))))
+
+
 (defun vertices (digraph)
   "Return a fresh list of the vertices of `digraph`."
   (hash-table-keys (digraph-nodes digraph)))
@@ -372,10 +375,24 @@
 
 
 (defun roots (digraph)
+  "Return all root vertices in `digraph`.
+
+  This is currently O(vertices).
+
+  A root is a vertex with no incoming edges (i.e. in-degree 0).
+
+  "
   (remove-if-not (lambda (v) (null (pred digraph v)))
                  (vertices digraph)))
 
 (defun leafs (digraph)
+  "Return all leaf vertices in `digraph`.
+
+  This is currently O(vertices).
+
+  A root is a vertex with no outgoing edges (i.e. out-degree 0).
+
+  "
   (remove-if-not (lambda (v) (null (succ digraph v)))
                  (vertices digraph)))
 
diff -r f5d201dead81 -r 516585a909d0 test/tests.lisp
--- a/test/tests.lisp	Tue Nov 08 14:11:17 2016 +0000
+++ b/test/tests.lisp	Sun Nov 20 15:38:47 2016 +0000
@@ -20,15 +20,34 @@
   (let ((g (make-digraph)))
     (is (zerop (count-vertices g)))
     (is (same () (vertices g)))
-    (is (same () (edges g))))
+    (is (same () (edges g)))
+    (is (emptyp g)))
   (let ((g (make-digraph :initial-vertices '(a b c))))
     (is (= 3 (count-vertices g)))
     (is (same '(a b c) (vertices g)))
-    (is (same () (edges g))))
+    (is (same () (edges g)))
+    (is (not (emptyp g))))
   (let ((g (make-digraph :initial-vertices '(a b a c a a))))
     (is (= 3 (count-vertices g)))
     (is (same '(a b c) (vertices g)))
-    (is (same () (edges g)))))
+    (is (same () (edges g)))
+    (is (not (emptyp g)))))
+
+
+(define-test roots-and-leafs
+  (let ((g (make-digraph)))
+    (is (same () (roots g)))
+    (is (same () (leafs g)))
+    (insert-vertex g 'a)
+    (insert-vertex g 'b)
+    (is (same '(a b) (roots g)))
+    (is (same '(a b) (leafs g)))
+    (insert-edge g 'a 'b)
+    (is (same '(a) (roots g)))
+    (is (same '(b) (leafs g)))
+    (insert-edge g 'b 'a)
+    (is (same () (roots g)))
+    (is (same () (leafs g)))))
 
 
 (define-test insert-vertex