docs/03-reference.markdown @ 7e80eda84170 v1.4.0

# 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`

### `ARBITRARY-VERTEX` (function)

    (ARBITRARY-VERTEX DIGRAPH)

Return an arbitrary vertex of `digraph` and `t`.

  If the digraph is empty, `(values nil nil)` will be returned instead.

  

### `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.

### `DIGRAPH-ERROR` (class)

Base condition for digraph-related errors.

### `EDGES` (function)

    (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)

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

### `INSERT-EDGE` (function)

    (INSERT-EDGE DIGRAPH PREDECESSOR SUCCESSOR)

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` (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.

  

### `LEAFP` (function)

    (LEAFP DIGRAPH VERTEX)

Return whether `vertex` is a leaf vertex in `digraph`.

### `LEAFS` (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).

  

### `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`.

  

### `MISSING-PREDECESSOR` (class)

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.

### `MISSING-SUCCESSOR` (class)

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.

### `MISSING-VERTEX` (class)

Base condition for errors signaled when inserting an edge with a vertex missing.

### `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`.

### `REACHABLEP` (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`.

  

### `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.

  

### `ROOTP` (function)

    (ROOTP DIGRAPH VERTEX)

Return whether `vertex` is a root vertex in `digraph`.

### `ROOTS` (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).

  

### `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.

  A `topological-sort-cycle` error will be signaled if the graph contains
  a cycle.

  

### `TOPOLOGICAL-SORT-CYCLE` (class)

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` (generic function)

    (VERTEX-INVOLVED CONDITION)

Retrieve the vertex involved in the condition.

### `VERTICES` (function)

    (VERTICES DIGRAPH)

Return a fresh list of the vertices of `digraph`.