0434eb58dde3 v1.3.0

Add `arbitrary-vertex`
[view raw] [browse files]
author Steve Losh <steve@stevelosh.com>
date Tue, 03 Dec 2019 19:34:41 -0500
parents 4a86a78b3de6
children 5be8c89f99ce
branches/tags v1.3.0
files .lispwords Makefile README.markdown cl-digraph.asd docs/03-reference.markdown docs/05-changelog.markdown docs/index.markdown package.lisp src/directed-graph.lisp test/tests.lisp

Changes

--- a/.lispwords	Sat Nov 03 15:44:01 2018 -0400
+++ b/.lispwords	Tue Dec 03 19:34:41 2019 -0500
@@ -0,0 +1,1 @@
+(1 do-vertices)
--- a/Makefile	Sat Nov 03 15:44:01 2018 -0400
+++ b/Makefile	Tue Dec 03 19:34:41 2019 -0500
@@ -40,7 +40,8 @@
 docs: docs/build/index.html
 
 pubdocs: docs
-	hg -R ~/src/sjl.bitbucket.org pull -u
-	rsync --delete -a ./docs/build/ ~/src/sjl.bitbucket.org/cl-digraph
-	hg -R ~/src/sjl.bitbucket.org commit -Am 'cl-digraph: Update site.'
-	hg -R ~/src/sjl.bitbucket.org push
+	hg -R ~/src/docs.stevelosh.com pull -u upstream
+	rsync --delete -a ./docs/build/ ~/src/docs.stevelosh.com/cl-digraph
+	hg -R ~/src/docs.stevelosh.com commit -Am 'cl-digraph: Update site.'
+	hg -R ~/src/docs.stevelosh.com push upstream
+	hg -R ~/src/docs.stevelosh.com push
--- a/README.markdown	Sat Nov 03 15:44:01 2018 -0400
+++ b/README.markdown	Tue Dec 03 19:34:41 2019 -0500
@@ -4,9 +4,9 @@
 [directed graph]: https://en.wikipedia.org/wiki/Directed_graph
 
 * **License:** MIT
-* **Documentation:** <https://sjl.bitbucket.io/cl-digraph/>
-* **Mercurial:** <http://bitbucket.org/sjl/cl-digraph/>
-* **Git:** <http://github.com/sjl/cl-digraph/>
+* **Documentation:** <http://docs.stevelosh.com/cl-digraph/>
+* **Mercurial:** <http://hg.sr.ht/~sjl/cl-digraph/>
+* **Git:** <https://github.com/sjl/cl-digraph/>
 
 cl-digraph focuses on simplicity, correctness, and usability.  Performance is
 not *terrible*, but is not a high priority.
--- a/cl-digraph.asd	Sat Nov 03 15:44:01 2018 -0400
+++ b/cl-digraph.asd	Tue Dec 03 19:34:41 2019 -0500
@@ -1,10 +1,10 @@
 (asdf:defsystem :cl-digraph
   :description "Simple directed graphs for Common Lisp."
   :author "Steve Losh <steve@stevelosh.com>"
-  :homepage "https://sjl.bitbucket.io/cl-digraph/"
+  :homepage "http://docs.stevelosh.com/cl-digraph/"
 
   :license "MIT/X11"
-  :version "1.2.1"
+  :version "1.3.0"
 
   :depends-on ()
 
--- a/docs/03-reference.markdown	Sat Nov 03 15:44:01 2018 -0400
+++ b/docs/03-reference.markdown	Tue Dec 03 19:34:41 2019 -0500
@@ -12,6 +12,16 @@
 
 ## Package `DIGRAPH`
 
+### `ARBITRARY-VERTEX` (function)
+
+    (ARBITRARY-VERTEX DIGRAPH)
+
+Return an arbitrary vertex of `digraph` and `t`.
+
+  If the digraph is empty, `(values nil nil)` will be returned instead.
+
+  
+
 ### `CONTAINS-EDGE-P` (function)
 
     (CONTAINS-EDGE-P DIGRAPH PREDECESSOR SUCCESSOR)
--- a/docs/05-changelog.markdown	Sat Nov 03 15:44:01 2018 -0400
+++ b/docs/05-changelog.markdown	Tue Dec 03 19:34:41 2019 -0500
@@ -5,6 +5,12 @@
 
 [TOC]
 
+v1.3.0
+------
+
+Added the `arbitrary-vertex` function to return an arbitrary vertex of
+a digraph.
+
 v1.2.1
 ------
 
--- a/docs/index.markdown	Sat Nov 03 15:44:01 2018 -0400
+++ b/docs/index.markdown	Tue Dec 03 19:34:41 2019 -0500
@@ -2,9 +2,9 @@
 for Common Lisp.
 
 * **License:** MIT
-* **Documentation:** <https://sjl.bitbucket.io/cl-digraph/>
-* **Mercurial:** <http://bitbucket.org/sjl/cl-digraph/>
-* **Git:** <http://github.com/sjl/cl-digraph/>
+* **Documentation:** <http://docs.stevelosh.com/cl-digraph/>
+* **Mercurial:** <https://hg.sr.ht/~sjl/cl-digraph/>
+* **Git:** <https://github.com/sjl/cl-digraph/>
 
 cl-digraph focuses on simplicity, correctness, and usability.  Performance is
 not *terrible*, but is not a high priority.
--- a/package.lisp	Sat Nov 03 15:44:01 2018 -0400
+++ b/package.lisp	Tue Dec 03 19:34:41 2019 -0500
@@ -9,6 +9,8 @@
     :vertices
     :edges
 
+    :arbitrary-vertex
+
     :roots
     :leafs
 
--- a/src/directed-graph.lisp	Sat Nov 03 15:44:01 2018 -0400
+++ b/src/directed-graph.lisp	Tue Dec 03 19:34:41 2019 -0500
@@ -158,6 +158,17 @@
     (apply #'insert-chain digraph successor later-successors)))
 
 
+(defun arbitrary-vertex (digraph)
+  "Return an arbitrary vertex of `digraph` and `t`.
+
+  If the digraph is empty, `(values nil nil)` will be returned instead.
+
+  "
+  (do-vertices (vertex digraph)
+    (return-from arbitrary-vertex (values vertex t)))
+  (values nil nil))
+
+
 (defun remove-edge (digraph predecessor successor)
   "Remove an edge from `predecessor` to `successor` if present.
 
--- a/test/tests.lisp	Sat Nov 03 15:44:01 2018 -0400
+++ b/test/tests.lisp	Tue Dec 03 19:34:41 2019 -0500
@@ -236,3 +236,19 @@
     (is (not (reachablep g 'a 'b)))
     (is (not (reachablep g 'z 'orphan)))))
 
+
+(define-test abitrary-vertex
+  (let ((g (make-simple-digraph)))
+    (is (member (arbitrary-vertex g) '(a b middle z orphan)))
+    (remove-vertex g 'b)
+    (is (member (arbitrary-vertex g) '(a middle z orphan)))
+    (remove-vertex g 'middle)
+    (is (member (arbitrary-vertex g) '(a z orphan)))
+    (remove-vertex g 'z)
+    (is (member (arbitrary-vertex g) '(a orphan)))
+    (remove-vertex g 'a)
+    (is (member (arbitrary-vertex g) '(orphan)))
+    (remove-vertex g 'orphan)
+    (is (null (arbitrary-vertex g)))
+    (insert-vertex g 'new)
+    (is (member (arbitrary-vertex g) '(new)))))