cl-digraph/reference/index.html @ 15d3b832fdc5 default tip
cl-digraph: Update site.
| author | Steve Losh <steve@stevelosh.com> |
|---|---|
| date | Wed, 21 Jun 2023 15:21:12 -0400 |
| parents | 55507a7c499d |
| children | (none) |
<!DOCTYPE html> <html> <head> <meta charset="utf-8"/> <title> API Reference / cl-digraph</title> <link rel="stylesheet" href="../_dmedia/tango.css"/> <link rel="stylesheet/less" type="text/css" href="../_dmedia/style.less"/> <script src="../_dmedia/less.js" type="text/javascript"> </script> </head> <body class="content"> <div class="wrap"> <header><h1><a href="..">cl-digraph</a></h1></header> <div class="markdown"> <h1 id="api-reference"><a href="">API Reference</a></h1><p>The following is a list of all user-facing parts of cl-digraph.</p> <p>If there are backwards-incompatible changes to anything listed here, they will be noted in the changelog and the author will feel bad.</p> <p>Anything not listed here is subject to change at any time with no warning, so don't touch it.</p> <div class="toc"> <ul> <li><a href="#package-digraph">Package DIGRAPH</a><ul> <li><a href="#arbitrary-vertex-function">ARBITRARY-VERTEX (function)</a></li> <li><a href="#build-from-leafs-function">BUILD-FROM-LEAFS (function)</a></li> <li><a href="#build-from-roots-function">BUILD-FROM-ROOTS (function)</a></li> <li><a href="#contains-edge-p-function">CONTAINS-EDGE-P (function)</a></li> <li><a href="#contains-vertex-p-function">CONTAINS-VERTEX-P (function)</a></li> <li><a href="#copy-digraph-function">COPY-DIGRAPH (function)</a></li> <li><a href="#count-edges-function">COUNT-EDGES (function)</a></li> <li><a href="#count-vertices-function">COUNT-VERTICES (function)</a></li> <li><a href="#degree-function">DEGREE (function)</a></li> <li><a href="#degree-in-function">DEGREE-IN (function)</a></li> <li><a href="#degree-out-function">DEGREE-OUT (function)</a></li> <li><a href="#digraph-class">DIGRAPH (class)</a></li> <li><a href="#digraph-error-class">DIGRAPH-ERROR (class)</a></li> <li><a href="#edges-function">EDGES (function)</a></li> <li><a href="#emptyp-function">EMPTYP (function)</a></li> <li><a href="#insert-edge-function">INSERT-EDGE (function)</a></li> <li><a href="#insert-vertex-function">INSERT-VERTEX (function)</a></li> <li><a href="#leafp-function">LEAFP (function)</a></li> <li><a href="#leafs-function">LEAFS (function)</a></li> <li><a href="#make-digraph-function">MAKE-DIGRAPH (function)</a></li> <li><a href="#map-breadth-first-function">MAP-BREADTH-FIRST (function)</a></li> <li><a href="#map-depth-first-function">MAP-DEPTH-FIRST (function)</a></li> <li><a href="#map-edges-function">MAP-EDGES (function)</a></li> <li><a href="#map-vertices-function">MAP-VERTICES (function)</a></li> <li><a href="#mapc-breadth-first-function">MAPC-BREADTH-FIRST (function)</a></li> <li><a href="#mapc-depth-first-function">MAPC-DEPTH-FIRST (function)</a></li> <li><a href="#mapc-edges-function">MAPC-EDGES (function)</a></li> <li><a href="#mapc-vertices-function">MAPC-VERTICES (function)</a></li> <li><a href="#missing-predecessor-class">MISSING-PREDECESSOR (class)</a></li> <li><a href="#missing-successor-class">MISSING-SUCCESSOR (class)</a></li> <li><a href="#missing-vertex-class">MISSING-VERTEX (class)</a></li> <li><a href="#neighbors-function">NEIGHBORS (function)</a></li> <li><a href="#predecessors-function">PREDECESSORS (function)</a></li> <li><a href="#reachablep-function">REACHABLEP (function)</a></li> <li><a href="#remove-edge-function">REMOVE-EDGE (function)</a></li> <li><a href="#remove-vertex-function">REMOVE-VERTEX (function)</a></li> <li><a href="#rootp-function">ROOTP (function)</a></li> <li><a href="#roots-function">ROOTS (function)</a></li> <li><a href="#successors-function">SUCCESSORS (function)</a></li> <li><a href="#topological-sort-function">TOPOLOGICAL-SORT (function)</a></li> <li><a href="#topological-sort-cycle-class">TOPOLOGICAL-SORT-CYCLE (class)</a></li> <li><a href="#vertex-involved-generic-function">VERTEX-INVOLVED (generic function)</a></li> <li><a href="#vertices-function">VERTICES (function)</a></li> </ul> </li> </ul></div> <h2 id="package-digraph">Package <code>DIGRAPH</code></h2> <h3 id="arbitrary-vertex-function"><code>ARBITRARY-VERTEX</code> (function)</h3> <div class="codehilite"><pre><span/>(ARBITRARY-VERTEX DIGRAPH) </pre></div> <p>Return an arbitrary vertex of <code>digraph</code> and <code>t</code>.</p> <p>If the digraph is empty, <code>(values nil nil)</code> will be returned instead.</p> <h3 id="build-from-leafs-function"><code>BUILD-FROM-LEAFS</code> (function)</h3> <div class="codehilite"><pre><span/>(BUILD-FROM-LEAFS LEAFS PREDECESSOR-FUNCTION &KEY (TEST #'EQL) (HASH-FUNCTION NIL)) </pre></div> <p>Build a fresh <code>digraph</code> starting from <code>leafs</code> using <code>predecessor-function</code>.</p> <p>This is a convenience function to build a digraph object if you have some leafs and a function that can find their parents.</p> <p><code>leafs</code> must be a list.</p> <p><code>predecessor-function</code> must be a function that takes a vertex and returns a list of its predecessors.</p> <h3 id="build-from-roots-function"><code>BUILD-FROM-ROOTS</code> (function)</h3> <div class="codehilite"><pre><span/>(BUILD-FROM-ROOTS ROOTS SUCCESSOR-FUNCTION &KEY (TEST #'EQL) (HASH-FUNCTION NIL)) </pre></div> <p>Build a fresh <code>digraph</code> starting from <code>roots</code> using <code>successor-function</code>.</p> <p>This is a convenience function to build a digraph object if you have some roots and a function that can find their children.</p> <p><code>roots</code> must be a list.</p> <p><code>successor-function</code> must be a function that takes a vertex and returns a list of its successors.</p> <h3 id="contains-edge-p-function"><code>CONTAINS-EDGE-P</code> (function)</h3> <div class="codehilite"><pre><span/>(CONTAINS-EDGE-P DIGRAPH PREDECESSOR SUCCESSOR) </pre></div> <p>Return whether the graph contains an edge from <code>predecessor</code> to <code>successor</code>.</p> <h3 id="contains-vertex-p-function"><code>CONTAINS-VERTEX-P</code> (function)</h3> <div class="codehilite"><pre><span/>(CONTAINS-VERTEX-P DIGRAPH VERTEX) </pre></div> <p>Return whether the graph contains <code>vertex</code>.</p> <h3 id="copy-digraph-function"><code>COPY-DIGRAPH</code> (function)</h3> <div class="codehilite"><pre><span/>(COPY-DIGRAPH DIGRAPH) </pre></div> <p>Create a fresh copy of <code>digraph</code>.</p> <p>The vertex objects themselves are not copied, but everything else is.</p> <h3 id="count-edges-function"><code>COUNT-EDGES</code> (function)</h3> <div class="codehilite"><pre><span/>(COUNT-EDGES DIGRAPH) </pre></div> <p>Return the number of edges in <code>digraph</code>.</p> <h3 id="count-vertices-function"><code>COUNT-VERTICES</code> (function)</h3> <div class="codehilite"><pre><span/>(COUNT-VERTICES DIGRAPH) </pre></div> <p>Return the number of vertices in <code>digraph</code>.</p> <h3 id="degree-function"><code>DEGREE</code> (function)</h3> <div class="codehilite"><pre><span/>(DEGREE DIGRAPH VERTEX) </pre></div> <p>Return the number of neighbors of <code>vertex</code>.</p> <h3 id="degree-in-function"><code>DEGREE-IN</code> (function)</h3> <div class="codehilite"><pre><span/>(DEGREE-IN DIGRAPH VERTEX) </pre></div> <p>Return the number of predecessors of <code>vertex</code>.</p> <h3 id="degree-out-function"><code>DEGREE-OUT</code> (function)</h3> <div class="codehilite"><pre><span/>(DEGREE-OUT DIGRAPH VERTEX) </pre></div> <p>Return the number of successors of <code>vertex</code>.</p> <h3 id="digraph-class"><code>DIGRAPH</code> (class)</h3> <p>A directed graph. Use <code>make-digraph</code> to create one.</p> <h3 id="digraph-error-class"><code>DIGRAPH-ERROR</code> (class)</h3> <p>Base condition for digraph-related errors.</p> <h3 id="edges-function"><code>EDGES</code> (function)</h3> <div class="codehilite"><pre><span/>(EDGES DIGRAPH) </pre></div> <p>Return a fresh list of the edges of <code>digraph</code>.</p> <p>Each edge will be a cons of the form <code>(predecessor . successor)</code>.</p> <h3 id="emptyp-function"><code>EMPTYP</code> (function)</h3> <div class="codehilite"><pre><span/>(EMPTYP DIGRAPH) </pre></div> <p>Return <code>t</code> if <code>digraph</code> has no vertices or edges, <code>nil</code> otherwise.</p> <h3 id="insert-edge-function"><code>INSERT-EDGE</code> (function)</h3> <div class="codehilite"><pre><span/>(INSERT-EDGE DIGRAPH PREDECESSOR SUCCESSOR) </pre></div> <p>Insert an edge from <code>predecessor</code> to <code>successor</code> if not already present.</p> <p>Returns <code>t</code> if the edge was already in the graph, or <code>nil</code> if it was inserted.</p> <p>The <code>predecessor</code> and <code>successor</code> vertices must already exist in the graph. If <code>predecessor</code> is not in the graph a <code>missing-predecessor</code> error will be signaled. Otherwise, if <code>successor</code> is not in the graph, a <code>missing-successor</code> error will be signaled.</p> <h3 id="insert-vertex-function"><code>INSERT-VERTEX</code> (function)</h3> <div class="codehilite"><pre><span/>(INSERT-VERTEX DIGRAPH VERTEX) </pre></div> <p>Insert <code>vertex</code> into the graph if it is not already a member.</p> <p>Returns <code>t</code> if the vertex was already in the graph, or <code>nil</code> if it was inserted.</p> <h3 id="leafp-function"><code>LEAFP</code> (function)</h3> <div class="codehilite"><pre><span/>(LEAFP DIGRAPH VERTEX) </pre></div> <p>Return whether <code>vertex</code> is a leaf vertex in <code>digraph</code>.</p> <h3 id="leafs-function"><code>LEAFS</code> (function)</h3> <div class="codehilite"><pre><span/>(LEAFS DIGRAPH) </pre></div> <p>Return all leaf vertices in <code>digraph</code>.</p> <p>This is currently O(vertices).</p> <p>A root is a vertex with no outgoing edges (i.e. out-degree 0).</p> <h3 id="make-digraph-function"><code>MAKE-DIGRAPH</code> (function)</h3> <div class="codehilite"><pre><span/>(MAKE-DIGRAPH &KEY INITIAL-VERTICES (TEST #'EQL) (HASH-FUNCTION NIL)) </pre></div> <p>Create and return a new digraph.</p> <p><code>initial-vertices</code> can be a sequence of vertices to add to the graph.</p> <p><code>test</code> should be one of the hash table equality predicates.</p> <p>If your Lisp implementation supports the <code>:hash-function</code> argument for creating hash tables with custom predicates, you can specify one with <code>hash-function</code>.</p> <h3 id="map-breadth-first-function"><code>MAP-BREADTH-FIRST</code> (function)</h3> <div class="codehilite"><pre><span/>(MAP-BREADTH-FIRST FUNCTION DIGRAPH START-VERTEX) </pre></div> <p>Apply <code>function</code> to the vertices of a breadth-first traversal of <code>digraph</code>.</p> <p>Returns a fresh list with the results.</p> <p>Vertices are processed in breadth-first order, beginning at <code>start-vertex</code>, and the resulting list has this order as well.</p> <p>Cycles in the graph will not be traversed into.</p> <h3 id="map-depth-first-function"><code>MAP-DEPTH-FIRST</code> (function)</h3> <div class="codehilite"><pre><span/>(MAP-DEPTH-FIRST FUNCTION DIGRAPH START-VERTEX) </pre></div> <p>Apply <code>function</code> to the vertices of a breadth-first traversal of <code>digraph</code>.</p> <p>Returns a fresh list with the results.</p> <p>Vertices are processed in depth-first order, beginning at <code>start-vertex</code>, and the resulting list has this order as well.</p> <p>Cycles in the graph will not be traversed into.</p> <h3 id="map-edges-function"><code>MAP-EDGES</code> (function)</h3> <div class="codehilite"><pre><span/>(MAP-EDGES FUNCTION DIGRAPH) </pre></div> <p>Return a fresh list with the results of calling <code>function</code> on each edge.</p> <p>For each edge, <code>function</code> will be called once with two arguments:</p> <div class="codehilite"><pre><span/>(function predecessor successor) </pre></div> <p>The order of the resulting list is unspecified.</p> <h3 id="map-vertices-function"><code>MAP-VERTICES</code> (function)</h3> <div class="codehilite"><pre><span/>(MAP-VERTICES FUNCTION DIGRAPH) </pre></div> <p>Return a fresh list with the results of calling <code>function</code> on each vertex.</p> <p>The order of the resulting list is unspecified.</p> <h3 id="mapc-breadth-first-function"><code>MAPC-BREADTH-FIRST</code> (function)</h3> <div class="codehilite"><pre><span/>(MAPC-BREADTH-FIRST FUNCTION DIGRAPH START-VERTEX) </pre></div> <p>Apply <code>function</code> to the vertices of a breadth-first traversal of <code>digraph</code>.</p> <p>Returns <code>nil</code>.</p> <p>Vertices are processed in breadth-first order, beginning at <code>start-vertex</code>.</p> <p>Cycles in the graph will not be traversed into.</p> <h3 id="mapc-depth-first-function"><code>MAPC-DEPTH-FIRST</code> (function)</h3> <div class="codehilite"><pre><span/>(MAPC-DEPTH-FIRST FUNCTION DIGRAPH START-VERTEX) </pre></div> <p>Apply <code>function</code> to the vertices of a depth-first traversal of <code>digraph</code>.</p> <p>Returns <code>nil</code>.</p> <p>Vertices are processed in depth-first order, beginning at <code>start-vertex</code>.</p> <p>Cycles in the graph will not be traversed into.</p> <h3 id="mapc-edges-function"><code>MAPC-EDGES</code> (function)</h3> <div class="codehilite"><pre><span/>(MAPC-EDGES FUNCTION DIGRAPH) </pre></div> <p>Call <code>function</code> on each edge in <code>digraph</code>.</p> <p>For each edge, <code>function</code> will be called once with two arguments:</p> <div class="codehilite"><pre><span/>(function predecessor successor) </pre></div> <p>The order in which the edges are processed is unspecified.</p> <p>Returns <code>nil</code>.</p> <h3 id="mapc-vertices-function"><code>MAPC-VERTICES</code> (function)</h3> <div class="codehilite"><pre><span/>(MAPC-VERTICES FUNCTION DIGRAPH) </pre></div> <p>Call <code>function</code> on each vertex in <code>digraph</code>.</p> <p>The order in which the vertices are processed is unspecified.</p> <p>Returns <code>nil</code>.</p> <h3 id="missing-predecessor-class"><code>MISSING-PREDECESSOR</code> (class)</h3> <p>An error signaled when trying to insert an edge whose predecessor is not in the graph.</p> <p><code>vertex-involved</code> can be used to retrieve the offending predecessor.</p> <h3 id="missing-successor-class"><code>MISSING-SUCCESSOR</code> (class)</h3> <p>An error signaled when trying to insert an edge whose successor is not in the graph.</p> <p><code>vertex-involved</code> can be used to retrieve the offending successor.</p> <h3 id="missing-vertex-class"><code>MISSING-VERTEX</code> (class)</h3> <p>Base condition for errors signaled when inserting an edge with a vertex missing.</p> <h3 id="neighbors-function"><code>NEIGHBORS</code> (function)</h3> <div class="codehilite"><pre><span/>(NEIGHBORS DIGRAPH VERTEX) </pre></div> <p>Return a fresh list of the neighbors of <code>vertex</code>.</p> <h3 id="predecessors-function"><code>PREDECESSORS</code> (function)</h3> <div class="codehilite"><pre><span/>(PREDECESSORS DIGRAPH VERTEX) </pre></div> <p>Return a fresh list of the predecessors of <code>vertex</code>.</p> <h3 id="reachablep-function"><code>REACHABLEP</code> (function)</h3> <div class="codehilite"><pre><span/>(REACHABLEP DIGRAPH START TARGET &KEY (STRATEGY :BREADTH-FIRST)) </pre></div> <p>Return <code>t</code> if it is possible to reach <code>target</code> from <code>start</code>, otherwise <code>nil</code>.</p> <p>All vertices are reachable from themselves.</p> <p>Otherwise a <code>target</code> is reachable from <code>start</code> if a directed path exists from the start to the target.</p> <p><code>strategy</code> will be used to determine how to traverse the graph when searching for a path, and can be one of <code>:breadth-first</code> or <code>:depth-first</code>.</p> <h3 id="remove-edge-function"><code>REMOVE-EDGE</code> (function)</h3> <div class="codehilite"><pre><span/>(REMOVE-EDGE DIGRAPH PREDECESSOR SUCCESSOR) </pre></div> <p>Remove an edge from <code>predecessor</code> to <code>successor</code> if present.</p> <p>Returns <code>t</code> if there was such an edge, or <code>nil</code> if not.</p> <h3 id="remove-vertex-function"><code>REMOVE-VERTEX</code> (function)</h3> <div class="codehilite"><pre><span/>(REMOVE-VERTEX DIGRAPH VERTEX) </pre></div> <p>Remove <code>vertex</code> from the graph if present.</p> <p>If there are any edges to/from <code>vertex</code> they will be automatically removed.</p> <p>Returns <code>t</code> if there was such a vertex, or <code>nil</code> if not.</p> <h3 id="rootp-function"><code>ROOTP</code> (function)</h3> <div class="codehilite"><pre><span/>(ROOTP DIGRAPH VERTEX) </pre></div> <p>Return whether <code>vertex</code> is a root vertex in <code>digraph</code>.</p> <h3 id="roots-function"><code>ROOTS</code> (function)</h3> <div class="codehilite"><pre><span/>(ROOTS DIGRAPH) </pre></div> <p>Return all root vertices in <code>digraph</code>.</p> <p>This is currently O(vertices).</p> <p>A root is a vertex with no incoming edges (i.e. in-degree 0).</p> <h3 id="successors-function"><code>SUCCESSORS</code> (function)</h3> <div class="codehilite"><pre><span/>(SUCCESSORS DIGRAPH VERTEX) </pre></div> <p>Return a fresh list of the successors of <code>vertex</code>.</p> <h3 id="topological-sort-function"><code>TOPOLOGICAL-SORT</code> (function)</h3> <div class="codehilite"><pre><span/>(TOPOLOGICAL-SORT DIGRAPH) </pre></div> <p>Return a fresh list of the vertices of <code>digraph</code> in topological order.</p> <p>Edges are treated as meaning "depends on", so an edge <code>A --> B</code> 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.</p> <p>The order in which the vertices are processed is unspecified.</p> <p>A <code>topological-sort-cycle</code> error will be signaled if the graph contains a cycle.</p> <h3 id="topological-sort-cycle-class"><code>TOPOLOGICAL-SORT-CYCLE</code> (class)</h3> <p>An error signaled when topologically sorting a graph that contains a cycle.</p> <p><code>vertex-involved</code> can be used to retrieve one of the vertices involved in a cycle. Which vertex in the cycle is chosen is arbitrary.</p> <h3 id="vertex-involved-generic-function"><code>VERTEX-INVOLVED</code> (generic function)</h3> <div class="codehilite"><pre><span/>(VERTEX-INVOLVED CONDITION) </pre></div> <p>Retrieve the vertex involved in the condition.</p> <h3 id="vertices-function"><code>VERTICES</code> (function)</h3> <div class="codehilite"><pre><span/>(VERTICES DIGRAPH) </pre></div> <p>Return a fresh list of the vertices of <code>digraph</code>.</p> </div> <footer><p><i>Made with Lisp and love by <a href="http://stevelosh.com/">Steve Losh</a> in Reykjavík, Iceland.</i></p></footer> </div> </body> </html>