This is the cl-digraph Reference Manual, version 1.4.0, generated automatically by Declt version 4.0 beta 2 "William Riker" on Sun Dec 15 04:50:15 2024 GMT+0.
The main system appears first, followed by any subsystem dependency.
cl-digraphSimple directed graphs for Common Lisp.
Steve Losh <steve@stevelosh.com>
MIT/X11
1.4.0
vendor (module).
package.lisp (file).
src (module).
Modules are listed depth-first from the system components tree.
cl-digraph/vendorcl-digraph (system).
quickutils-package.lisp (file).
quickutils.lisp (file).
cl-digraph/srcpackage.lisp (file).
cl-digraph (system).
directed-graph.lisp (file).
Files are sorted by type and then listed depth-first from the systems components trees.
cl-digraph/cl-digraph.asdcl-digraph/vendor/quickutils-package.lispcl-digraph/vendor/quickutils.lispcl-digraph/package.lispcl-digraph/src/directed-graph.lispcl-digraph/vendor/quickutils-package.lispvendor (module).
*utilities* (special variable).
cl-digraph/vendor/quickutils.lispquickutils-package.lisp (file).
vendor (module).
appendf (macro).
compose (compiler macro).
compose (function).
curry (compiler macro).
curry (function).
dohash (macro).
ensure-boolean (function).
ensure-gethash (macro).
ensure-list (function).
hash-table-keys (function).
maphash-keys (function).
mkstr (function).
once-only (macro).
rcurry (function).
removef (macro).
symb (function).
with-gensyms (macro).
with-unique-names (macro).
ensure-function (function).
make-gensym-list (function).
remove/swapped-arguments (function).
string-designator (type).
cl-digraph/package.lispvendor (module).
cl-digraph (system).
cl-digraph/src/directed-graph.lispsrc (module).
arbitrary-vertex (function).
build-from-leafs (function).
build-from-roots (function).
contains-edge-p (function).
contains-vertex-p (function).
copy-digraph (function).
count-edges (function).
count-vertices (function).
degree (function).
degree-in (function).
degree-out (function).
digraph (class).
digraph-error (condition).
edges (function).
emptyp (function).
insert-edge (function).
insert-vertex (function).
leafp (function).
leafs (function).
make-digraph (function).
map-breadth-first (function).
map-depth-first (function).
map-edges (function).
map-vertices (function).
mapc-breadth-first (function).
mapc-depth-first (function).
mapc-edges (function).
mapc-vertices (function).
missing-predecessor (condition).
missing-successor (condition).
missing-vertex (condition).
neighbors (function).
predecessors (function).
print-object (method).
reachablep (function).
remove-edge (function).
remove-vertex (function).
rootp (function).
roots (function).
successors (function).
topological-sort (function).
topological-sort-cycle (condition).
vertex-involved (generic reader).
vertices (function).
digraph-hash-function (reader method).
digraph-nodes (reader method).
digraph-test (reader method).
do-edges (macro).
do-vertices (macro).
find-vertex-if (function).
insert-chain (function).
make-hash-table-portably (function).
pred (macro).
succ (macro).
topological-sort% (function).
Packages are listed by definition order.
digraph.quickutilsPackage that contains Quickutil utility functions.
common-lisp.
appendf (macro).
compose (compiler macro).
compose (function).
curry (compiler macro).
curry (function).
dohash (macro).
ensure-boolean (function).
ensure-gethash (macro).
ensure-list (function).
hash-table-keys (function).
maphash-keys (function).
mkstr (function).
once-only (macro).
rcurry (function).
removef (macro).
symb (function).
with-gensyms (macro).
with-unique-names (macro).
*utilities* (special variable).
ensure-function (function).
make-gensym-list (function).
remove/swapped-arguments (function).
string-designator (type).
digraphcommon-lisp.
digraph.quickutils.
arbitrary-vertex (function).
build-from-leafs (function).
build-from-roots (function).
contains-edge-p (function).
contains-vertex-p (function).
copy-digraph (function).
count-edges (function).
count-vertices (function).
degree (function).
degree-in (function).
degree-out (function).
digraph (class).
digraph-error (condition).
edges (function).
emptyp (function).
insert-edge (function).
insert-vertex (function).
leafp (function).
leafs (function).
make-digraph (function).
map-breadth-first (function).
map-depth-first (function).
map-edges (function).
map-vertices (function).
mapc-breadth-first (function).
mapc-depth-first (function).
mapc-edges (function).
mapc-vertices (function).
missing-predecessor (condition).
missing-successor (condition).
missing-vertex (condition).
neighbors (function).
predecessors (function).
reachablep (function).
remove-edge (function).
remove-vertex (function).
rootp (function).
roots (function).
successors (function).
topological-sort (function).
topological-sort-cycle (condition).
vertex-involved (generic reader).
vertices (function).
digraph-hash-function (generic reader).
digraph-nodes (generic reader).
digraph-test (generic reader).
do-edges (macro).
do-vertices (macro).
find-vertex-if (function).
insert-chain (function).
make-hash-table-portably (function).
pred (macro).
succ (macro).
topological-sort% (function).
Definitions are sorted by export status, category, package, and then by lexicographic order.
Modify-macro for ‘append‘. Appends ‘lists‘ to the place designated by the first argument.
Iterate over the hash table ‘table‘, executing ‘body‘, with ‘key‘ and ‘value‘ bound to the keys and values of the hash table respectively. Return ‘result‘ from the iteration form.
Like ‘gethash‘, but if ‘key‘ is not found in the ‘hash-table‘ saves the ‘default‘ under key before returning it. Secondary return value is true if key was already in the table.
Evaluates ‘forms‘ with symbols specified in ‘specs‘ rebound to temporary
variables, ensuring that each initform is evaluated only once.
Each of ‘specs‘ must either be a symbol naming the variable to be rebound, or of
the form:
(symbol initform)
Bare symbols in ‘specs‘ are equivalent to
(symbol symbol)
Example:
(defmacro cons1 (x) (once-only (x) ‘(cons ,x ,x)))
(let ((y 0)) (cons1 (incf y))) => (1 . 1)
Modify-macro for ‘remove‘. Sets place designated by the first argument to the result of calling ‘remove‘ with ‘item‘, place, and the ‘keyword-arguments‘.
Binds each variable named by a symbol in ‘names‘ to a unique symbol around
‘forms‘. Each of ‘names‘ must either be either a symbol, or of the form:
(symbol string-designator)
Bare symbols appearing in ‘names‘ are equivalent to:
(symbol symbol)
The string-designator is used as the argument to ‘gensym‘ when constructing the unique symbol the named variable will be bound to.
Binds each variable named by a symbol in ‘names‘ to a unique symbol around
‘forms‘. Each of ‘names‘ must either be either a symbol, or of the form:
(symbol string-designator)
Bare symbols appearing in ‘names‘ are equivalent to:
(symbol symbol)
The string-designator is used as the argument to ‘gensym‘ when constructing the unique symbol the named variable will be bound to.
Return an arbitrary vertex of ‘digraph‘ and ‘t‘.
If the digraph is empty, ‘(values nil nil)‘ will be returned instead.
Build a fresh ‘digraph‘ starting from ‘leafs‘ using ‘predecessor-function‘.
This is a convenience function to build a digraph object if you have some
leafs and a function that can find their parents.
‘leafs‘ must be a list.
‘predecessor-function‘ must be a function that takes a vertex and returns
a list of its predecessors.
Build a fresh ‘digraph‘ starting from ‘roots‘ using ‘successor-function‘.
This is a convenience function to build a digraph object if you have some
roots and a function that can find their children.
‘roots‘ must be a list.
‘successor-function‘ must be a function that takes a vertex and returns a list
of its successors.
Returns a function composed of ‘function‘ and ‘more-functions‘ that applies its ; arguments to to each in turn, starting from the rightmost of ‘more-functions‘, and then calling the next one with the primary value of the last.
Return whether the graph contains an edge from ‘predecessor‘ to ‘successor‘.
Return whether the graph contains ‘vertex‘.
Create a fresh copy of ‘digraph‘.
The vertex objects themselves are not copied, but everything else is.
Return the number of edges in ‘digraph‘.
Return the number of vertices in ‘digraph‘.
Returns a function that applies ‘arguments‘ and the arguments it is called with to ‘function‘.
Return the number of neighbors of ‘vertex‘.
Return the number of predecessors of ‘vertex‘.
Return the number of successors of ‘vertex‘.
Return a fresh list of the edges of ‘digraph‘.
Each edge will be a cons of the form ‘(predecessor . successor)‘.
Return ‘t‘ if ‘digraph‘ has no vertices or edges, ‘nil‘ otherwise.
Convert ‘x‘ into a Boolean value.
If ‘list‘ is a list, it is returned. Otherwise returns the list designated by ‘list‘.
Returns a list containing the keys of hash table ‘table‘.
Insert an edge from ‘predecessor‘ to ‘successor‘ if not already present.
Returns ‘t‘ if the edge was already in the graph, or ‘nil‘ if it was
inserted.
The ‘predecessor‘ and ‘successor‘ vertices must already exist in the graph.
If ‘predecessor‘ is not in the graph a ‘missing-predecessor‘ error will be
signaled. Otherwise, if ‘successor‘ is not in the graph, a ‘missing-successor‘
error will be signaled.
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.
Return whether ‘vertex‘ is a leaf vertex in ‘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).
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‘.
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.
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.
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.
Return a fresh list with the results of calling ‘function‘ on each vertex.
The order of the resulting list is unspecified.
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.
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.
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‘.
Call ‘function‘ on each vertex in ‘digraph‘.
The order in which the vertices are processed is unspecified.
Returns ‘nil‘.
Like ‘maphash‘, but calls ‘function‘ with each key in the hash table ‘table‘.
Receives any number of objects (string, symbol, keyword, char, number), extracts all printed representations, and concatenates them all into one string.
Extracted from _On Lisp_, chapter 4.
Return a fresh list of the neighbors of ‘vertex‘.
Return a fresh list of the predecessors of ‘vertex‘.
Returns a function that applies the arguments it is called with and ‘arguments‘ to ‘function‘.
Return ‘t‘ if it is possible to reach ‘target‘ from ‘start‘, otherwise ‘nil‘.
All vertices are reachable from themselves.
Otherwise a ‘target‘ is reachable from ‘start‘ if a directed path exists from
the start to the target.
‘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 an edge from ‘predecessor‘ to ‘successor‘ if present.
Returns ‘t‘ if there was such an edge, or ‘nil‘ if not.
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.
Return whether ‘vertex‘ is a root vertex in ‘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).
Return a fresh list of the successors of ‘vertex‘.
Receives any number of objects, concatenates all into one string with ‘#’mkstr‘ and converts them to symbol.
Extracted from _On Lisp_, chapter 4.
See also: ‘symbolicate‘
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.
A ‘topological-sort-cycle‘ error will be signaled if the graph contains
a cycle.
Return a fresh list of the vertices of ‘digraph‘.
Retrieve the vertex involved in the condition.
missing-vertex)) ¶topological-sort-cycle)) ¶Base condition for digraph-related errors.
error.
An error signaled when trying to insert an edge whose predecessor is not in the graph.
‘vertex-involved‘ can be used to retrieve the offending predecessor.
An error signaled when trying to insert an edge whose successor is not in the graph.
‘vertex-involved‘ can be used to retrieve the offending successor.
Base condition for errors signaled when inserting an edge with a vertex missing.
:vertex-involved
This slot is read-only.
An error signaled when topologically sorting a graph that contains a cycle.
‘vertex-involved‘ can be used to retrieve one of the vertices involved in a cycle. Which vertex in the cycle is chosen is arbitrary.
:vertex-involved
This slot is read-only.
A directed graph. Use ‘make-digraph‘ to create one.
Returns the function designated by ‘function-designator‘:
if ‘function-designator‘ is a function, it is returned, otherwise
it must be a function name and its ‘fdefinition‘ is returned.
Insert edges between a series of vertices.
Give a series of vertices ‘V0 V1 ... Vn‘, edges between each will be inserted
if not already present:
V0 -> V1 -> ... -> Vn
All vertices must exist in the graph already.
Returns ‘nil‘.
Returns a list of ‘length‘ gensyms, each generated as if with a call to ‘make-gensym‘, using the second (optional, defaulting to ‘"G"‘) argument.
A string designator type. A string designator is either a string, a symbol, or a character.
| Jump to: | A B C D E F G H I L M N O P R S T V W |
|---|
| Jump to: | A B C D E F G H I L M N O P R S T V W |
|---|
| Jump to: | *
H N S T V |
|---|
| Jump to: | *
H N S T V |
|---|
| Jump to: | C D F M P Q S T V |
|---|
| Jump to: | C D F M P Q S T V |
|---|