hg.stevelosh.com > docs.stevelosh.com

<!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="#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="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 &amp;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 &amp;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 --&gt; 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>
author	Steve Losh <steve@stevelosh.com>
date	Sun, 14 Mar 2021 21:32:47 -0400
parents	f204de42ccef
children	15d3b832fdc5