Next: Introduction, Previous: (dir), Up: (dir) [Contents][Index]
This is the cl-digraph Reference Manual, version 1.4.0, generated automatically by Declt version 4.0 beta 2 "William Riker" on Tue Nov 15 04:40:08 2022 GMT+0.
Next: Systems, Previous: The cl-digraph Reference Manual, Up: The cl-digraph Reference Manual [Contents][Index]
cl-digraph is an implementation of a mutable directed graph data structure for Common Lisp.
cl-digraph focuses on simplicity, correctness, and usability. Performance is not terrible, but is not a high priority.
It is currently not thread-safe, but this may happen in the future.
The test suite currently passes in SBCL, CCL, ECL, and ABCL on OS X and Debian. Further testing is welcome.
Next: Modules, Previous: Introduction, Up: The cl-digraph Reference Manual [Contents][Index]
The main system appears first, followed by any subsystem dependency.
Simple directed graphs for Common Lisp.
Steve Losh <steve@stevelosh.com>
MIT/X11
1.4.0
Next: Files, Previous: Systems, Up: The cl-digraph Reference Manual [Contents][Index]
Modules are listed depth-first from the system components tree.
Next: cl-digraph/src, Previous: Modules, Up: Modules [Contents][Index]
cl-digraph (system).
Previous: cl-digraph/vendor, Up: Modules [Contents][Index]
package.lisp (file).
cl-digraph (system).
directed-graph.lisp (file).
Next: Packages, Previous: Modules, Up: The cl-digraph Reference Manual [Contents][Index]
Files are sorted by type and then listed depth-first from the systems components trees.
Next: cl-digraph/vendor/quickutils-package.lisp, Previous: Lisp, Up: Lisp [Contents][Index]
cl-digraph (system).
Next: cl-digraph/vendor/quickutils.lisp, Previous: cl-digraph/cl-digraph.asd, Up: Lisp [Contents][Index]
vendor (module).
*utilities* (special variable).
Next: cl-digraph/package.lisp, Previous: cl-digraph/vendor/quickutils-package.lisp, Up: Lisp [Contents][Index]
quickutils-package.lisp (file).
vendor (module).
Next: cl-digraph/src/directed-graph.lisp, Previous: cl-digraph/vendor/quickutils.lisp, Up: Lisp [Contents][Index]
vendor (module).
cl-digraph (system).
Previous: cl-digraph/package.lisp, Up: Lisp [Contents][Index]
src (module).
Next: Definitions, Previous: Files, Up: The cl-digraph Reference Manual [Contents][Index]
Packages are listed by definition order.
Package that contains Quickutil utility functions.
common-lisp.
Previous: digraph.quickutils, Up: Packages [Contents][Index]
Next: Indexes, Previous: Packages, Up: The cl-digraph Reference Manual [Contents][Index]
Definitions are sorted by export status, category, package, and then by lexicographic order.
Next: Internals, Previous: Definitions, Up: Definitions [Contents][Index]
Next: Compiler macros, Previous: Public Interface, Up: Public Interface [Contents][Index]
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.
Next: Ordinary functions, Previous: Macros, Up: Public Interface [Contents][Index]
Next: Generic functions, Previous: Compiler macros, Up: Public Interface [Contents][Index]
Return an arbitrary vertex of ‘digraph‘ and ‘t‘.
If the digraph is empty, ‘(values nil nil)‘ will be returned instead.
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‘.
Next: Standalone methods, Previous: Ordinary functions, Up: Public Interface [Contents][Index]
Retrieve the vertex involved in the condition.
Next: Conditions, Previous: Generic functions, Up: Public Interface [Contents][Index]
Next: Classes, Previous: Standalone methods, Up: Public Interface [Contents][Index]
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.
Previous: Conditions, Up: Public Interface [Contents][Index]
A directed graph. Use ‘make-digraph‘ to create one.
Previous: Public Interface, Up: Definitions [Contents][Index]
Next: Ordinary functions, Previous: Special variables, Up: Internals [Contents][Index]
Next: Generic functions, Previous: Macros, Up: Internals [Contents][Index]
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.
Next: Types, Previous: Ordinary functions, Up: Internals [Contents][Index]
Previous: Generic functions, Up: Internals [Contents][Index]
A string designator type. A string designator is either a string, a symbol, or a character.
Previous: Definitions, Up: The cl-digraph Reference Manual [Contents][Index]
| Jump to: | A C D E F G H I L M N O P R S T V W |
|---|
| Jump to: | A C D E F G H I L M N O P R S T V W |
|---|
Next: Data types, Previous: Functions, Up: Indexes [Contents][Index]
| 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 |
|---|