hg.stevelosh.com > docs.stevelosh.com

<!DOCTYPE html>
<html>
    <head>
        <meta charset="utf-8"/>
        <title>Usage / 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="usage"><a href="">Usage</a></h1><p>cl-digraph is a simple library for working with <a href="https://en.wikipedia.org/wiki/Directed_graph">directed graphs</a> in Common
Lisp.</p>
<div class="toc">
<ul>
<li><a href="#package">Package</a></li>
<li><a href="#creating-digraphs">Creating Digraphs</a></li>
<li><a href="#working-with-vertices">Working with Vertices</a></li>
<li><a href="#equality">Equality</a></li>
<li><a href="#working-with-edges">Working with Edges</a></li>
<li><a href="#retrieving-digraph-information">Retrieving Digraph Information</a><ul>
<li><a href="#vertices-and-edges">Vertices and Edges</a></li>
<li><a href="#neighboring-vertices">Neighboring Vertices</a></li>
<li><a href="#membership">Membership</a></li>
<li><a href="#sizes-and-counts">Sizes and Counts</a></li>
</ul>
</li>
<li><a href="#mapping-traversal-and-sorting">Mapping, Traversal, and Sorting</a><ul>
<li><a href="#unordered-mapping">Unordered Mapping</a></li>
<li><a href="#ordered-traversal">Ordered Traversal</a></li>
<li><a href="#topological-sorting">Topological Sorting</a></li>
</ul>
</li>
<li><a href="#conditions">Conditions</a></li>
<li><a href="#drawing">Drawing</a></li>
</ul></div>
<h2 id="package">Package</h2>
<p>All core cl-digraph functions are in the <code>digraph</code> package.  You can <code>:use</code> that
if you really want to, but it's probably clearer to use namespaced <code>digraph:...</code>
symbols.</p>
<h2 id="creating-digraphs">Creating Digraphs</h2>
<p>Digraphs can be created with <code>make-digraph</code>:</p>
<div class="codehilite"><pre><span/><span class="p">(</span><span class="nv">digraph:make-digraph</span><span class="p">)</span>
<span class="c1">; =&gt; #&lt;DIGRAPH:DIGRAPH () {1002CFD343}&gt;</span>
</pre></div>


<h2 id="working-with-vertices">Working with Vertices</h2>
<p>Vertices can be added to a digraph with <code>insert-vertex</code>, and a list of all
vertices in the graph retrieved with <code>vertices</code>:</p>
<div class="codehilite"><pre><span/><span class="p">(</span><span class="nb">defparameter</span> <span class="vg">*d*</span> <span class="p">(</span><span class="nv">digraph:make-digraph</span><span class="p">))</span>

<span class="p">(</span><span class="nv">digraph:vertices</span> <span class="vg">*d*</span><span class="p">)</span>
<span class="c1">; =&gt; ()</span>

<span class="p">(</span><span class="nv">digraph:insert-vertex</span> <span class="vg">*d*</span> <span class="ss">'foo</span><span class="p">)</span>
<span class="p">(</span><span class="nv">digraph:vertices</span> <span class="vg">*d*</span><span class="p">)</span>
<span class="c1">; =&gt; (foo)</span>

<span class="p">(</span><span class="nv">digraph:insert-vertex</span> <span class="vg">*d*</span> <span class="ss">'bar</span><span class="p">)</span>
<span class="p">(</span><span class="nv">digraph:vertices</span> <span class="vg">*d*</span><span class="p">)</span>
<span class="c1">; =&gt; (bar foo)</span>
</pre></div>


<p>The order of vertices returned in the list is arbitrary.  We'll see how to
retrieve vertices in specific orders later.</p>
<p>Duplicate vertices are silently ignored:</p>
<div class="codehilite"><pre><span/><span class="p">(</span><span class="nb">defparameter</span> <span class="vg">*d*</span> <span class="p">(</span><span class="nv">digraph:make-digraph</span><span class="p">))</span>

<span class="p">(</span><span class="nv">digraph:insert-vertex</span> <span class="vg">*d*</span> <span class="ss">'foo</span><span class="p">)</span>
<span class="p">(</span><span class="nv">digraph:insert-vertex</span> <span class="vg">*d*</span> <span class="ss">'foo</span><span class="p">)</span>
<span class="p">(</span><span class="nv">digraph:insert-vertex</span> <span class="vg">*d*</span> <span class="ss">'foo</span><span class="p">)</span>
<span class="p">(</span><span class="nv">digraph:vertices</span> <span class="vg">*d*</span><span class="p">)</span>
<span class="c1">; =&gt; (foo)</span>
</pre></div>


<p>You can also specify some initial vertices directly in the <code>make-digraph</code> call
if you want:</p>
<div class="codehilite"><pre><span/><span class="p">(</span><span class="nb">defparameter</span> <span class="vg">*d*</span>
  <span class="p">(</span><span class="nv">digraph:make-digraph</span> <span class="ss">:initial-vertices</span> <span class="o">'</span><span class="p">(</span><span class="nv">a</span> <span class="nv">b</span> <span class="nv">c</span><span class="p">)))</span>

<span class="p">(</span><span class="nv">digraph:vertices</span> <span class="vg">*d*</span><span class="p">)</span>
<span class="c1">; =&gt; (a c b)</span>

<span class="p">(</span><span class="nv">digraph:insert-vertex</span> <span class="vg">*d*</span> <span class="ss">'foo</span><span class="p">)</span>
<span class="p">(</span><span class="nv">digraph:vertices</span> <span class="vg">*d*</span><span class="p">)</span>
<span class="c1">; =&gt; (a c foo b)</span>
</pre></div>


<p>You can remove vertices with <code>remove-vertex</code>.  Removing a vertex that's not in
the graph is silently ignored:</p>
<div class="codehilite"><pre><span/><span class="p">(</span><span class="nb">defparameter</span> <span class="vg">*d*</span>
  <span class="p">(</span><span class="nv">digraph:make-digraph</span> <span class="ss">:initial-vertices</span> <span class="o">'</span><span class="p">(</span><span class="nv">a</span> <span class="nv">b</span> <span class="nv">c</span><span class="p">)))</span>

<span class="p">(</span><span class="nv">digraph:vertices</span> <span class="vg">*d*</span><span class="p">)</span>
<span class="c1">; =&gt; (a c b)</span>

<span class="p">(</span><span class="nv">digraph:remove-vertex</span> <span class="vg">*d*</span> <span class="ss">'a</span><span class="p">)</span>
<span class="p">(</span><span class="nv">digraph:vertices</span> <span class="vg">*d*</span><span class="p">)</span>
<span class="c1">; =&gt; (c b)</span>

<span class="p">(</span><span class="nv">digraph:remove-vertex</span> <span class="vg">*d*</span> <span class="ss">'cats</span><span class="p">)</span>
<span class="p">(</span><span class="nv">digraph:vertices</span> <span class="vg">*d*</span><span class="p">)</span>
<span class="c1">; =&gt; (c b)</span>
</pre></div>


<h2 id="equality">Equality</h2>
<p>By default cl-digraph compares vertices for equality with <code>eql</code>.  You can
specify a different equality predicate with the <code>:test</code> argument to
<code>make-digraph</code>:</p>
<div class="codehilite"><pre><span/><span class="p">(</span><span class="nb">defparameter</span> <span class="vg">*d*</span>
  <span class="p">(</span><span class="nv">digraph:make-digraph</span> <span class="ss">:test</span> <span class="nf">#'</span><span class="nb">equal</span><span class="p">))</span>

<span class="p">(</span><span class="nv">digraph:insert-vertex</span> <span class="vg">*d*</span> <span class="p">(</span><span class="nb">list</span> <span class="mi">1</span> <span class="mi">2</span><span class="p">))</span>
<span class="p">(</span><span class="nv">digraph:insert-vertex</span> <span class="vg">*d*</span> <span class="p">(</span><span class="nb">list</span> <span class="mi">3</span> <span class="mi">4</span><span class="p">))</span>
<span class="p">(</span><span class="nv">digraph:vertices</span> <span class="vg">*d*</span><span class="p">)</span>
<span class="c1">; =&gt; ((1 2) (3 4))</span>

<span class="p">(</span><span class="nv">digraph:insert-vertex</span> <span class="vg">*d*</span> <span class="p">(</span><span class="nb">list</span> <span class="mi">1</span> <span class="mi">2</span><span class="p">))</span>
<span class="p">(</span><span class="nv">digraph:vertices</span> <span class="vg">*d*</span><span class="p">)</span>
<span class="c1">; =&gt; ((1 2) (3 4))</span>

<span class="p">(</span><span class="nv">digraph:remove-vertex</span> <span class="vg">*d*</span> <span class="p">(</span><span class="nb">list</span> <span class="mi">1</span> <span class="mi">2</span><span class="p">))</span>
<span class="p">(</span><span class="nv">digraph:vertices</span> <span class="vg">*d*</span><span class="p">)</span>
<span class="c1">; =&gt; ((3 4))</span>
</pre></div>


<p>cl-digraph stores data in hash tables internally, so <code>test</code> must be one of the
predicates supported as a hash table test (<code>eq</code>, <code>eql</code>, <code>equal</code>, or <code>equalp</code>).</p>
<p>If your Lisp implementation supports creating hash tables with custom hash
functions with the <code>:hash-function</code> argument to <code>make-hash-table</code>, you can use
them with cl-digraph as well:</p>
<div class="codehilite"><pre><span/><span class="p">(</span><span class="nb">defparameter</span> <span class="vg">*d*</span>
  <span class="p">(</span><span class="nv">digraph:make-digraph</span> <span class="ss">:test</span> <span class="nf">#'</span><span class="nv">some-predicate</span>
                        <span class="ss">:hash-function</span> <span class="nf">#'</span><span class="nv">custom-hash-function</span><span class="p">))</span>
</pre></div>


<p>This should work in SBCL, LispWorks, Allegro, CCL, and possibly others.</p>
<h2 id="working-with-edges">Working with Edges</h2>
<p>Once you've got some vertices in a digraph you can add edges between them.  The
vertex that an edge goes <em>out of</em> is called the <strong>predecessor</strong>, and the vertex
the edge goes <em>into</em> is called the <strong>successor</strong>:</p>
<div class="codehilite"><pre><span/>┌─────────────┐      ┌─────────────┐
│ predecessor │─────▶│  successor  │
└─────────────┘      └─────────────┘
</pre></div>


<p>Edges are added with <code>insert-edge</code>.  A list of edges in a digraph can be
retrieved with <code>edges</code>:</p>
<div class="codehilite"><pre><span/><span class="p">(</span><span class="nb">defparameter</span> <span class="vg">*d*</span>
  <span class="p">(</span><span class="nv">digraph:make-digraph</span> <span class="ss">:initial-vertices</span> <span class="o">'</span><span class="p">(</span><span class="nv">a</span> <span class="nv">b</span> <span class="nv">c</span><span class="p">)))</span>

<span class="p">(</span><span class="nv">digraph:edges</span> <span class="vg">*d*</span><span class="p">)</span>
<span class="c1">; =&gt; ()</span>

<span class="p">(</span><span class="nv">digraph:insert-edge</span> <span class="vg">*d*</span> <span class="ss">'a</span> <span class="ss">'b</span><span class="p">)</span> <span class="c1">; a -&gt; b</span>
<span class="p">(</span><span class="nv">digraph:edges</span> <span class="vg">*d*</span><span class="p">)</span>
<span class="c1">; =&gt; ((a . b))</span>

<span class="p">(</span><span class="nv">digraph:insert-edge</span> <span class="vg">*d*</span> <span class="ss">'b</span> <span class="ss">'c</span><span class="p">)</span> <span class="c1">; b -&gt; c</span>
<span class="p">(</span><span class="nv">digraph:edges</span> <span class="vg">*d*</span><span class="p">)</span>
<span class="c1">; =&gt; ((b . c) (a . b))</span>
</pre></div>


<p>Duplicate edges are silently ignored.  The predecessor and successor must both
exist in the graph already, or an error will be signaled:</p>
<div class="codehilite"><pre><span/><span class="p">(</span><span class="nb">defparameter</span> <span class="vg">*d*</span>
  <span class="p">(</span><span class="nv">digraph:make-digraph</span> <span class="ss">:initial-vertices</span> <span class="o">'</span><span class="p">(</span><span class="nv">a</span> <span class="nv">b</span> <span class="nv">c</span><span class="p">)))</span>

<span class="p">(</span><span class="nv">digraph:insert-edge</span> <span class="vg">*d*</span> <span class="ss">'a</span> <span class="ss">'b</span><span class="p">)</span> <span class="c1">; a -&gt; b</span>
<span class="p">(</span><span class="nv">digraph:insert-edge</span> <span class="vg">*d*</span> <span class="ss">'a</span> <span class="ss">'b</span><span class="p">)</span> <span class="c1">; ignored</span>
<span class="p">(</span><span class="nv">digraph:insert-edge</span> <span class="vg">*d*</span> <span class="ss">'a</span> <span class="ss">'b</span><span class="p">)</span> <span class="c1">; ignored</span>
<span class="p">(</span><span class="nv">digraph:edges</span> <span class="vg">*d*</span><span class="p">)</span>
<span class="c1">; =&gt; ((a . b))</span>

<span class="p">(</span><span class="nv">digraph:insert-edge</span> <span class="vg">*d*</span> <span class="ss">'cats</span> <span class="ss">'dogs</span><span class="p">)</span>
<span class="c1">; =&gt;</span>
<span class="c1">; Cannot add edge with predecessor CATS because it is not in the graph</span>
<span class="c1">;    [Condition of type DIGRAPH::MISSING-PREDECESSOR]</span>
<span class="c1">;</span>
<span class="c1">; Restarts:</span>
<span class="c1">;   R 0. CONTINUE - Retry assertion with new value for DIGRAPH::PREDECESSOR.</span>
<span class="c1">;   R 1. ABORT    - Exit debugger, returning to top level.</span>
</pre></div>


<p>See the <a href="#conditions">Conditions</a> section for more information about the error
hierarchy.</p>
<p>Edges can be removed with <code>remove-edge</code>.  Removing an edge that's not in the
graph is silently ignored:</p>
<div class="codehilite"><pre><span/><span class="p">(</span><span class="nb">defparameter</span> <span class="vg">*d*</span>
  <span class="p">(</span><span class="nv">digraph:make-digraph</span> <span class="ss">:initial-vertices</span> <span class="o">'</span><span class="p">(</span><span class="nv">a</span> <span class="nv">b</span> <span class="nv">c</span><span class="p">)))</span>

<span class="p">(</span><span class="nv">digraph:insert-edge</span> <span class="vg">*d*</span> <span class="ss">'a</span> <span class="ss">'b</span><span class="p">)</span> <span class="c1">; a -&gt; b</span>
<span class="p">(</span><span class="nv">digraph:edges</span> <span class="vg">*d*</span><span class="p">)</span>
<span class="c1">; =&gt; ((a . b))</span>

<span class="p">(</span><span class="nv">digraph:remove-edge</span> <span class="vg">*d*</span> <span class="ss">'a</span> <span class="ss">'b</span><span class="p">)</span> <span class="c1">; removes a -&gt; b</span>
<span class="p">(</span><span class="nv">digraph:remove-edge</span> <span class="vg">*d*</span> <span class="ss">'a</span> <span class="ss">'b</span><span class="p">)</span> <span class="c1">; ignored</span>
<span class="p">(</span><span class="nv">digraph:edges</span> <span class="vg">*d*</span><span class="p">)</span>
<span class="c1">; =&gt; ()</span>
</pre></div>


<h2 id="retrieving-digraph-information">Retrieving Digraph Information</h2>
<p>Once you've got a digraph you might want to ask it about itself.  Let's consider
a simple digraph as an example:</p>
<div class="codehilite"><pre><span/><span class="c1">;            ┌───┐      ┌───┐</span>
<span class="c1">;   ┌───────▶│ B │─────▶│ D │</span>
<span class="c1">;   │        └───┘      └───┘</span>
<span class="c1">; ┌───┐</span>
<span class="c1">; │ A │               ┌─────┐       ┌─────┐</span>
<span class="c1">; └───┘               │ FOO │──────▶│ BAR │──┐</span>
<span class="c1">;   │        ┌───┐    └─────┘       └─────┘  │</span>
<span class="c1">;   └───────▶│ C │                     ▲     │</span>
<span class="c1">;            └───┘                     │     │</span>
<span class="c1">;                                      └─────┘</span>
<span class="p">(</span><span class="nb">defparameter</span> <span class="vg">*d*</span>
  <span class="p">(</span><span class="nv">digraph:make-digraph</span> <span class="ss">:initial-vertices</span> <span class="o">'</span><span class="p">(</span><span class="nv">a</span> <span class="nv">b</span> <span class="nv">c</span> <span class="nv">d</span> <span class="nv">foo</span> <span class="nv">bar</span><span class="p">)))</span>

<span class="p">(</span><span class="nb">loop</span> <span class="ss">:for</span> <span class="p">(</span><span class="nv">from</span> <span class="nv">to</span><span class="p">)</span> <span class="ss">:in</span> <span class="o">'</span><span class="p">((</span><span class="nv">a</span> <span class="nv">b</span><span class="p">)</span> <span class="p">(</span><span class="nv">a</span> <span class="nv">c</span><span class="p">)</span> <span class="p">(</span><span class="nv">b</span> <span class="nv">d</span><span class="p">)</span> <span class="p">(</span><span class="nv">foo</span> <span class="nv">bar</span><span class="p">)</span> <span class="p">(</span><span class="nv">bar</span> <span class="nv">bar</span><span class="p">))</span>
      <span class="ss">:do</span> <span class="p">(</span><span class="nv">digraph:insert-edge</span> <span class="vg">*d*</span> <span class="nv">from</span> <span class="nv">to</span><span class="p">))</span>
</pre></div>


<p>Notice that digraphs don't have to be connected, and vertices can have edges to
themselves.</p>
<h3 id="vertices-and-edges">Vertices and Edges</h3>
<p>We've already seen <code>vertices</code> and <code>edges</code>:</p>
<div class="codehilite"><pre><span/><span class="p">(</span><span class="nv">digraph:vertices</span> <span class="vg">*d*</span><span class="p">)</span>
<span class="c1">; =&gt; (BAR FOO D C B A)</span>

<span class="p">(</span><span class="nv">digraph:edges</span> <span class="vg">*d*</span><span class="p">)</span>
<span class="c1">; =&gt; ((BAR . BAR) (FOO . BAR) (B . D) (A . B) (A . C))</span>
</pre></div>


<p>These functions return their results in an arbitrary order — don't rely on it
being anything in particular.</p>
<h3 id="neighboring-vertices">Neighboring Vertices</h3>
<p>The <code>predecessors</code> and <code>successors</code> functions return a list of vertices with
edges to/from a particular vertex:</p>
<div class="codehilite"><pre><span/><span class="p">(</span><span class="nv">digraph:predecessors</span> <span class="vg">*d*</span> <span class="ss">'a</span><span class="p">)</span> <span class="c1">; =&gt; ()</span>
<span class="p">(</span><span class="nv">digraph:successors</span> <span class="vg">*d*</span> <span class="ss">'a</span><span class="p">)</span>   <span class="c1">; =&gt; (b c)</span>

<span class="p">(</span><span class="nv">digraph:predecessors</span> <span class="vg">*d*</span> <span class="ss">'bar</span><span class="p">)</span> <span class="c1">; =&gt; (foo bar)</span>
<span class="p">(</span><span class="nv">digraph:successors</span> <span class="vg">*d*</span>   <span class="ss">'bar</span><span class="p">)</span> <span class="c1">; =&gt; (bar)</span>
</pre></div>


<p><code>neighbors</code> returns all vertices that are a predecessor <em>or</em> successor of the
given vertex:</p>
<div class="codehilite"><pre><span/><span class="p">(</span><span class="nv">digraph:neighbors</span> <span class="vg">*d*</span> <span class="ss">'b</span><span class="p">)</span> <span class="c1">; =&gt; (a d)</span>
</pre></div>


<h3 id="membership">Membership</h3>
<p>To check whether a digraph contains a particular edge or vertex use
<code>contains-vertex-p</code> and <code>contains-edge-p</code>:</p>
<div class="codehilite"><pre><span/><span class="p">(</span><span class="nv">digraph:contains-vertex-p</span> <span class="vg">*d*</span> <span class="ss">'a</span><span class="p">)</span>      <span class="c1">; =&gt; t</span>
<span class="p">(</span><span class="nv">digraph:contains-vertex-p</span> <span class="vg">*d*</span> <span class="ss">'horses</span><span class="p">)</span> <span class="c1">; =&gt; nil</span>

<span class="p">(</span><span class="nv">digraph:contains-edge-p</span> <span class="vg">*d*</span> <span class="ss">'a</span> <span class="ss">'b</span><span class="p">)</span>     <span class="c1">; =&gt; t</span>
<span class="p">(</span><span class="nv">digraph:contains-edge-p</span> <span class="vg">*d*</span> <span class="ss">'a</span> <span class="ss">'foo</span><span class="p">)</span>   <span class="c1">; =&gt; nil</span>
</pre></div>


<h3 id="sizes-and-counts">Sizes and Counts</h3>
<p>If you just want the <em>number</em> of vertices or edges in a digraph and don't need
a list of them, use <code>count-vertices</code> and <code>count-edges</code>:</p>
<div class="codehilite"><pre><span/><span class="p">(</span><span class="nv">digraph:count-vertices</span> <span class="vg">*d*</span><span class="p">)</span> <span class="c1">; =&gt; 6</span>
<span class="p">(</span><span class="nv">digraph:count-edges</span> <span class="vg">*d*</span><span class="p">)</span>    <span class="c1">; =&gt; 5</span>
</pre></div>


<p>Similarly, if you want to know the number of edges into/out of/involving
a vertex use <code>degree</code>, <code>degree-in</code>, and <code>degree-out</code>:</p>
<div class="codehilite"><pre><span/><span class="p">(</span><span class="nv">digraph:predecessors</span> <span class="vg">*d*</span> <span class="ss">'a</span><span class="p">)</span> <span class="c1">; =&gt; ()</span>
<span class="p">(</span><span class="nv">digraph:degree-in</span>    <span class="vg">*d*</span> <span class="ss">'a</span><span class="p">)</span> <span class="c1">; = 0</span>

<span class="p">(</span><span class="nv">digraph:successors</span> <span class="vg">*d*</span> <span class="ss">'bar</span><span class="p">)</span> <span class="c1">; =&gt; (bar)</span>
<span class="p">(</span><span class="nv">digraph:degree-out</span> <span class="vg">*d*</span> <span class="ss">'bar</span><span class="p">)</span> <span class="c1">; =&gt; 1</span>

<span class="p">(</span><span class="nv">digraph:neighbors</span>  <span class="vg">*d*</span> <span class="ss">'b</span><span class="p">)</span> <span class="c1">; =&gt; (a d)</span>
<span class="p">(</span><span class="nv">digraph:degree-out</span> <span class="vg">*d*</span> <span class="ss">'b</span><span class="p">)</span> <span class="c1">; =&gt; 2</span>
</pre></div>


<h2 id="mapping-traversal-and-sorting">Mapping, Traversal, and Sorting</h2>
<p>Sometimes you may want to perform an action on each vertex or edge in a directed
graph, possibly in a specific order.</p>
<h3 id="unordered-mapping">Unordered Mapping</h3>
<p>If you don't care about the order the items are processed/returned in, use one
of the unordered mapping functions:</p>
<ul>
<li><code>(digraph:mapc-vertices function digraph)</code></li>
<li><code>(digraph:mapc-edges function digraph)</code></li>
<li><code>(digraph:map-vertices function digraph)</code></li>
<li><code>(digraph:map-edges function digraph)</code></li>
</ul>
<p>The <code>map-</code> variants return a fresh list of the results of calling <code>function</code> on
the argument(s).</p>
<p>The <code>mapc-</code> variants return <code>nil</code>, so you'd want to use them for the side
effects of <code>function</code>.</p>
<p>The <code>-vertices</code> variants call <code>function</code> with a single argument: the vertex.</p>
<p>The <code>-edges</code> variants call <code>function</code> with two arguments: the predecessor and
successor.</p>
<h3 id="ordered-traversal">Ordered Traversal</h3>
<p>Sometimes you may want to traverse the vertices of a digraph in depth-first or
breadth-first order.  You can use the ordered mapping functions for this:</p>
<ul>
<li><code>(digraph:mapc-depth-first function digraph start-vertex)</code></li>
<li><code>(digraph:mapc-breadth-first function digraph start-vertex)</code></li>
<li><code>(digraph:map-depth-first function digraph start-vertex)</code></li>
<li><code>(digraph:map-breadth-first function digraph start-vertex)</code></li>
</ul>
<p>If a traversal contains a cycle the traversal will stop that line of traversing
instead of looping infinitely.</p>
<h3 id="topological-sorting">Topological Sorting</h3>
<p>One common use of (acyclic) digraphs is to represent graphs of dependencies,
e.g. library <code>foo</code> depends on library <code>bar</code>, and <code>bar</code> depends on <code>baz</code>.</p>
<p>Often the end goal of constructing such a graph is to produce a <a href="https://en.wikipedia.org/wiki/Topological_sorting">topologically
sorted</a> list of the vertices — a list where each vertex comes after the ones
it depends on.  cl-digraph can produce a list in this order with the
<code>topological-sort</code> function:</p>
<div class="codehilite"><pre><span/><span class="p">(</span><span class="nb">defparameter</span> <span class="vg">*d*</span>
  <span class="p">(</span><span class="nv">digraph:make-digraph</span> <span class="ss">:initial-vertices</span> <span class="o">'</span><span class="p">(</span><span class="nv">a</span> <span class="nv">b</span> <span class="nv">c</span> <span class="nv">d</span><span class="p">)))</span>

<span class="p">(</span><span class="nv">digraph:insert-edge</span> <span class="vg">*d*</span> <span class="ss">'a</span> <span class="ss">'b</span><span class="p">)</span> <span class="c1">; a depends on b</span>
<span class="p">(</span><span class="nv">digraph:insert-edge</span> <span class="vg">*d*</span> <span class="ss">'a</span> <span class="ss">'c</span><span class="p">)</span> <span class="c1">; a depends on c</span>
<span class="p">(</span><span class="nv">digraph:insert-edge</span> <span class="vg">*d*</span> <span class="ss">'d</span> <span class="ss">'a</span><span class="p">)</span> <span class="c1">; d depends on a</span>

<span class="p">(</span><span class="nv">digraph:topological-sort</span> <span class="vg">*d*</span><span class="p">)</span>
<span class="c1">; =&gt; one of</span>
<span class="c1">; (C B A D)</span>
<span class="c1">; (B C A D)</span>
</pre></div>


<p>A <code>digraph:topological-sort-cycle</code> will be signaled if the digraph
contains a cycle:</p>
<div class="codehilite"><pre><span/><span class="p">(</span><span class="nb">defparameter</span> <span class="vg">*d*</span>
  <span class="p">(</span><span class="nv">digraph:make-digraph</span> <span class="ss">:initial-vertices</span> <span class="o">'</span><span class="p">(</span><span class="nv">a</span> <span class="nv">b</span> <span class="nv">c</span> <span class="nv">d</span><span class="p">)))</span>

<span class="p">(</span><span class="nv">digraph:insert-edge</span> <span class="vg">*d*</span> <span class="ss">'a</span> <span class="ss">'b</span><span class="p">)</span> <span class="c1">; a depends on b</span>
<span class="p">(</span><span class="nv">digraph:insert-edge</span> <span class="vg">*d*</span> <span class="ss">'b</span> <span class="ss">'c</span><span class="p">)</span> <span class="c1">; b depends on c</span>
<span class="p">(</span><span class="nv">digraph:insert-edge</span> <span class="vg">*d*</span> <span class="ss">'c</span> <span class="ss">'a</span><span class="p">)</span> <span class="c1">; c depends on a</span>

<span class="p">(</span><span class="nv">digraph:topological-sort</span> <span class="vg">*d*</span><span class="p">)</span>
<span class="c1">; =&gt;</span>
<span class="c1">; Cycle detected during topological sort involving vertex A</span>
<span class="c1">;     [Condition of type DIGRAPH:TOPOLOGICAL-SORT-CYCLE]</span>
<span class="c1">;</span>
<span class="c1">; Restarts:</span>
<span class="c1">;   R 0. ABORT - Exit debugger, returning to top level.</span>
</pre></div>


<p>See the <a href="#conditions">Conditions</a> section for more information about the error
hierarchy.</p>
<h2 id="conditions">Conditions</h2>
<p>The following condition types are defined by cl-digraph:</p>
<p><a href="../static/conditions.svg"><img alt="condition type hierarchy" src="../static/conditions.svg"/></a></p>
<p>Dotted outlines denote abstract types that are never actually instantiated, but
can be useful for handling whole classes of errors.</p>
<ul>
<li><code>digraph-error</code>: abstract type for digraph-related errors.</li>
<li><code>missing-vertex</code>: abstract type for errors signaled when trying to insert an edge involving a vertex that is not in the graph.</li>
<li><code>missing-predecessor</code>: error signaled when trying to insert an edge whose predecessor is not in the graph.</li>
<li><code>missing-successor</code>: error signaled when trying to insert an edge whose successor is not in the graph.</li>
<li><code>topological-sort-cycle</code>: error signaled when trying to topologically sort a graph involving a cycle.</li>
</ul>
<p>For <code>missing-vertex</code> errors of both kinds you can use the <code>vertex-involved</code>
reader to retrieve the offending vertex from the condition object.</p>
<p>For <code>topological-sort-cycle</code> errors you can use the <code>vertex-involved</code> reader to
retrieve one of the vertices involved in a cycle from the condition object.
<em>Which</em> vertex of the cycle is returned is arbitrary:</p>
<div class="codehilite"><pre><span/><span class="p">(</span><span class="nb">defparameter</span> <span class="vg">*d*</span>
  <span class="p">(</span><span class="nv">digraph:make-digraph</span> <span class="ss">:initial-vertices</span> <span class="o">'</span><span class="p">(</span><span class="nv">a</span> <span class="nv">b</span> <span class="nv">c</span> <span class="nv">d</span><span class="p">)))</span>

<span class="p">(</span><span class="nv">digraph:insert-edge</span> <span class="vg">*d*</span> <span class="ss">'a</span> <span class="ss">'b</span><span class="p">)</span> <span class="c1">; a depends on b</span>
<span class="p">(</span><span class="nv">digraph:insert-edge</span> <span class="vg">*d*</span> <span class="ss">'b</span> <span class="ss">'c</span><span class="p">)</span> <span class="c1">; b depends on c</span>
<span class="p">(</span><span class="nv">digraph:insert-edge</span> <span class="vg">*d*</span> <span class="ss">'c</span> <span class="ss">'a</span><span class="p">)</span> <span class="c1">; c depends on a</span>

<span class="p">(</span><span class="nb">handler-case</span> <span class="p">(</span><span class="nv">digraph:topological-sort</span> <span class="vg">*d*</span><span class="p">)</span>
  <span class="p">(</span><span class="nv">digraph:topological-sort-cycle</span> <span class="p">(</span><span class="nv">c</span><span class="p">)</span>
    <span class="p">(</span><span class="nb">list</span> <span class="ss">:cyclic</span> <span class="p">(</span><span class="nv">digraph:vertex-involved</span> <span class="nv">c</span><span class="p">))))</span>
<span class="c1">; =&gt;</span>
<span class="c1">; (:CYCLIC A)</span>
</pre></div>


<h2 id="drawing">Drawing</h2>
<p>If you have <a href="http://www.graphviz.org/">Graphviz</a> installed, you can draw digraph objects to images with
the <a href="https://github.com/michaelw/cl-dot">cl-dot</a> library by loading the optional <code>cl-digraph.dot</code> system:</p>
<div class="codehilite"><pre><span/><span class="p">(</span><span class="nv">ql:quickload</span> <span class="ss">'cl-digraph.dot</span><span class="p">)</span>

<span class="p">(</span><span class="nb">defparameter</span> <span class="vg">*d*</span>
  <span class="p">(</span><span class="nv">digraph:make-digraph</span> <span class="ss">:initial-vertices</span> <span class="o">'</span><span class="p">(</span><span class="nv">a</span> <span class="nv">b</span> <span class="nv">c</span> <span class="nv">d</span> <span class="nv">foo</span> <span class="nv">bar</span><span class="p">)))</span>

<span class="p">(</span><span class="nb">loop</span> <span class="ss">:for</span> <span class="p">(</span><span class="nv">from</span> <span class="nv">to</span><span class="p">)</span> <span class="ss">:in</span> <span class="o">'</span><span class="p">((</span><span class="nv">a</span> <span class="nv">b</span><span class="p">)</span> <span class="p">(</span><span class="nv">a</span> <span class="nv">c</span><span class="p">)</span> <span class="p">(</span><span class="nv">b</span> <span class="nv">d</span><span class="p">)</span> <span class="p">(</span><span class="nv">foo</span> <span class="nv">bar</span><span class="p">)</span> <span class="p">(</span><span class="nv">bar</span> <span class="nv">bar</span><span class="p">))</span>
      <span class="ss">:do</span> <span class="p">(</span><span class="nv">digraph:insert-edge</span> <span class="vg">*d*</span> <span class="nv">from</span> <span class="nv">to</span><span class="p">))</span>

<span class="p">(</span><span class="nv">digraph.dot:draw</span> <span class="vg">*d*</span> <span class="ss">:filename</span> <span class="s">"digraph.png"</span> <span class="ss">:format</span> <span class="ss">:png</span><span class="p">)</span>
</pre></div>


<p><img alt="Digraph PNG" src="http://i.imgur.com/TtyGQfM.png"/></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	Mon, 05 Apr 2021 22:00:28 -0400
parents	55507a7c499d
children	864b4d836c7b