cl-digraph/reference/index.html @ 3d730f8497b4
cl-ggp: Update site.
| author | Steve Losh <steve@stevelosh.com> |
|---|---|
| date | Fri, 10 Feb 2017 16:28:41 +0000 |
| parents | 9133e251a03d |
| children | e5e174afc292 |
<!DOCTYPE html> <html> <head> <meta charset="utf-8"/> <title> API Reference / cl-digraph</title> <link rel="stylesheet" href="../_dmedia/pygments-clean.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="#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="#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="#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="#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="#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="#vertices-function">VERTICES (function)</a></li> </ul> </li> </ul></div> <h2 id="package-digraph">Package <code>DIGRAPH</code></h2> <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="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>The <code>predecessor</code> and <code>successor</code> vertices must exist in the graph already.</p> <p>Returns <code>t</code> if the edge was already in the graph, or <code>nil</code> if it was inserted.</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="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="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="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>An error will be signaled if the graph contains a cycle.</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> <script> (function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){ (i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o), m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m) })(window,document,'script','//www.google-analytics.com/analytics.js','ga'); ga('create', 'UA-15328874-3', 'auto'); ga('send', 'pageview'); </script></footer> </div> </body> </html>