hg.stevelosh.com > docs.stevelosh.com

cl-digraph/usage/index.html @ 15305ac3db17 

adopt: Update site.
author Steve Losh <steve@stevelosh.com>
date Thu, 22 Nov 2018 00:39:35 -0500
parents e034aa553148
children e805f586a549 
<!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="#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">; =&amp;gt;</span>
<span class="err">#</span><span class="nv">&amp;lt</span><span class="c1">;DIGRAPH:DIGRAPH () {1002CFD343}&amp;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">; =&amp;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">; =&amp;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">; =&amp;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">; =&amp;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">; =&amp;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">; =&amp;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">; =&amp;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">; =&amp;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">; =&amp;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">; =&amp;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">; =&amp;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">; =&amp;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">; =&amp;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 -&amp;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">; =&amp;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 -&amp;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">; =&amp;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 -&amp;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">; =&amp;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">; =&amp;gt; Error!</span>
</pre></div>


<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 -&amp;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">; =&amp;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 -&amp;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">; =&amp;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">; =&amp;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">; =&amp;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">; =&amp;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">; =&amp;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">; =&amp;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">; =&amp;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">; =&amp;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">; =&amp;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">; =&amp;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">; =&amp;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">; =&amp;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">; =&amp;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">; =&amp;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">; =&amp;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">; =&amp;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">; =&amp;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">; =&amp;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">; =&amp;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">; =&amp;gt; one of</span>
<span class="p">(</span><span class="nv">C</span> <span class="nv">B</span> <span class="nv">A</span> <span class="nv">D</span><span class="p">)</span>
<span class="p">(</span><span class="nv">B</span> <span class="nv">C</span> <span class="nv">A</span> <span class="nv">D</span><span class="p">)</span>
</pre></div>


<p>An error will be signaled if the digraph contains a cycle.</p>
<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>
<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>