<p>This is the manual for version 1.13.1 of the <strong class="pkg">Digraphs</strong> package. This package was developed at the University of St Andrews by:</p>
<ul>
<li><p>Jan De Beule,</p>
</li>
<li><p>Julius Jonušas,</p>
</li>
<li><p>James D. Mitchell,</p>
</li>
<li><p>Maria Tsalakou,</p>
</li>
<li><p>Wilf A. Wilson, and</p>
</li>
<li><p>Michael C. Young.</p>
</li>
</ul>
<p>Additional contributions were made by many people, for which the authors are very grateful. A full list can be found on the title page. The <strong class="pkg">Digraphs</strong> package contains a variety of methods for efficiently creating and storing mutable and immutable digraphs and computing information about them. Full explanations of all the functions contained in the package are provided below.</p>
<p>If the <span class="URL"><a href="https://gap-packages.github.io/grape">GRAPE</a></span> package is available, it will be loaded automatically. Digraphs created with the <strong class="pkg">Digraphs</strong> package can be converted to <span class="URL"><a href="https://gap-packages.github.io/grape">GRAPE</a></span> graphs with <code class="func">Graph</code> (<a href="chap3_mj.html#X7B335342839E5146"><span class="RefLink">3.2-3</span></a>), and conversely <span class="URL"><a href="https://gap-packages.github.io/grape">GRAPE</a></span> graphs can be converted to <strong class="pkg">Digraphs</strong> objects with <code class="func">Digraph</code> (<a href="chap3_mj.html#X834843057CE86655"><span class="RefLink">3.1-7</span></a>). <span class="URL"><a href="https://gap-packages.github.io/grape">GRAPE</a></span> is not required for <strong class="pkg">Digraphs</strong> to run.</p>
<p>The <span class="URL"><a href="http://www.tcs.tkk.fi/Software/bliss/">bliss</a></span> tool <a href="chapBib_mj.html#biBJK07">[JK07]</a> is included in this package. It is an open-source tool for computing automorphism groups and canonical forms of graphs, written by Tommi Junttila and Petteri Kaski. Several of the methods in the <strong class="pkg">Digraphs</strong> package rely on <span class="URL"><a href="http://www.tcs.tkk.fi/Software/bliss/">bliss</a></span> . If the <span class="URL"><a href="https://github.com/gap-packages/NautyTracesInterface">NautyTracesInterface</a></span> package for GAP is available then it is also possible to use <span class="URL"><a href="https://pallini.di.uniroma1.it">nauty</a></span> <a href="chapBib_mj.html#biBMP14">[MP14]</a> for computing automorphism groups and canonical forms in <strong class="pkg">Digraphs</strong>. See Section <a href="chap7_mj.html#X7E48B9F87A0F22D4"><span class="RefLink">7.2</span></a> for more details.</p>
<p>The <span class="URL"><a href="https://github.com/graph-algorithms/edge-addition-planarity-suite">edge-addition-planarity-suite</a></span> is also included in <strong class="pkg">Digraphs</strong>; see <a href="chapBib_mj.html#biBBM04">[BM04]</a>, <a href="chapBib_mj.html#biBB06">[Boy06]</a>, <a href="chapBib_mj.html#biBBM06">[BM06]</a>, and <a href="chapBib_mj.html#biBB12">[Boy12]</a> . The <span class="URL"><a href="https://github.com/graph-algorithms/edge-addition-planarity-suite">edge-addition-planarity-suite</a></span> is an open-source implementation of the edge addition planar graph embedding algorithm and related algorithms by John M. Boyer. See Section <a href="chap6_mj.html#X7E2305528492DDC0"><span class="RefLink">6.7</span></a> for more details.</p>
<p>From version 1.0.0 of this package, digraphs can be either mutable or immutable. Mutable digraphs can be changed in-place by many of the methods in the package, which avoids unnecessary copying. Immutable digraphs cannot be changed in-place, but their advantage is that the value of an attribute of an immutable digraph is only ever computed once. Mutable digraphs can be converted into immutable digraphs in-place using <code class="func">MakeImmutable</code> (<a href="/home/runner/gap/doc/ref/chap12_mj.html#X80CE136D804097C7"><span class="RefLink">Reference: MakeImmutable</span></a>). One of the motivations for introducing mutable digraphs in version 1.0.0 was that in practice the authors often wanted to create a digraph and immediately modify it (removing certain edges, loops, and so on). Before version 1.0.0, this involved copying the digraph several times, with each copy being discarded almost immediately. From version 1.0.0, this unnecessary copying can be eliminated by first creating a mutable digraph, then changing it in-place, and finally converting the mutable digraph to an immutable one in-place (if desirable).</p>
<p>For the purposes of this package and its documentation, the following definitions apply:</p>
<p>A <em>digraph</em> <span class="SimpleMath">\(E=(E^0,E^1,r,s)\)</span>, also known as a <em>directed graph</em>, consists of a set of vertices <span class="SimpleMath">\(E^0\)</span> and a set of edges <span class="SimpleMath">\(E^1\)</span> together with functions <span class="SimpleMath">\(s, r: E^1 \to E^0\)</span>, called the <em>source</em> and <em>range</em>, respectively. The source and range of an edge is respectively the values of <span class="SimpleMath">\(s, r\)</span> at that edge. An edge is called a <em>loop</em> if its source and range are the same. A digraph is called a <em>multidigraph</em> if there exist two or more edges with the same source and the same range.</p>
<p>A <em>directed walk</em> on a digraph is a sequence of alternating vertices and edges <span class="SimpleMath">\((v_1, e_1, v_2, e_2, ..., e_{n-1}, v_n)\)</span> such that each edge <span class="SimpleMath">\(e_i\)</span> has source <span class="SimpleMath">\(v_i\)</span> and range <span class="SimpleMath">\(v_{i+1}\)</span>. A <em>directed path</em> is a directed walk where no vertex (and hence no edge) is repeated. A <em>directed circuit</em> is a directed walk where <span class="SimpleMath">\(v_1 = v_n\)</span>, and a <em>directed cycle</em> is a directed circuit where where no vertex is repeated, except for <span class="SimpleMath">\(v_1 = v_n\)</span>.</p>
<p>The <em>length</em> of a directed walk <span class="SimpleMath">\((v_1, e_1, v_2, e_2, ..., e_{n-1}, v_n)\)</span> is equal to <span class="SimpleMath">\(n-1\)</span>, the number of edges it contains. A directed walk (or path) <span class="SimpleMath">\((v_1, e_1, v_2, e_2, ..., e_{n-1}, v_n)\)</span> is sometimes called a directed walk (or path) <em>from vertex <span class="SimpleMath">\(v_1\)</span> to vertex <span class="SimpleMath">\(v_n\)</span></em>. A directed walk of zero length, i.e. a sequence <span class="SimpleMath">\((v)\)</span> for some vertex <span class="SimpleMath">\(v\)</span>, is called <em>trivial</em>. A trivial directed walk is considered to be both a circuit and a cycle, as is the empty directed walk <span class="SimpleMath">\(()\)</span>. A <em>simple circuit</em> is another name for a non-trivial and non-empty directed cycle.</p>
Die Informationen auf dieser Webseite wurden
nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit,
noch Qualität der bereit gestellten Informationen zugesichert.
Bemerkung:
Die farbliche Syntaxdarstellung ist noch experimentell.
