cl-digraph

API Reference

cl-digraph

Simple directed graphs for Common Lisp.

DIGRAPH.QUICKUTILS

Package that contains Quickutil utility functions.
  • Macro APPENDF (place &rest lists &environment env)
    Modify-macro for `append`. Appends `lists` to the place designated by the first argument.
  • Function COMPOSE (function &rest more-functions)
    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.
  • Function CURRY (function &rest arguments)
    Returns a function that applies `arguments` and the arguments it is called with to `function`.
  • Macro DOHASH ((key value table &optional result) &body body)
    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.
  • Function ENSURE-BOOLEAN (x)
    Convert `x` into a Boolean value.
  • Macro ENSURE-GETHASH (key hash-table &optional default)
    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.
  • Function ENSURE-LIST (list)
    If `list` is a list, it is returned. Otherwise returns the list designated by `list`.
  • Function MAPHASH-KEYS (function table)
    Like `maphash`, but calls `function` with each key in the hash table `table`.
  • Function HASH-TABLE-KEYS (table)
    Returns a list containing the keys of hash table `table`.
  • Function MKSTR (&rest args)
    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.
  • Macro ONCE-ONLY (specs &body forms)
    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)
  • Function RCURRY (function &rest arguments)
    Returns a function that applies the arguments it is called with and `arguments` to `function`.
  • Macro REMOVEF (place item &rest remove-keywords &environment env)
    Modify-macro for `remove`. Sets place designated by the first argument to the result of calling `remove` with `item`, place, and the `keyword-arguments`.
  • Function SYMB (&rest args)
    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`
  • Macro WITH-GENSYMS (names &body forms)
    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.
  • Macro WITH-UNIQUE-NAMES (names &body forms)
    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.

DIGRAPH

  • Class DIGRAPH
    A directed graph. Use `make-digraph` to create one.
    NODES   Reader: DIGRAPH-NODES
    TEST   Reader: DIGRAPH-TEST
    HASH-FUNCTION   Reader: DIGRAPH-HASH-FUNCTION
  • 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`.
  • Function EMPTYP (digraph)
    Return `t` if `digraph` has no vertices or edges, `nil` otherwise.
  • Function VERTICES (digraph)
    Return a fresh list of the vertices of `digraph`.
  • Function EDGES (digraph)
    Return a fresh list of the edges of `digraph`. Each edge will be a cons of the form `(predecessor . successor)`.
  • Function PREDECESSORS (digraph vertex)
    Return a fresh list of the predecessors of `vertex`.
  • Function SUCCESSORS (digraph vertex)
    Return a fresh list of the successors of `vertex`.
  • Function NEIGHBORS (digraph vertex)
    Return a fresh list of the neighbors of `vertex`.
  • Function CONTAINS-VERTEX-P (digraph vertex)
    Return whether the graph contains `vertex`.
  • Function CONTAINS-EDGE-P (digraph predecessor successor)
    Return whether the graph contains an edge from `predecessor` to `successor`.
  • 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.
  • 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.
  • 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.
  • 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.
  • Function DEGREE (digraph vertex)
    Return the number of neighbors of `vertex`.
  • Function DEGREE-IN (digraph vertex)
    Return the number of predecessors of `vertex`.
  • Function DEGREE-OUT (digraph vertex)
    Return the number of successors of `vertex`.
  • Function COUNT-VERTICES (digraph)
    Return the number of vertices in `digraph`.
  • Function COUNT-EDGES (digraph)
    Return the number of edges in `digraph`.
  • Function ROOTP (digraph vertex)
    Return whether `vertex` is a root vertex in `digraph`.
  • Function LEAFP (digraph vertex)
    Return whether `vertex` is a leaf vertex in `digraph`.
  • Function MAPC-VERTICES (function digraph)
    Call `function` on each vertex in `digraph`. The order in which the vertices are processed is unspecified. Returns `nil`.
  • 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`.
  • 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.
  • 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.
  • Function COPY-DIGRAPH (digraph)
    Create a fresh copy of `digraph`. The vertex objects themselves are not copied, but everything else is.
  • 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.
  • 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.
  • 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.
  • 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.
  • Function ROOTS (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).
  • Function LEAFS (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).
  • 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.
  • Function REACHABLEP (digraph start target &key (strategy :breadth-first))
    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`.

cl-digraph.dot

cl-dot support for cl-digraph

DIGRAPH.DOT

  • Function DRAW (digraph &key (filename "digraph.png") (format :png))
    Draw `digraph` with cl-dot.