# HG changeset patch # User Steve Losh # Date 1478476156 0 # Node ID 412a127b74190bac314618d0b9886c0457586c1f # Parent 1b9b79185f177683766c23d30acf9e0c6245ee11 Add some documentation diff -r 1b9b79185f17 -r 412a127b7419 .hgignore --- 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 diff -r 1b9b79185f17 -r 412a127b7419 Makefile --- 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 diff -r 1b9b79185f17 -r 412a127b7419 docs/01-installation.markdown --- /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 diff -r 1b9b79185f17 -r 412a127b7419 docs/02-usage.markdown --- /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) + ; => + # + +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 diff -r 1b9b79185f17 -r 412a127b7419 docs/03-reference.markdown --- /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`. + diff -r 1b9b79185f17 -r 412a127b7419 docs/04-reference-dot.markdown --- /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. + diff -r 1b9b79185f17 -r 412a127b7419 docs/05-changelog.markdown --- /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. diff -r 1b9b79185f17 -r 412a127b7419 docs/api.lisp --- /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") + diff -r 1b9b79185f17 -r 412a127b7419 docs/footer.markdown --- /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 @@ +Made with Lisp and love by [Steve Losh][] in Reykjavík, Iceland. + +[Steve Losh]: http://stevelosh.com/ + + diff -r 1b9b79185f17 -r 412a127b7419 docs/index.markdown --- /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:** +* **Mercurial:** +* **Git:** + +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. diff -r 1b9b79185f17 -r 412a127b7419 docs/title --- /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 diff -r 1b9b79185f17 -r 412a127b7419 package.lisp --- 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)) diff -r 1b9b79185f17 -r 412a127b7419 src/directed-graph.lisp --- 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))) diff -r 1b9b79185f17 -r 412a127b7419 src/dot.lisp --- 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) diff -r 1b9b79185f17 -r 412a127b7419 test/tests.lisp --- 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))))