--- a/.hgignore Sun Nov 06 21:22:16 2016 +0000
+++ b/.hgignore Sun Nov 06 23:49:16 2016 +0000
@@ -1,4 +1,5 @@
syntax: glob
scratch.lisp
-digraph.png
+*.png
+docs/build
--- a/Makefile Sun Nov 06 21:22:16 2016 +0000
+++ b/Makefile Sun Nov 06 23:49:16 2016 +0000
@@ -1,4 +1,8 @@
-.PHONY: vendor test test-sbcl test-ccl test-ecl test-abcl
+.PHONY: vendor test test-sbcl test-ccl test-ecl test-abcl pubdocs
+
+sourcefiles = $(shell ffind --full-path --literal .lisp)
+docfiles = $(shell ls docs/*.markdown)
+apidocs = $(shell ls docs/*reference*.markdown)
# Vendor ----------------------------------------------------------------------
vendor/quickutils.lisp: vendor/make-quickutils.lisp
@@ -25,3 +29,18 @@
test-abcl:
echo; figlet -kf broadway 'ABCL' | sed -Ee 's/ +$$//' | tr -s '\n' | lolcat --freq=0.25; echo
abcl --load test/run.lisp
+
+# Documentation ---------------------------------------------------------------
+$(apidocs): $(sourcefiles)
+ sbcl --noinform --load docs/api.lisp --eval '(quit)'
+
+docs/build/index.html: $(docfiles) $(apidocs) docs/title
+ cd docs && ~/.virtualenvs/d/bin/d
+
+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
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/docs/01-installation.markdown Sun Nov 06 23:49:16 2016 +0000
@@ -0,0 +1,17 @@
+Installation
+============
+
+cl-digraph is compatible with Quicklisp, but not *in* Quicklisp (yet?). You can
+clone the repository into your [Quicklisp local-projects][local] directory for
+now.
+
+The `cl-digraph` system contains the core API and has no dependencies.
+
+The `cl-digraph.dot` system contains support for drawing digraphs with Graphviz
+using [cl-dot][].
+
+The `cl-digraph.test` system contains the test suite, which uses [1am][].
+
+[local]: https://www.quicklisp.org/beta/faq.html#local-project
+[1am]: https://github.com/lmj/1am
+[cl-dot]: https://github.com/michaelw/cl-dot
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/docs/02-usage.markdown Sun Nov 06 23:49:16 2016 +0000
@@ -0,0 +1,348 @@
+Usage
+=====
+
+cl-digraph is a simple library for working with [directed graphs][] in Common
+Lisp.
+
+[directed graphs]: https://en.wikipedia.org/wiki/Directed_graph
+
+[TOC]
+
+Package
+-------
+
+All core cl-digraph functions are in the `digraph` package. You can `:use` that
+if you really want to, but it's probably clearer to use namespaced `digraph:...`
+symbols.
+
+Creating Digraphs
+-----------------
+
+Digraphs can be created with `make-digraph`:
+
+ :::lisp
+ (digraph:make-digraph)
+ ; =>
+ #<DIGRAPH:DIGRAPH () {1002CFD343}>
+
+Working with Vertices
+---------------------
+
+Vertices can be added to a digraph with `insert-vertex`, and a list of all
+vertices in the graph retrieved with `vertices`:
+
+ :::lisp
+ (defparameter *d* (digraph:make-digraph))
+
+ (digraph:vertices *d*)
+ ; => ()
+
+ (digraph:insert-vertex *d* 'foo)
+ (digraph:vertices *d*)
+ ; => (foo)
+
+ (digraph:insert-vertex *d* 'bar)
+ (digraph:vertices *d*)
+ ; => (bar foo)
+
+The order of vertices returned in the list is arbitrary. We'll see how to
+retrieve vertices in specific orders later.
+
+Duplicate vertices are silently ignored:
+
+ :::lisp
+ (defparameter *d* (digraph:make-digraph))
+
+ (digraph:insert-vertex *d* 'foo)
+ (digraph:insert-vertex *d* 'foo)
+ (digraph:insert-vertex *d* 'foo)
+ (digraph:vertices *d*)
+ ; => (foo)
+
+You can also specify some initial vertices directly in the `make-digraph` call
+if you want:
+
+ :::lisp
+ (defparameter *d*
+ (digraph:make-digraph :initial-vertices '(a b c)))
+
+ (digraph:vertices *d*)
+ ; => (a c b)
+
+ (digraph:insert-vertex *d* 'foo)
+ (digraph:vertices *d*)
+ ; => (a c foo b)
+
+You can remove vertices with `remove-vertex`. Removing a vertex that's not in
+the graph is silently ignored:
+
+ :::lisp
+ (defparameter *d*
+ (digraph:make-digraph :initial-vertices '(a b c)))
+
+ (digraph:vertices *d*)
+ ; => (a c b)
+
+ (digraph:remove-vertex *d* 'a)
+ (digraph:vertices *d*)
+ ; => (c b)
+
+ (digraph:remove-vertex *d* 'cats)
+ (digraph:vertices *d*)
+ ; => (c b)
+
+Equality
+--------
+
+By default cl-digraph compares vertices for equality with `eql`. You can
+specify a different equality predicate with the `:test` argument to
+`make-digraph`:
+
+ :::lisp
+ (defparameter *d*
+ (digraph:make-digraph :test #'equal))
+
+ (digraph:insert-vertex *d* (list 1 2))
+ (digraph:insert-vertex *d* (list 3 4))
+ (digraph:vertices *d*)
+ ; => ((1 2) (3 4))
+
+ (digraph:insert-vertex *d* (list 1 2))
+ (digraph:vertices *d*)
+ ; => ((1 2) (3 4))
+
+ (digraph:remove-vertex *d* (list 1 2))
+ (digraph:vertices *d*)
+ ; => ((3 4))
+
+cl-digraph stores data in hash tables internally, so `test` must be one of the
+predicates supported as a hash table test (`eq`, `eql`, `equal`, or `equalp`).
+
+If your Lisp implementation supports creating hash tables with custom hash
+functions with the `:hash-function` argument to `make-hash-table`, you can use
+them with cl-digraph as well:
+
+ :::lisp
+ (defparameter *d*
+ (digraph:make-digraph :test #'some-predicate
+ :hash-function #'custom-hash-function))
+
+This should work in SBCL, LispWorks, Allegro, CCL, and possibly others.
+
+Working with Edges
+------------------
+
+Once you've got some vertices in a digraph you can add edges between them. The
+vertex that an edge goes *out of* is called the **predecessor**, and the vertex
+the edge goes *into* is called the **successor**:
+
+ ┌─────────────┐ ┌─────────────┐
+ │ predecessor │─────▶│ successor │
+ └─────────────┘ └─────────────┘
+
+Edges are added with `insert-edge`. A list of edges in a digraph can be
+retrieved with `edges`:
+
+ :::lisp
+ (defparameter *d*
+ (digraph:make-digraph :initial-vertices '(a b c)))
+
+ (digraph:edges *d*)
+ ; => ()
+
+ (digraph:insert-edge *d* 'a 'b) ; a -> b
+ (digraph:edges *d*)
+ ; => ((a . b))
+
+ (digraph:insert-edge *d* 'b 'c) ; b -> c
+ (digraph:edges *d*)
+ ; => ((b . c) (a . b))
+
+Duplicate edges are silently ignored. The predecessor and successor must both
+exist in the graph already, or an error will be signaled:
+
+ :::lisp
+ (defparameter *d*
+ (digraph:make-digraph :initial-vertices '(a b c)))
+
+ (digraph:insert-edge *d* 'a 'b) ; a -> b
+ (digraph:insert-edge *d* 'a 'b) ; ignored
+ (digraph:insert-edge *d* 'a 'b) ; ignored
+ (digraph:edges *d*)
+ ; => ((a . b))
+
+ (digraph:insert-edge *d* 'cats 'dogs)
+ ; => Error!
+
+Edges can be removed with `remove-edge`. Removing an edge that's not in the
+graph is silently ignored:
+
+ :::lisp
+ (defparameter *d*
+ (digraph:make-digraph :initial-vertices '(a b c)))
+
+ (digraph:insert-edge *d* 'a 'b) ; a -> b
+ (digraph:edges *d*)
+ ; => ((a . b))
+
+ (digraph:remove-edge *d* 'a 'b) ; removes a -> b
+ (digraph:remove-edge *d* 'a 'b) ; ignored
+ (digraph:edges *d*)
+ ; => ()
+
+Retrieving Digraph Information
+------------------------------
+
+Once you've got a digraph you might want to ask it about itself. Let's consider
+a simple digraph as an example:
+
+ :::lisp
+ ; ┌───┐ ┌───┐
+ ; ┌───────▶│ B │─────▶│ D │
+ ; │ └───┘ └───┘
+ ; ┌───┐
+ ; │ A │ ┌─────┐ ┌─────┐
+ ; └───┘ │ FOO │──────▶│ BAR │──┐
+ ; │ ┌───┐ └─────┘ └─────┘ │
+ ; └───────▶│ C │ ▲ │
+ ; └───┘ │ │
+ ; └─────┘
+ (defparameter *d*
+ (digraph:make-digraph :initial-vertices '(a b c d foo bar)))
+
+ (loop :for (from to) :in '((a b) (a c) (b d) (foo bar) (bar bar))
+ :do (digraph:insert-edge *d* from to))
+
+Notice that digraphs don't have to be connected, and vertices can have edges to
+themselves.
+
+### Vertices and Edges
+
+We've already seen `vertices` and `edges`:
+
+ :::lisp
+ (digraph:vertices *d*)
+ ; => (BAR FOO D C B A)
+
+ (digraph:edges *d*)
+ ; => ((BAR . BAR) (FOO . BAR) (B . D) (A . B) (A . C))
+
+These functions return their results in an arbitrary order — don't rely on it
+being anything in particular.
+
+### Neighboring Vertices
+
+The `predecessors` and `successors` functions return a list of vertices with
+edges to/from a particular vertex:
+
+ :::lisp
+ (digraph:predecessors *d* 'a) ; => ()
+ (digraph:successors *d* 'a) ; => (b c)
+
+ (digraph:predecessors *d* 'bar) ; => (foo bar)
+ (digraph:successors *d* 'bar) ; => (bar)
+
+`neighbors` returns all vertices that are a predecessor *or* successor of the
+given vertex:
+
+ :::lisp
+ (digraph:neighbors *d* 'b) ; => (a d)
+
+### Membership
+
+To check whether a digraph contains a particular edge or vertex use
+`contains-vertex-p` and `contains-edge-p`:
+
+ :::lisp
+ (digraph:contains-vertex-p *d* 'a) ; => t
+ (digraph:contains-vertex-p *d* 'horses) ; => nil
+
+ (digraph:contains-edge-p *d* 'a 'b) ; => t
+ (digraph:contains-edge-p *d* 'a 'foo) ; => nil
+
+### Sizes and Counts
+
+If you just want the *number* of vertices or edges in a digraph and don't need
+a list of them, use `count-vertices` and `count-edges`:
+
+ :::lisp
+ (digraph:count-vertices *d*) ; => 6
+ (digraph:count-edges *d*) ; => 5
+
+Similarly, if you want to know the number of edges into/out of/involving
+a vertex use `degree`, `degree-in`, and `degree-out`:
+
+ :::lisp
+ (digraph:predecessors *d* 'a) ; => ()
+ (digraph:degree-in *d* 'a) ; = 0
+
+ (digraph:successors *d* 'bar) ; => (bar)
+ (digraph:degree-out *d* 'bar) ; => 1
+
+ (digraph:neighbors *d* 'b) ; => (a d)
+ (digraph:degree-out *d* 'b) ; => 2
+
+Mapping, Traversal, and Sorting
+-------------------------------
+
+Sometimes you may want to perform an action on each vertex or edge in a directed
+graph, possibly in a specific order.
+
+### Unordered Mapping
+
+If you don't care about the order the items are processed/returned in, use one
+of the unordered mapping functions:
+
+* `(digraph:mapc-vertices function digraph)`
+* `(digraph:mapc-edges function digraph)`
+* `(digraph:map-vertices function digraph)`
+* `(digraph:map-edges function digraph)`
+
+The `map-` variants return a fresh list of the results of calling `function` on
+the argument(s).
+
+The `mapc-` variants return `nil`, so you'd want to use them for the side
+effects of `function`.
+
+The `-vertices` variants call `function` with a single argument: the vertex.
+
+The `-edges` variants call `function` with two arguments: the predecessor and
+successor.
+
+### Ordered Traversal
+
+Sometimes you may want to traverse the vertices of a digraph in depth-first or
+breadth-first order. You can use the ordered mapping functions for this:
+
+* `(digraph:mapc-depth-first function digraph start-vertex)`
+* `(digraph:mapc-breadth-first function digraph start-vertex)`
+* `(digraph:map-depth-first function digraph start-vertex)`
+* `(digraph:map-breadth-first function digraph start-vertex)`
+
+If a traversal contains a cycle the traversal will stop that line of traversing
+instead of looping infinitely.
+
+### Topological Sorting
+
+One common use of (acyclic) digraphs is to represent graphs of dependencies,
+e.g. library `foo` depends on library `bar`, and `bar` depends on `baz`.
+
+Often the end goal of constructing such a graph is to produce a [topologically
+sorted][] list of the vertices — a list where each vertex comes after the ones
+it depends on. cl-digraph can produce a list in this order with the
+`topological-sort` function:
+
+ :::lisp
+ (defparameter *d*
+ (digraph:make-digraph :initial-vertices '(a b c d)))
+
+ (digraph:insert-edge *d* 'a 'b) ; a depends on b
+ (digraph:insert-edge *d* 'a 'c) ; a depends on c
+ (digraph:insert-edge *d* 'd 'a) ; d depends on a
+
+ (digraph:topological-sort *d*)
+ ; => one of
+ (C B A D)
+ (B C A D)
+
+[topologically sorted]: https://en.wikipedia.org/wiki/Topological_sorting
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/docs/03-reference.markdown Sun Nov 06 23:49:16 2016 +0000
@@ -0,0 +1,292 @@
+# API Reference
+
+The following is a list of all user-facing parts of cl-digraph.
+
+If there are backwards-incompatible changes to anything listed here, they will
+be noted in the changelog and the author will feel bad.
+
+Anything not listed here is subject to change at any time with no warning, so
+don't touch it.
+
+[TOC]
+
+## Package `DIGRAPH`
+
+### `CONTAINS-EDGE-P` (function)
+
+ (CONTAINS-EDGE-P DIGRAPH PREDECESSOR SUCCESSOR)
+
+Return whether the graph contains an edge from `predecessor` to `successor`.
+
+### `CONTAINS-VERTEX-P` (function)
+
+ (CONTAINS-VERTEX-P DIGRAPH VERTEX)
+
+Return whether the graph contains `vertex`.
+
+### `COPY-DIGRAPH` (function)
+
+ (COPY-DIGRAPH DIGRAPH)
+
+Create a fresh copy of `digraph`.
+
+ The vertex objects themselves are not copied, but everything else is.
+
+
+
+### `COUNT-EDGES` (function)
+
+ (COUNT-EDGES DIGRAPH)
+
+Return the number of edges in `digraph`.
+
+### `COUNT-VERTICES` (function)
+
+ (COUNT-VERTICES DIGRAPH)
+
+Return the number of vertices in `digraph`.
+
+### `DEGREE` (function)
+
+ (DEGREE DIGRAPH VERTEX)
+
+Return the number of neighbors of `vertex`.
+
+### `DEGREE-IN` (function)
+
+ (DEGREE-IN DIGRAPH VERTEX)
+
+Return the number of predecessors of `vertex`.
+
+### `DEGREE-OUT` (function)
+
+ (DEGREE-OUT DIGRAPH VERTEX)
+
+Return the number of successors of `vertex`.
+
+### `DIGRAPH` (class)
+
+A directed graph. Use `make-digraph` to create one.
+
+### `EDGES` (function)
+
+ (EDGES DIGRAPH)
+
+Return a fresh list of the edges of `digraph`.
+
+ Each edge will be a cons of the form `(predecessor . successor)`.
+
+
+
+### `INSERT-EDGE` (function)
+
+ (INSERT-EDGE DIGRAPH PREDECESSOR SUCCESSOR)
+
+Insert an edge from `predecessor` to `successor` if not already present.
+
+ The `predecessor` and `successor` vertices must exist in the graph already.
+
+ Returns `t` if the edge was already in the graph, or `nil` if it was
+ inserted.
+
+
+
+### `INSERT-VERTEX` (function)
+
+ (INSERT-VERTEX DIGRAPH VERTEX)
+
+Insert `vertex` into the graph if it is not already a member.
+
+ Returns `t` if the vertex was already in the graph, or `nil` if it was
+ inserted.
+
+
+
+### `MAKE-DIGRAPH` (function)
+
+ (MAKE-DIGRAPH &KEY INITIAL-VERTICES (TEST #'EQL) (HASH-FUNCTION NIL))
+
+Create and return a new digraph.
+
+ `initial-vertices` can be a sequence of vertices to add to the graph.
+
+ `test` should be one of the hash table equality predicates.
+
+ If your Lisp implementation supports the `:hash-function` argument for
+ creating hash tables with custom predicates, you can specify one with
+ `hash-function`.
+
+
+
+### `MAP-BREADTH-FIRST` (function)
+
+ (MAP-BREADTH-FIRST FUNCTION DIGRAPH START-VERTEX)
+
+Apply `function` to the vertices of a breadth-first traversal of `digraph`.
+
+ Returns a fresh list with the results.
+
+ Vertices are processed in breadth-first order, beginning at `start-vertex`,
+ and the resulting list has this order as well.
+
+ Cycles in the graph will not be traversed into.
+
+
+
+### `MAP-DEPTH-FIRST` (function)
+
+ (MAP-DEPTH-FIRST FUNCTION DIGRAPH START-VERTEX)
+
+Apply `function` to the vertices of a breadth-first traversal of `digraph`.
+
+ Returns a fresh list with the results.
+
+ Vertices are processed in depth-first order, beginning at `start-vertex`, and
+ the resulting list has this order as well.
+
+ Cycles in the graph will not be traversed into.
+
+
+
+### `MAP-EDGES` (function)
+
+ (MAP-EDGES FUNCTION DIGRAPH)
+
+Return a fresh list with the results of calling `function` on each edge.
+
+ For each edge, `function` will be called once with two arguments:
+
+ (function predecessor successor)
+
+ The order of the resulting list is unspecified.
+
+
+
+### `MAP-VERTICES` (function)
+
+ (MAP-VERTICES FUNCTION DIGRAPH)
+
+Return a fresh list with the results of calling `function` on each vertex.
+
+ The order of the resulting list is unspecified.
+
+
+
+### `MAPC-BREADTH-FIRST` (function)
+
+ (MAPC-BREADTH-FIRST FUNCTION DIGRAPH START-VERTEX)
+
+Apply `function` to the vertices of a breadth-first traversal of `digraph`.
+
+ Returns `nil`.
+
+ Vertices are processed in breadth-first order, beginning at `start-vertex`.
+
+ Cycles in the graph will not be traversed into.
+
+
+
+### `MAPC-DEPTH-FIRST` (function)
+
+ (MAPC-DEPTH-FIRST FUNCTION DIGRAPH START-VERTEX)
+
+Apply `function` to the vertices of a depth-first traversal of `digraph`.
+
+ Returns `nil`.
+
+ Vertices are processed in depth-first order, beginning at `start-vertex`.
+
+ Cycles in the graph will not be traversed into.
+
+
+
+### `MAPC-EDGES` (function)
+
+ (MAPC-EDGES FUNCTION DIGRAPH)
+
+Call `function` on each edge in `digraph`.
+
+ For each edge, `function` will be called once with two arguments:
+
+ (function predecessor successor)
+
+ The order in which the edges are processed is unspecified.
+
+ Returns `nil`.
+
+
+
+### `MAPC-VERTICES` (function)
+
+ (MAPC-VERTICES FUNCTION DIGRAPH)
+
+Call `function` on each vertex in `digraph`.
+
+ The order in which the vertices are processed is unspecified.
+
+ Returns `nil`.
+
+
+
+### `NEIGHBORS` (function)
+
+ (NEIGHBORS DIGRAPH VERTEX)
+
+Return a fresh list of the neighbors of `vertex`.
+
+### `PREDECESSORS` (function)
+
+ (PREDECESSORS DIGRAPH VERTEX)
+
+Return a fresh list of the predecessors of `vertex`.
+
+### `REMOVE-EDGE` (function)
+
+ (REMOVE-EDGE DIGRAPH PREDECESSOR SUCCESSOR)
+
+Remove an edge from `predecessor` to `successor` if present.
+
+ Returns `t` if there was such an edge, or `nil` if not.
+
+
+
+### `REMOVE-VERTEX` (function)
+
+ (REMOVE-VERTEX DIGRAPH VERTEX)
+
+Remove `vertex` from the graph if present.
+
+ If there are any edges to/from `vertex` they will be automatically removed.
+
+ Returns `t` if there was such a vertex, or `nil` if not.
+
+
+
+### `SUCCESSORS` (function)
+
+ (SUCCESSORS DIGRAPH VERTEX)
+
+Return a fresh list of the successors of `vertex`.
+
+### `TOPOLOGICAL-SORT` (function)
+
+ (TOPOLOGICAL-SORT DIGRAPH)
+
+Return a fresh list of the vertices of `digraph` in topological order.
+
+ Edges are treated as meaning "depends on", so an edge `A --> B` means "A
+ depends on B" and that B must come before A in the resulting list. Aside
+ from this restriction, the order of the resulting list is arbitrary.
+
+ The order in which the vertices are processed is unspecified.
+
+ An error will be signaled if the graph contains a cycle.
+
+
+
+### `VERTICES` (function)
+
+ (VERTICES DIGRAPH)
+
+Return a fresh list of the vertices of `digraph`.
+
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/docs/04-reference-dot.markdown Sun Nov 06 23:49:16 2016 +0000
@@ -0,0 +1,15 @@
+# cl-dot Support
+
+cl-digraph includes support for drawing digraphs with Graphviz using `cl-dot`
+ in the `cl-digraphs.dot` system.
+
+ [TOC]
+
+## Package `DIGRAPH.DOT`
+
+### `DRAW` (function)
+
+ (DRAW DIGRAPH &KEY (FILENAME digraph.png) (FORMAT :PNG))
+
+Draw `digraph` with cl-dot.
+
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/docs/05-changelog.markdown Sun Nov 06 23:49:16 2016 +0000
@@ -0,0 +1,11 @@
+Changelog
+=========
+
+Here's the list of changes in each released version.
+
+[TOC]
+
+v1.0.0
+------
+
+Initial version.
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/docs/api.lisp Sun Nov 06 23:49:16 2016 +0000
@@ -0,0 +1,30 @@
+(ql:quickload "cl-d-api")
+
+(defparameter *header*
+ "The following is a list of all user-facing parts of cl-digraph.
+
+If there are backwards-incompatible changes to anything listed here, they will
+be noted in the changelog and the author will feel bad.
+
+Anything not listed here is subject to change at any time with no warning, so
+don't touch it.
+
+")
+
+(d-api:generate-documentation
+ :cl-digraph
+ #p"docs/03-reference.markdown"
+ (list "DIGRAPH")
+ *header*
+ :title "API Reference")
+
+(d-api:generate-documentation
+ :cl-digraph.dot
+ #p"docs/04-reference-dot.markdown"
+ (list "DIGRAPH.DOT")
+ "cl-digraph includes support for drawing digraphs with Graphviz using `cl-dot`
+ in the `cl-digraphs.dot` system.
+
+ "
+ :title "cl-dot Support")
+
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/docs/footer.markdown Sun Nov 06 23:49:16 2016 +0000
@@ -0,0 +1,14 @@
+<i>Made with Lisp and love by [Steve Losh][] in Reykjavík, Iceland.</i>
+
+[Steve Losh]: http://stevelosh.com/
+
+<script>
+ (function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){
+ (i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
+ m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
+ })(window,document,'script','//www.google-analytics.com/analytics.js','ga');
+
+ ga('create', 'UA-15328874-3', 'auto');
+ ga('send', 'pageview');
+
+</script>
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/docs/index.markdown Sun Nov 06 23:49:16 2016 +0000
@@ -0,0 +1,15 @@
+cl-digraph is an implementation of a mutable [directed graph][] data structure
+for Common Lisp.
+
+[directed graph]: https://en.wikipedia.org/wiki/Directed_graph
+
+* **License:** MIT/X11
+* **Documentation:** <http://sjl.bitbucket.org/cl-digraph/>
+* **Mercurial:** <http://bitbucket.org/sjl/cl-digraph/>
+* **Git:** <http://github.com/sjl/cl-digraph/>
+
+cl-digraph focuses on simplicity, correctness, and usability. Performance is
+not *terrible*, but is not a high priority.
+
+The test suite currently passes in SBCL, CCL, ECL, and ABCL on OS X. Further
+testing is welcome.
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/docs/title Sun Nov 06 23:49:16 2016 +0000
@@ -0,0 +1,1 @@
+cl-digraph
--- a/package.lisp Sun Nov 06 21:22:16 2016 +0000
+++ b/package.lisp Sun Nov 06 23:49:16 2016 +0000
@@ -27,8 +27,6 @@
:count-vertices
:count-edges
- :do-vertices
- :do-edges
:mapc-vertices
:mapc-edges
:map-vertices
@@ -39,4 +37,6 @@
:mapc-depth-first
:mapc-breadth-first
+ :topological-sort
+
:copy-digraph))
--- a/src/directed-graph.lisp Sun Nov 06 21:22:16 2016 +0000
+++ b/src/directed-graph.lisp Sun Nov 06 23:49:16 2016 +0000
@@ -17,9 +17,10 @@
;;;; Data ---------------------------------------------------------------------
(defclass digraph ()
- ((nodes :initarg :nodes :accessor digraph-nodes)
- (test :initarg :test :accessor digraph-test)
- (hash-function :initarg :hash-function :accessor digraph-hash-function)))
+ ((nodes :initarg :nodes :reader digraph-nodes)
+ (test :initarg :test :reader digraph-test)
+ (hash-function :initarg :hash-function :reader digraph-hash-function))
+ (:documentation "A directed graph. Use `make-digraph` to create one."))
(defun make-digraph (&key initial-vertices
(test #'eql)
@@ -104,7 +105,7 @@
(nth-value 1 (gethash vertex (digraph-nodes digraph))))
(defun contains-edge-p (digraph predecessor successor)
- "Return whether the graph contains and edge from `predecessor` to `successor`."
+ "Return whether the graph contains an edge from `predecessor` to `successor`."
(ensure-boolean (member successor (succ digraph predecessor)
:test (digraph-test digraph))))
@@ -399,10 +400,8 @@
(mapc #'visit (roots digraph))))
nil)
-(defun topological-sort (function digraph)
- "Apply `function` to the vertices of `digraph` in topological order.
-
- Returns a fresh list with the results.
+(defun topological-sort (digraph)
+ "Return a fresh list of the vertices of `digraph` in topological order.
Edges are treated as meaning \"depends on\", so an edge `A --> B` means \"A
depends on B\" and that B must come before A in the resulting list. Aside
@@ -414,7 +413,7 @@
"
(let ((result nil))
- (topological-sort% (lambda (v) (push (funcall function v) result)) digraph)
+ (topological-sort% (lambda (v) (push v result)) digraph)
(nreverse result)))
--- a/src/dot.lisp Sun Nov 06 21:22:16 2016 +0000
+++ b/src/dot.lisp Sun Nov 06 23:49:16 2016 +0000
@@ -29,11 +29,12 @@
(successors *current-digraph* vertex))
-(defun draw (digraph &key (filename "digraph.png"))
+(defun draw (digraph &key (filename "digraph.png") (format :png))
+ "Draw `digraph` with cl-dot."
(let ((*current-digraph* digraph))
(cl-dot:dot-graph
(cl-dot:generate-graph-from-roots 'digraph (find-dot-roots digraph))
filename
- :format :png))
+ :format format))
digraph)
--- a/test/tests.lisp Sun Nov 06 21:22:16 2016 +0000
+++ b/test/tests.lisp Sun Nov 06 23:49:16 2016 +0000
@@ -18,28 +18,35 @@
;;;; Tests --------------------------------------------------------------------
(define-test make-digraph
(let ((g (make-digraph)))
- (is (zerop (size g)))
+ (is (zerop (count-vertices g)))
(is (same () (vertices g)))
(is (same () (edges g))))
(let ((g (make-digraph :initial-vertices '(a b c))))
- (is (= 3 (size g)))
+ (is (= 3 (count-vertices g)))
(is (same '(a b c) (vertices g)))
(is (same () (edges g))))
(let ((g (make-digraph :initial-vertices '(a b a c a a))))
- (is (= 3 (size g)))
+ (is (= 3 (count-vertices g)))
(is (same '(a b c) (vertices g)))
(is (same () (edges g)))))
(define-test insert-vertex
(let ((g (make-digraph)))
+ (is (= 0 (count-vertices g)))
+ (is (same '() (vertices g)))
+
(insert-vertex g 'a)
+ (is (= 1 (count-vertices g)))
+ (is (same '(a) (vertices g)))
+
(insert-vertex g 'b)
- (insert-vertex g 'c)
+ (is (= 2 (count-vertices g)))
+ (is (same '(a b) (vertices g)))
+
(insert-vertex g 'a) ; dup
- (is (= 3 (size g)))
- (is (same '(a b c) (vertices g)))
- (is (same () (edges g)))))
+ (is (= 2 (count-vertices g)))
+ (is (same '(a b) (vertices g)))))
(define-test insert-edge
(let ((g (make-digraph :initial-vertices '(a b c))))