# HG changeset patch # User Steve Losh # Date 1484955740 0 # Node ID 9133e251a03d604a07aa8bc5692e417817281258 # Parent f3fc28996523c704df2f90c66cd9286d9263c58d cl-digraph: Update site. diff -r f3fc28996523 -r 9133e251a03d cl-digraph/changelog/index.html --- a/cl-digraph/changelog/index.html Fri Dec 23 10:50:32 2016 -0500 +++ b/cl-digraph/changelog/index.html Fri Jan 20 23:42:20 2017 +0000 @@ -15,8 +15,13 @@

Changelog

Here's the list of changes in each released version.

+

v1.1.0

+

Minor internal cleanup.

+

If you pass an invalid strategy argument to reachablep there will now be +a restart available to supply a new value, instead of just crashing and burning.

v1.0.0

Initial version.

diff -r f3fc28996523 -r 9133e251a03d cl-digraph/reference-dot/index.html --- a/cl-digraph/reference-dot/index.html Fri Dec 23 10:50:32 2016 -0500 +++ b/cl-digraph/reference-dot/index.html Fri Jan 20 23:42:20 2017 +0000 @@ -23,7 +23,7 @@

Package DIGRAPH.DOT

DRAW (function)

-
(DRAW DIGRAPH &KEY (FILENAME digraph.png) (FORMAT :PNG))
+
(DRAW DIGRAPH &KEY (FILENAME digraph.png) (FORMAT :PNG))
 
diff -r f3fc28996523 -r 9133e251a03d cl-digraph/reference/index.html --- a/cl-digraph/reference/index.html Fri Dec 23 10:50:32 2016 -0500 +++ b/cl-digraph/reference/index.html Fri Jan 20 23:42:20 2017 +0000 @@ -57,50 +57,50 @@

Package DIGRAPH

CONTAINS-EDGE-P (function)

-
(CONTAINS-EDGE-P DIGRAPH PREDECESSOR SUCCESSOR)
+
(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)
+
(CONTAINS-VERTEX-P DIGRAPH VERTEX)
 

Return whether the graph contains vertex.

COPY-DIGRAPH (function)

-
(COPY-DIGRAPH DIGRAPH)
+
(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)
+
(COUNT-EDGES DIGRAPH)
 

Return the number of edges in digraph.

COUNT-VERTICES (function)

-
(COUNT-VERTICES DIGRAPH)
+
(COUNT-VERTICES DIGRAPH)
 

Return the number of vertices in digraph.

DEGREE (function)

-
(DEGREE DIGRAPH VERTEX)
+
(DEGREE DIGRAPH VERTEX)
 

Return the number of neighbors of vertex.

DEGREE-IN (function)

-
(DEGREE-IN DIGRAPH VERTEX)
+
(DEGREE-IN DIGRAPH VERTEX)
 

Return the number of predecessors of vertex.

DEGREE-OUT (function)

-
(DEGREE-OUT DIGRAPH VERTEX)
+
(DEGREE-OUT DIGRAPH VERTEX)
 
@@ -108,20 +108,20 @@

DIGRAPH (class)

A directed graph. Use make-digraph to create one.

EDGES (function)

-
(EDGES DIGRAPH)
+
(EDGES DIGRAPH)
 

Return a fresh list of the edges of digraph.

Each edge will be a cons of the form (predecessor . successor).

EMPTYP (function)

-
(EMPTYP DIGRAPH)
+
(EMPTYP DIGRAPH)
 

Return t if digraph has no vertices or edges, nil otherwise.

INSERT-EDGE (function)

-
(INSERT-EDGE DIGRAPH PREDECESSOR SUCCESSOR)
+
(INSERT-EDGE DIGRAPH PREDECESSOR SUCCESSOR)
 
@@ -130,7 +130,7 @@

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 DIGRAPH VERTEX)
 
@@ -138,7 +138,7 @@

Returns t if the vertex was already in the graph, or nil if it was inserted.

LEAFS (function)

-
(LEAFS DIGRAPH)
+
(LEAFS DIGRAPH)
 
@@ -146,7 +146,7 @@

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))
+
(MAKE-DIGRAPH &KEY INITIAL-VERTICES (TEST #'EQL) (HASH-FUNCTION NIL))
 
@@ -157,7 +157,7 @@ creating hash tables with custom predicates, you can specify one with hash-function.

MAP-BREADTH-FIRST (function)

-
(MAP-BREADTH-FIRST FUNCTION DIGRAPH START-VERTEX)
+
(MAP-BREADTH-FIRST FUNCTION DIGRAPH START-VERTEX)
 
@@ -167,7 +167,7 @@ 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)
+
(MAP-DEPTH-FIRST FUNCTION DIGRAPH START-VERTEX)
 
@@ -177,26 +177,26 @@ the resulting list has this order as well.

Cycles in the graph will not be traversed into.

MAP-EDGES (function)

-
(MAP-EDGES FUNCTION DIGRAPH)
+
(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)
+
(function predecessor successor)
 

The order of the resulting list is unspecified.

MAP-VERTICES (function)

-
(MAP-VERTICES FUNCTION DIGRAPH)
+
(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)
+
(MAPC-BREADTH-FIRST FUNCTION DIGRAPH START-VERTEX)
 
@@ -205,7 +205,7 @@

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)
+
(MAPC-DEPTH-FIRST FUNCTION DIGRAPH START-VERTEX)
 
@@ -214,20 +214,20 @@

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)
+
(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)
+
(function predecessor successor)
 

The order in which the edges are processed is unspecified.

Returns nil.

MAPC-VERTICES (function)

-
(MAPC-VERTICES FUNCTION DIGRAPH)
+
(MAPC-VERTICES FUNCTION DIGRAPH)
 
@@ -235,19 +235,19 @@

The order in which the vertices are processed is unspecified.

Returns nil.

NEIGHBORS (function)

-
(NEIGHBORS DIGRAPH VERTEX)
+
(NEIGHBORS DIGRAPH VERTEX)
 

Return a fresh list of the neighbors of vertex.

PREDECESSORS (function)

-
(PREDECESSORS DIGRAPH VERTEX)
+
(PREDECESSORS DIGRAPH VERTEX)
 

Return a fresh list of the predecessors of vertex.

REACHABLEP (function)

-
(REACHABLEP DIGRAPH START TARGET &KEY (STRATEGY :BREADTH-FIRST))
+
(REACHABLEP DIGRAPH START TARGET &KEY (STRATEGY :BREADTH-FIRST))
 
@@ -258,14 +258,14 @@

strategy will be used to determine how to traverse the graph when searching for a path, and can be one of :breadth-first or :depth-first.

REMOVE-EDGE (function)

-
(REMOVE-EDGE DIGRAPH PREDECESSOR SUCCESSOR)
+
(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 DIGRAPH VERTEX)
 
@@ -273,7 +273,7 @@

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.

ROOTS (function)

-
(ROOTS DIGRAPH)
+
(ROOTS DIGRAPH)
 
@@ -281,13 +281,13 @@

This is currently O(vertices).

A root is a vertex with no incoming edges (i.e. in-degree 0).

SUCCESSORS (function)

-
(SUCCESSORS DIGRAPH VERTEX)
+
(SUCCESSORS DIGRAPH VERTEX)
 

Return a fresh list of the successors of vertex.

TOPOLOGICAL-SORT (function)

-
(TOPOLOGICAL-SORT DIGRAPH)
+
(TOPOLOGICAL-SORT DIGRAPH)
 
@@ -298,7 +298,7 @@

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)
+
(VERTICES DIGRAPH)
 
diff -r f3fc28996523 -r 9133e251a03d cl-digraph/usage/index.html --- a/cl-digraph/usage/index.html Fri Dec 23 10:50:32 2016 -0500 +++ b/cl-digraph/usage/index.html Fri Jan 20 23:42:20 2017 +0000 @@ -42,7 +42,7 @@ symbols.

Creating Digraphs

Digraphs can be created with make-digraph:

-
(digraph:make-digraph)
+
(digraph:make-digraph)
 ; =>
 #<DIGRAPH:DIGRAPH () {1002CFD343}>
 
@@ -51,7 +51,7 @@

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:

-
(defparameter *d* (digraph:make-digraph))
+
(defparameter *d* (digraph:make-digraph))
 
 (digraph:vertices *d*)
 ; => ()
@@ -69,7 +69,7 @@
 

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:

-
(defparameter *d* (digraph:make-digraph))
+
(defparameter *d* (digraph:make-digraph))
 
 (digraph:insert-vertex *d* 'foo)
 (digraph:insert-vertex *d* 'foo)
@@ -81,7 +81,7 @@
 
 

You can also specify some initial vertices directly in the make-digraph call if you want:

-
(defparameter *d*
+
(defparameter *d*
   (digraph:make-digraph :initial-vertices '(a b c)))
 
 (digraph:vertices *d*)
@@ -95,7 +95,7 @@
 
 

You can remove vertices with remove-vertex. Removing a vertex that's not in the graph is silently ignored:

-
(defparameter *d*
+
(defparameter *d*
   (digraph:make-digraph :initial-vertices '(a b c)))
 
 (digraph:vertices *d*)
@@ -115,7 +115,7 @@
 

By default cl-digraph compares vertices for equality with eql. You can specify a different equality predicate with the :test argument to make-digraph:

-
(defparameter *d*
+
(defparameter *d*
   (digraph:make-digraph :test #'equal))
 
 (digraph:insert-vertex *d* (list 1 2))
@@ -138,7 +138,7 @@
 

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:

-
(defparameter *d*
+
(defparameter *d*
   (digraph:make-digraph :test #'some-predicate
                         :hash-function #'custom-hash-function))
 
@@ -149,7 +149,7 @@

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  │
 └─────────────┘      └─────────────┘
 
@@ -157,7 +157,7 @@

Edges are added with insert-edge. A list of edges in a digraph can be retrieved with edges:

-
(defparameter *d*
+
(defparameter *d*
   (digraph:make-digraph :initial-vertices '(a b c)))
 
 (digraph:edges *d*)
@@ -175,7 +175,7 @@
 
 

Duplicate edges are silently ignored. The predecessor and successor must both exist in the graph already, or an error will be signaled:

-
(defparameter *d*
+
(defparameter *d*
   (digraph:make-digraph :initial-vertices '(a b c)))
 
 (digraph:insert-edge *d* 'a 'b) ; a -> b
@@ -191,7 +191,7 @@
 
 

Edges can be removed with remove-edge. Removing an edge that's not in the graph is silently ignored:

-
(defparameter *d*
+
(defparameter *d*
   (digraph:make-digraph :initial-vertices '(a b c)))
 
 (digraph:insert-edge *d* 'a 'b) ; a -> b
@@ -208,7 +208,7 @@
 

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:

-
;            ┌───┐      ┌───┐
+
;            ┌───┐      ┌───┐
 ;   ┌───────▶│ B │─────▶│ D │
 ;   │        └───┘      └───┘
 ; ┌───┐
@@ -230,7 +230,7 @@
 themselves.

Vertices and Edges

We've already seen vertices and edges:

-
(digraph:vertices *d*)
+
(digraph:vertices *d*)
 ; => (BAR FOO D C B A)
 
 (digraph:edges *d*)
@@ -243,7 +243,7 @@
 

Neighboring Vertices

The predecessors and successors functions return a list of vertices with edges to/from a particular vertex:

-
(digraph:predecessors *d* 'a) ; => ()
+
(digraph:predecessors *d* 'a) ; => ()
 (digraph:successors *d* 'a)   ; => (b c)
 
 (digraph:predecessors *d* 'bar) ; => (foo bar)
@@ -253,14 +253,14 @@
 
 

neighbors returns all vertices that are a predecessor or successor of the given vertex:

-
(digraph:neighbors *d* 'b) ; => (a d)
+
(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:

-
(digraph:contains-vertex-p *d* 'a)      ; => t
+
(digraph:contains-vertex-p *d* 'a)      ; => t
 (digraph:contains-vertex-p *d* 'horses) ; => nil
 
 (digraph:contains-edge-p *d* 'a 'b)     ; => t
@@ -271,14 +271,14 @@
 

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:

-
(digraph:count-vertices *d*) ; => 6
+
(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:

-
(digraph:predecessors *d* 'a) ; => ()
+
(digraph:predecessors *d* 'a) ; => ()
 (digraph:degree-in    *d* 'a) ; = 0
 
 (digraph:successors *d* 'bar) ; => (bar)
@@ -326,7 +326,7 @@
 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:

-
(defparameter *d*
+
(defparameter *d*
   (digraph:make-digraph :initial-vertices '(a b c d)))
 
 (digraph:insert-edge *d* 'a 'b) ; a depends on b
@@ -344,7 +344,7 @@
 

Drawing

If you have Graphviz installed, you can draw digraph objects to images with the cl-dot library by loading the optional cl-digraph.dot system:

-
(ql:quickload 'cl-digraph.dot)
+
(ql:quickload 'cl-digraph.dot)
 
 (defparameter *d*
   (digraph:make-digraph :initial-vertices '(a b c d foo bar)))