author |
Steve Losh <steve@stevelosh.com> |
date |
Tue, 21 May 2019 22:07:39 -0400 |
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">; =&gt;</span>
<span class="err">#</span><span class="nv">&lt</span><span class="c1">;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; 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 -&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="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>