Ziele Untersuchung
mit Columbo Integrität von
Datenbanken Interaktion und
Portierbarkeit Ergonomie der
Schnittstellen

Angebot Produkte Projekt Beratung

Mittel Analytik Modellierung Sprachen Algebra Logik Hardware Denken Kreativität

Zusammenhänge Gesellschaft Wirtschaft Branche Firma


products/Sources/formale Sprachen/GAP/pkg/digraphs/doc/ (Algebra von RWTH Aachen Version 4.15.1^©) Datei vom 27.8.2025 mit Größe 251 kB

SSL chap5_mj.html

Interaktion und
PortierbarkeitHTML

products/Sources/formale Sprachen/GAP/pkg/digraphs/doc/chap5_mj.html

<?xml version="1.0" encoding="UTF-8"?>

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
 "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">

<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en">
<head>
<script type="text/javascript"
 src="https://cdn.jsdelivr.net/npm/mathjax@2/MathJax.js?config=TeX-AMS-MML_HTMLorMML">
</script>
<title>GAP (Digraphs) - Chapter 5: Attributes and operations</title>
<meta http-equiv="content-type" content="text/html; charset=UTF-8" />
<meta name="generator" content="GAPDoc2HTML" />
<link rel="stylesheet" type="text/css" href="manual.css" />
<script src="manual.js" type="text/javascript"></script>
<script type="text/javascript">overwriteStyle();</script>
</head>
<body class="chap5" onload="jscontent()">

<div class="chlinktop">Goto Chapter: <a href="chap0_mj.html">Top</a> <a href="chap1_mj.html">1</a> <a href="chap2_mj.html">2</a> <a href="chap3_mj.html">3</a> <a href="chap4_mj.html">4</a> <a href="chap5_mj.html">5</a> <a href="chap6_mj.html">6</a> <a href="chap7_mj.html">7</a> <a href="chap8_mj.html">8</a> <a href="chap9_mj.html">9</a> <a href="chapA_mj.html">A</a> <a href="chapB_mj.html">B</a> <a href="chapBib_mj.html">Bib</a> <a href="chapInd_mj.html">Ind</a> </div>

<div class="chlinkprevnexttop"> <a href="chap0_mj.html">[Top of Book]</a> <a href="chap0_mj.html#contents">[Contents]</a> <a href="chap4_mj.html">[Previous Chapter]</a> <a href="chap6_mj.html">[Next Chapter]</a> </div>

<a href="chap5.html">[MathJax off]</a>
<a id="X8739F6CD78C90B14" name="X8739F6CD78C90B14"></a>
<div class="ChapSects"><a href="chap5_mj.html#X8739F6CD78C90B14">5 Attributes and operations</a>
<div class="ContSect"> <a href="chap5_mj.html#X7E814B6478F7D015">5.1 Vertices and edges</a>

<div class="ContSSBlock">
 <a href="chap5_mj.html#X7C45F7D878D896AC">5.1-1 DigraphVertices</a>
 <a href="chap5_mj.html#X7C6F19B57CB2E882">5.1-2 DigraphNrVertices</a>
 <a href="chap5_mj.html#X7D1C6A4D7ECEC317">5.1-3 DigraphEdges</a>
 <a href="chap5_mj.html#X85E1CFDD7E164AD0">5.1-4 DigraphNrEdges</a>
 <a href="chap5_mj.html#X7BD5D255809C859E">5.1-5 DigraphNrAdjacencies</a>
 <a href="chap5_mj.html#X7E53E728795BB862">5.1-6 DigraphNrAdjacenciesWithoutLoops</a>
 <a href="chap5_mj.html#X7BDABAF07917462B">5.1-7 DigraphNrLoops</a>
 <a href="chap5_mj.html#X85D5E08280914EE4">5.1-8 DigraphSinks</a>
 <a href="chap5_mj.html#X7F5C6268839BE98C">5.1-9 DigraphSources</a>
 <a href="chap5_mj.html#X785C30378064CF47">5.1-10 DigraphTopologicalSort</a>
 <a href="chap5_mj.html#X7CA91E4B7904F793">5.1-11 DigraphVertexLabel</a>
 <a href="chap5_mj.html#X7E51F2FE87140B32">5.1-12 DigraphVertexLabels</a>
 <a href="chap5_mj.html#X79FAEACC7F438C2F">5.1-13 DigraphEdgeLabel</a>
 <a href="chap5_mj.html#X7C24851087D4A8FB">5.1-14 DigraphEdgeLabels</a>
 <a href="chap5_mj.html#X7EFAF01B7A155157">5.1-15 DigraphInEdges</a>
 <a href="chap5_mj.html#X7BECFE6687ECD028">5.1-16 DigraphOutEdges</a>
 <a href="chap5_mj.html#X7BB8ED88835F07B4">5.1-17 IsDigraphEdge</a>
 <a href="chap5_mj.html#X848FED0B7B4ACD1F">5.1-18 IsMatching</a>
 <a href="chap5_mj.html#X7B7A67277B1C9A02">5.1-19 DigraphMaximalMatching</a>
 <a href="chap5_mj.html#X78E9847A858788D1">5.1-20 DigraphMaximumMatching</a>
</div></div>
<div class="ContSect"> <a href="chap5_mj.html#X7D7CE8328187D0DF">5.2 Neighbours and degree</a>

<div class="ContSSBlock">
 <a href="chap5_mj.html#X7DC2CD70830BEE60">5.2-1 AdjacencyMatrix</a>
 <a href="chap5_mj.html#X87FA0A727CDB060B">5.2-2 CharacteristicPolynomial</a>
 <a href="chap5_mj.html#X8507DC4F794780C1">5.2-3 BooleanAdjacencyMatrix</a>
 <a href="chap5_mj.html#X7AFCE34A7A04D5C1">5.2-4 DigraphAdjacencyFunction</a>
 <a href="chap5_mj.html#X7FDEBF3279759961">5.2-5 DigraphRange</a>
 <a href="chap5_mj.html#X7E9880767AE68E00">5.2-6 OutNeighbours</a>
 <a href="chap5_mj.html#X85C7AA5A81DA6E11">5.2-7 InNeighbours</a>
 <a href="chap5_mj.html#X7F5ACE807D1BC2E2">5.2-8 OutDegrees</a>
 <a href="chap5_mj.html#X7ADDFBFD7A365775">5.2-9 InDegrees</a>
 <a href="chap5_mj.html#X7A09EB648070276D">5.2-10 OutDegreeOfVertex</a>
 <a href="chap5_mj.html#X83315B0186850806">5.2-11 OutNeighboursOfVertex</a>
 <a href="chap5_mj.html#X7C9CD0527CB9E6EF">5.2-12 InDegreeOfVertex</a>
 <a href="chap5_mj.html#X7C0DA18B8291F302">5.2-13 InNeighboursOfVertex</a>
 <a href="chap5_mj.html#X83271F607BD809CF">5.2-14 DigraphLoops</a>
 <a href="chap5_mj.html#X7BEAE1C78267F54D">5.2-15 DegreeMatrix</a>
 <a href="chap5_mj.html#X865390B08331936B">5.2-16 LaplacianMatrix</a>
</div></div>
<div class="ContSect"> <a href="chap5_mj.html#X86424F167BD4F629">5.3 Orders</a>

<div class="ContSSBlock">
 <a href="chap5_mj.html#X7DDB33B686B3A2C6">5.3-1 PartialOrderDigraphMeetOfVertices</a>
 <a href="chap5_mj.html#X824B9896798530F6">5.3-2 NonUpperSemimodularPair</a>
</div></div>
<div class="ContSect"> <a href="chap5_mj.html#X8537F4088400DC48">5.4 Reachability and connectivity</a>

<div class="ContSSBlock">
 <a href="chap5_mj.html#X7F16B9EB8398459C">5.4-1 DigraphDiameter</a>
 <a href="chap5_mj.html#X8104A9D37BCD8A05">5.4-2 DigraphShortestDistance</a>
 <a href="chap5_mj.html#X81F99BC67E9D050F">5.4-3 DigraphShortestDistances</a>
 <a href="chap5_mj.html#X8223718079D98A82">5.4-4 DigraphLongestDistanceFromVertex</a>
 <a href="chap5_mj.html#X7CB7DDCD84621D38">5.4-5 DigraphDistanceSet</a>
 <a href="chap5_mj.html#X79A3DA4078CF3C90">5.4-6 DigraphGirth</a>
 <a href="chap5_mj.html#X8374B7357EC189C1">5.4-7 DigraphOddGirth</a>
 <a href="chap5_mj.html#X84688B337BDDBB09">5.4-8 DigraphUndirectedGirth</a>
 <a href="chap5_mj.html#X842FAD6A7B835977">5.4-9 DigraphConnectedComponents</a>
 <a href="chap5_mj.html#X8484EC557810CD31">5.4-10 DigraphConnectedComponent</a>
 <a href="chap5_mj.html#X833ECD6B7A84944C">5.4-11 DigraphStronglyConnectedComponents</a>
 <a href="chap5_mj.html#X7EFCB5017D662254">5.4-12 DigraphStronglyConnectedComponent</a>
 <a href="chap5_mj.html#X7F1B5A2782F598B1">5.4-13 DigraphBicomponents</a>
 <a href="chap5_mj.html#X7DDE06E47E605DD7">5.4-14 ArticulationPoints</a>
 <a href="chap5_mj.html#X803459AB86AB9BE2">5.4-15 MinimalCyclicEdgeCut</a>
 <a href="chap5_mj.html#X84D5A125848BD800">5.4-16 Bridges</a>
 <a href="chap5_mj.html#X865590147BD1C507">5.4-17 StrongOrientation</a>
 <a href="chap5_mj.html#X853D0B0981A33433">5.4-18 DigraphPeriod</a>
 <a href="chap5_mj.html#X864A31A8809F61C2">5.4-19 DigraphFloydWarshall</a>
 <a href="chap5_mj.html#X7FBAB09E7C0BE5CF">5.4-20 IsReachable</a>
 <a href="chap5_mj.html#X7ECD22877AEA89CC">5.4-21 IsDigraphPath</a>
 <a href="chap5_mj.html#X7F255A2A84CB868C">5.4-22 VerticesReachableFrom</a>
 <a href="chap5_mj.html#X8039170B82A32257">5.4-23 DigraphPath</a>
 <a href="chap5_mj.html#X80E9D645843973A6">5.4-24 DigraphShortestPath</a>
 <a href="chap5_mj.html#X7C45396C808308C4">5.4-25 DigraphRandomWalk</a>
 <a href="chap5_mj.html#X787459247B2005E6">5.4-26 DigraphAbsorptionProbabilities</a>
 <a href="chap5_mj.html#X7B0A62CF7F6F23E9">5.4-27 DigraphAbsorptionExpectedSteps</a>
 <a href="chap5_mj.html#X7FE79CB278CE6991">5.4-28 Dominators</a>
 <a href="chap5_mj.html#X7D66A0FB7F6100FB">5.4-29 DominatorTree</a>
 <a href="chap5_mj.html#X7C0416FE7A69CA2C">5.4-30 IteratorOfPaths</a>
 <a href="chap5_mj.html#X7ECD16838704FAAA">5.4-31 DigraphAllSimpleCircuits</a>
 <a href="chap5_mj.html#X7C735C4E86BDD5F6">5.4-32 DigraphLongestSimpleCircuit</a>
 <a href="chap5_mj.html#X7F9EDAA8854FB538">5.4-33 DigraphAllUndirectedSimpleCircuits</a>
 <a href="chap5_mj.html#X7F0AC5617CE5E9DD">5.4-34 DigraphAllChordlessCycles</a>
 <a href="chap5_mj.html#X805F15398735AD7D">5.4-35 FacialWalks</a>
 <a href="chap5_mj.html#X870E04307C5F213F">5.4-36 DigraphLayers</a>
 <a href="chap5_mj.html#X7B2E42327DA118E0">5.4-37 DigraphDegeneracy</a>
 <a href="chap5_mj.html#X827C2BD17A4547E3">5.4-38 DigraphDegeneracyOrdering</a>
 <a href="chap5_mj.html#X863FDFC4839A3B82">5.4-39 HamiltonianPath</a>
 <a href="chap5_mj.html#X82F30D5681466BC6">5.4-40 NrSpanningTrees</a>
 <a href="chap5_mj.html#X79352A8286D1D8F6">5.4-41 DigraphDijkstra</a>
 <a href="chap5_mj.html#X794CD6037D4CF58C">5.4-42 DigraphCycleBasis</a>
 <a href="chap5_mj.html#X835AAF9085BC9D84">5.4-43 DigraphIsKing</a>
 <a href="chap5_mj.html#X7A17B9B67AC50561">5.4-44 DigraphKings</a>
</div></div>
<div class="ContSect"> <a href="chap5_mj.html#X82F900777D677F55">5.5 Cayley graphs of groups</a>

<div class="ContSSBlock">
 <a href="chap5_mj.html#X7A000B1D7CCF7093">5.5-1 GroupOfCayleyDigraph</a>
 <a href="chap5_mj.html#X8528455987D7D2BF">5.5-2 GeneratorsOfCayleyDigraph</a>
</div></div>
<div class="ContSect"> <a href="chap5_mj.html#X790FD6647ECCAE3C">5.6 Associated semigroups</a>

<div class="ContSSBlock">
 <a href="chap5_mj.html#X87D5C60D7B0C1309">5.6-1 AsSemigroup</a>
 <a href="chap5_mj.html#X7C6D5EC27C51066B">5.6-2 AsSemigroup</a>
</div></div>
<div class="ContSect"> <a href="chap5_mj.html#X7E2305528492DDC0">5.7 Planarity</a>

<div class="ContSSBlock">
 <a href="chap5_mj.html#X7DC478637E8C190D">5.7-1 KuratowskiPlanarSubdigraph</a>
 <a href="chap5_mj.html#X78E8F09A8286501B">5.7-2 KuratowskiOuterPlanarSubdigraph</a>
 <a href="chap5_mj.html#X84E3947E7D39BA64">5.7-3 PlanarEmbedding</a>
 <a href="chap5_mj.html#X85DFB8C18088711F">5.7-4 OuterPlanarEmbedding</a>
 <a href="chap5_mj.html#X806D2D6B85E0B269">5.7-5 SubdigraphHomeomorphicToK23</a>
 <a href="chap5_mj.html#X876803517C34E1CD">5.7-6 DualPlanarGraph</a>
</div></div>
<div class="ContSect"> <a href="chap5_mj.html#X7FF5E2D07D48647E">5.8 Hashing</a>

<div class="ContSSBlock">
 <a href="chap5_mj.html#X7D97D990867B0149">5.8-1 DigraphHash</a>
</div></div>
</div>

<h3>5 Attributes and operations</h3>

<a id="X7E814B6478F7D015" name="X7E814B6478F7D015"></a>

<h4>5.1 Vertices and edges</h4>

<a id="X7C45F7D878D896AC" name="X7C45F7D878D896AC"></a>

<h5>5.1-1 DigraphVertices</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DigraphVertices</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
Returns: A list of positive integers.

Returns the vertices of the digraph <var class="Arg">digraph</var>.

Note that the vertices of a digraph are always the range of positive integers from <code class="code">1</code> to the number of vertices of the graph, <code class="func">DigraphNrVertices</code> (<a href="chap5_mj.html#X7C6F19B57CB2E882">5.1-2</a>). Arbitrary labels can be assigned to the vertices of a digraph; see <code class="func">DigraphVertexLabels</code> (<a href="chap5_mj.html#X7E51F2FE87140B32">5.1-12</a>) for more information about this.

<div class="example"><pre>
gap> gr := Digraph(["a", "b", "c"],
> ["a", "b", "b"],
> ["b", "c", "a"]);
<immutable digraph with 3 vertices, 3 edges>
gap> DigraphVertices(gr);
[ 1 .. 3 ]
gap> gr := Digraph([1, 2, 3, 4, 5, 7],
> [1, 2, 2, 4, 4],
> [2, 7, 5, 3, 7]);
<immutable digraph with 6 vertices, 5 edges>
gap> DigraphVertices(gr);
[ 1 .. 6 ]
gap> DigraphVertices(RandomDigraph(100));
[ 1 .. 100 ]
gap> D := CycleDigraph(IsMutableDigraph, 3);
<mutable digraph with 3 vertices, 3 edges>
gap> DigraphVertices(D);
[ 1 .. 3 ]
</pre></div>

<a id="X7C6F19B57CB2E882" name="X7C6F19B57CB2E882"></a>

<h5>5.1-2 DigraphNrVertices</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DigraphNrVertices</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
Returns: An non-negative integer.

Returns the number of vertices of the digraph <var class="Arg">digraph</var>.

<div class="example"><pre>
gap> gr := Digraph(["a", "b", "c"],
> ["a", "b", "b"],
> ["b", "c", "a"]);
<immutable digraph with 3 vertices, 3 edges>
gap> DigraphNrVertices(gr);
3
gap> gr := Digraph([1, 2, 3, 4, 5, 7],
> [1, 2, 2, 4, 4],
> [2, 7, 5, 3, 7]);
<immutable digraph with 6 vertices, 5 edges>
gap> DigraphNrVertices(gr);
6
gap> DigraphNrVertices(RandomDigraph(100));
100
gap> D := CycleDigraph(IsMutableDigraph, 3);
<mutable digraph with 3 vertices, 3 edges>
gap> DigraphNrVertices(D);
3
</pre></div>

<a id="X7D1C6A4D7ECEC317" name="X7D1C6A4D7ECEC317"></a>

<h5>5.1-3 DigraphEdges</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DigraphEdges</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
Returns: A list of lists of two positive integers.

Returns a list of edges of the digraph <var class="Arg">digraph</var>, where each edge is a pair of elements of <code class="func">DigraphVertices</code> (<a href="chap5_mj.html#X7C45F7D878D896AC">5.1-1</a>) of the form <code class="code">[source,range]</code>.

The entries of <code class="code">DigraphEdges(</code><var class="Arg">digraph</var><code class="code">)</code> are in one-to-one correspondence with the edges of <var class="Arg">digraph</var>. Hence <code class="code">DigraphEdges(</code><var class="Arg">digraph</var><code class="code">)</code> is duplicate-free if and only if <var class="Arg">digraph</var> contains no multiple edges.

The entries of <code class="code">DigraphEdges</code> are guaranteed to be sorted by their first component (i.e. by the source of each edge), but they are not necessarily then sorted by the second component.

<div class="example"><pre>
gap> gr := DigraphFromDiSparse6String(".DaXbOe?EAM@G~");
<immutable multidigraph with 5 vertices, 16 edges>
gap> edges := ShallowCopy(DigraphEdges(gr));; Sort(edges);
gap> edges;
[ [ 1, 1 ], [ 1, 3 ], [ 1, 3 ], [ 1, 4 ], [ 1, 5 ], [ 2, 1 ],
 [ 2, 2 ], [ 2, 3 ], [ 2, 5 ], [ 3, 2 ], [ 3, 4 ], [ 3, 5 ],
 [ 4, 2 ], [ 4, 4 ], [ 4, 5 ], [ 5, 1 ] ]
gap> D := CycleDigraph(IsMutableDigraph, 3);
<mutable digraph with 3 vertices, 3 edges>
gap> DigraphEdges(D);
[ [ 1, 2 ], [ 2, 3 ], [ 3, 1 ] ]
</pre></div>

<a id="X85E1CFDD7E164AD0" name="X85E1CFDD7E164AD0"></a>

<h5>5.1-4 DigraphNrEdges</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DigraphNrEdges</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
Returns: An integer.

Returns the number of edges of the digraph <var class="Arg">digraph</var>.

<div class="example"><pre>
gap> gr := Digraph([
> [1, 3, 4, 5], [1, 2, 3, 5], [2, 4, 5], [2, 4, 5], [1]]);;
gap> DigraphNrEdges(gr);
15
gap> gr := Digraph(["a", "b", "c"],
> ["a", "b", "b"],
> ["b", "a", "a"]);
<immutable multidigraph with 3 vertices, 3 edges>
gap> DigraphNrEdges(gr);
3
gap> D := CycleDigraph(IsMutableDigraph, 3);
<mutable digraph with 3 vertices, 3 edges>
gap> DigraphNrEdges(D);
3
</pre></div>

<a id="X7BD5D255809C859E" name="X7BD5D255809C859E"></a>

<h5>5.1-5 DigraphNrAdjacencies</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DigraphNrAdjacencies</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
Returns: An integer.

Returns the number of sets \(\{u, v\}\) of vertices of the digraph <var class="Arg">digraph</var>, such that either \((u, v)\) or \((v, u)\) is an edge. The following equality holds for any digraph <code class="code">D</code> with no multiple edges: <code class="code">DigraphNrAdjacencies(D) * 2 - DigraphNrLoops(D) = DigraphNrEdges(DigraphSymmetricClosure(D))</code>.

<div class="example"><pre>
gap> gr := Digraph([
> [1, 3, 4, 5], [1, 2, 3, 5], [2, 4, 5], [2, 4, 5], [1]]);;
gap> DigraphNrAdjacencies(gr);
13
gap> DigraphNrAdjacencies(gr) * 2 - DigraphNrLoops(gr) =
> DigraphNrEdges(DigraphSymmetricClosure(gr));
true
</pre></div>

<a id="X7E53E728795BB862" name="X7E53E728795BB862"></a>

<h5>5.1-6 DigraphNrAdjacenciesWithoutLoops</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DigraphNrAdjacenciesWithoutLoops</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
Returns: An integer.

Returns the number of sets \(\{u, v\}\) of vertices of the digraph <var class="Arg">digraph</var>, such that \(u \neq v\) and either \((u, v)\) or \((v, u)\) is an edge. The following equality holds for any digraph <code class="code">D</code> with no multiple edges: <code class="code">DigraphNrAdjacenciesWithoutLoops(D) * 2 + DigraphNrLoops(D) = DigraphNrEdges(DigraphSymmetricClosure(D))</code>.

<div class="example"><pre>
gap> gr := Digraph([
> [1, 3, 4, 5], [1, 2, 3, 5], [2, 4, 5], [2, 4, 5], [1]]);;
gap> DigraphNrAdjacenciesWithoutLoops(gr);
10
gap> DigraphNrAdjacenciesWithoutLoops(gr) * 2 + DigraphNrLoops(gr) =
> DigraphNrEdges(DigraphSymmetricClosure(gr));
true
</pre></div>

<a id="X7BDABAF07917462B" name="X7BDABAF07917462B"></a>

<h5>5.1-7 DigraphNrLoops</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DigraphNrLoops</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
Returns: An integer.

This function returns the number of loops of the digraph <var class="Arg">digraph</var>. See <code class="func">DigraphHasLoops</code> (<a href="chap6_mj.html#X7D92935C7D535187">6.2-1</a>).

<div class="example"><pre>
gap> D := Digraph([[2, 3], [1, 4], [3, 3, 5], [], [2, 5]]);
<immutable multidigraph with 5 vertices, 9 edges>
gap> DigraphNrLoops(D);
3
gap> D := EmptyDigraph(5);
<immutable empty digraph with 5 vertices>
gap> DigraphNrLoops(D);
0
gap> D := CompleteDigraph(5);
<immutable complete digraph with 5 vertices>
gap> DigraphNrLoops(D);
0
</pre></div>

<a id="X85D5E08280914EE4" name="X85D5E08280914EE4"></a>

<h5>5.1-8 DigraphSinks</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DigraphSinks</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
Returns: A list of vertices.

This function returns a list of the sinks of the digraph <var class="Arg">digraph</var>. A sink of a digraph is a vertex with out-degree zero. See <code class="func">OutDegreeOfVertex</code> (<a href="chap5_mj.html#X7A09EB648070276D">5.2-10</a>).

<div class="example"><pre>
gap> gr := Digraph([[3, 5, 2, 2], [3], [], [5, 2, 5, 3], []]);
<immutable multidigraph with 5 vertices, 9 edges>
gap> DigraphSinks(gr);
[ 3, 5 ]
gap> D := CycleDigraph(IsMutableDigraph, 3);
<mutable digraph with 3 vertices, 3 edges>
gap> DigraphSinks(D);
[ ]
</pre></div>

<a id="X7F5C6268839BE98C" name="X7F5C6268839BE98C"></a>

<h5>5.1-9 DigraphSources</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DigraphSources</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
Returns: A list of vertices.

This function returns an immutable list of the sources of the digraph <var class="Arg">digraph</var>. A source of a digraph is a vertex with in-degree zero. See <code class="func">InDegreeOfVertex</code> (<a href="chap5_mj.html#X7C9CD0527CB9E6EF">5.2-12</a>).

<div class="example"><pre>
gap> gr := Digraph([[3, 5, 2, 2], [3], [], [5, 2, 5, 3], []]);
<immutable multidigraph with 5 vertices, 9 edges>
gap> DigraphSources(gr);
[ 1, 4 ]
gap> D := CycleDigraph(IsMutableDigraph, 3);
<mutable digraph with 3 vertices, 3 edges>
gap> DigraphSources(D);
[ ]
</pre></div>

<a id="X785C30378064CF47" name="X785C30378064CF47"></a>

<h5>5.1-10 DigraphTopologicalSort</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DigraphTopologicalSort</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
Returns: A list of positive integers, or <code class="keyw">fail</code>.

If <var class="Arg">digraph</var> is a digraph whose only directed cycles are loops, then <code class="code">DigraphTopologicalSort</code> returns the vertices of <var class="Arg">digraph</var> ordered so that every edge's source appears no earlier in the list than its range. If the digraph <var class="Arg">digraph</var> contains directed cycles of length greater than \(1\), then this operation returns <code class="keyw">fail</code>.

See Section <a href="chap1_mj.html#X84541F61810C741D">1.1-1</a> for the definition of a directed cycle, and the definition of a loop.

The method used for this attribute has complexity \(O(m+n)\) where \(m\) is the number of edges (counting multiple edges as one) and \(n\) is the number of vertices in the digraph.

<div class="example"><pre>
gap> D := Digraph([
> [2, 3], [], [4, 6], [5], [], [7, 8, 9], [], [], []]);
<immutable digraph with 9 vertices, 8 edges>
gap> DigraphTopologicalSort(D);
[ 2, 5, 4, 7, 8, 9, 6, 3, 1 ]
gap> D := Digraph(IsMutableDigraph, [[2, 3], [3], [4], []]);
<mutable digraph with 4 vertices, 4 edges>
gap> DigraphTopologicalSort(D);
[ 4, 3, 2, 1 ]
</pre></div>

<a id="X7CA91E4B7904F793" name="X7CA91E4B7904F793"></a>

<h5>5.1-11 DigraphVertexLabel</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DigraphVertexLabel</code>( <var class="Arg">digraph</var>, <var class="Arg">i</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ SetDigraphVertexLabel</code>( <var class="Arg">digraph</var>, <var class="Arg">i</var>, <var class="Arg">obj</var> )</td><td class="tdright">( operation )</td></tr></table></div>
If <var class="Arg">digraph</var> is a digraph, then the first operation returns the label of the vertex <var class="Arg">i</var>. The second operation can be used to set the label of the vertex <var class="Arg">i</var> in <var class="Arg">digraph</var> to the arbitrary GAP object <var class="Arg">obj</var>.

The label of a vertex can be changed an arbitrary number of times. If no label has been set for the vertex <var class="Arg">i</var>, then the default value is <var class="Arg">i</var>.

If <var class="Arg">digraph</var> is a digraph created from a record with a component <code class="code">DigraphVertices</code>, then the labels of the vertices are set to the value of this component.

Induced subdigraphs, and some other operations which create new digraphs from old ones, inherit their labels from their parents.

<div class="example"><pre>
gap> D := DigraphFromDigraph6String("&DHUEe_");
<immutable digraph with 5 vertices, 11 edges>
gap> DigraphVertexLabel(D, 3);
3
gap> D := Digraph(["a", "b", "c"], [], []);
<immutable empty digraph with 3 vertices>
gap> DigraphVertexLabel(D, 2);
"b"
gap> SetDigraphVertexLabel(D, 2, "d");
gap> DigraphVertexLabel(D, 2);
"d"
gap> D := InducedSubdigraph(D, [1, 2]);
<immutable empty digraph with 2 vertices>
gap> DigraphVertexLabel(D, 2);
"d"
gap> D := Digraph(IsMutableDigraph, ["e", "f", "g"], [], []);
<mutable empty digraph with 3 vertices>
gap> DigraphVertexLabel(D, 1);
"e"
gap> SetDigraphVertexLabel(D, 1, "h");
gap> DigraphVertexLabel(D, 1);
"h"
gap> InducedSubdigraph(D, [1, 2]);
<mutable empty digraph with 2 vertices>
gap> DigraphVertexLabel(D, 1);
"h"
</pre></div>

<a id="X7E51F2FE87140B32" name="X7E51F2FE87140B32"></a>

<h5>5.1-12 DigraphVertexLabels</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DigraphVertexLabels</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ SetDigraphVertexLabels</code>( <var class="Arg">digraph</var>, <var class="Arg">list</var> )</td><td class="tdright">( operation )</td></tr></table></div>
If <var class="Arg">digraph</var> is a digraph, then <code class="code">DigraphVertexLabels</code> returns a copy of the labels of the vertices in <var class="Arg">digraph</var>. <code class="code">SetDigraphVertexLabels</code> can be used to set the labels of the vertices in <var class="Arg">digraph</var> to the list of arbitrary GAP objects <var class="Arg">list</var>, which must be of the same length as the number of vertices of <var class="Arg">digraph</var>.

If the list <var class="Arg">list</var> is immutable, then the vertex labels are set to a mutable copy of <var class="Arg">list</var>. Otherwise, the labels are set to exactly <var class="Arg">list</var>.

The label of a vertex can be changed an arbitrary number of times. If no label has been set for the vertex <var class="Arg">i</var>, then the default value is <var class="Arg">i</var>.

If <var class="Arg">digraph</var> is a digraph created from a record with a component <code class="code">DigraphVertices</code>, then the labels of the vertices are set to the value of this component. As in the above, if the component is immutable then the digraph's vertex labels are set to a mutable copy of <code class="code">DigraphVertices</code>. Otherwise, they are set to exactly <code class="code">DigraphVertices</code>.

Induced subdigraphs, and other operations which create new digraphs from old ones, inherit their labels from their parents.

<div class="example"><pre>
gap> D := DigraphFromDigraph6String("&DHUEe_");
<immutable digraph with 5 vertices, 11 edges>
gap> DigraphVertexLabels(D);
[ 1 .. 5 ]
gap> D := Digraph(["a", "b", "c"], [], []);
<immutable empty digraph with 3 vertices>
gap> DigraphVertexLabels(D);
[ "a", "b", "c" ]
gap> SetDigraphVertexLabel(D, 2, "d");
gap> DigraphVertexLabels(D);
[ "a", "d", "c" ]
gap> D := InducedSubdigraph(D, [1, 3]);
<immutable empty digraph with 2 vertices>
gap> DigraphVertexLabels(D);
[ "a", "c" ]
gap> D := Digraph(IsMutableDigraph, ["e", "f", "g"], [], []);
<mutable empty digraph with 3 vertices>
gap> SetDigraphVertexLabels(D, ["h", "i", "j"]);
gap> DigraphVertexLabels(D);
[ "h", "i", "j" ]
gap> InducedSubdigraph(D, [1, 3]);
<mutable empty digraph with 2 vertices>
gap> DigraphVertexLabels(D);
[ "h", "j" ]
</pre></div>

<a id="X79FAEACC7F438C2F" name="X79FAEACC7F438C2F"></a>

<h5>5.1-13 DigraphEdgeLabel</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DigraphEdgeLabel</code>( <var class="Arg">digraph</var>, <var class="Arg">i</var>, <var class="Arg">j</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ SetDigraphEdgeLabel</code>( <var class="Arg">digraph</var>, <var class="Arg">i</var>, <var class="Arg">j</var>, <var class="Arg">obj</var> )</td><td class="tdright">( operation )</td></tr></table></div>
If <var class="Arg">digraph</var> is a digraph without multiple edges, then the first operation returns the label of the edge from vertex <var class="Arg">i</var> to vertex <var class="Arg">j</var>. The second operation can be used to set the label of the edge between vertex <var class="Arg">i</var> and vertex <var class="Arg">j</var> to the arbitrary GAP object <var class="Arg">obj</var>.

The label of an edge can be changed an arbitrary number of times. If no label has been set for the edge, then the default value is <var class="Arg">1</var>.

Induced subdigraphs, and some other operations which create new digraphs from old ones, inherit their edge labels from their parents. See also <code class="func">DigraphEdgeLabels</code> (<a href="chap5_mj.html#X7C24851087D4A8FB">5.1-14</a>).

<div class="example"><pre>
gap> D := DigraphFromDigraph6String("&DHUEe_");
<immutable digraph with 5 vertices, 11 edges>
gap> DigraphEdgeLabel(D, 3, 1);
1
gap> SetDigraphEdgeLabel(D, 2, 5, [42]);
gap> DigraphEdgeLabel(D, 2, 5);
[ 42 ]
gap> D := InducedSubdigraph(D, [2, 5]);
<immutable digraph with 2 vertices, 3 edges>
gap> DigraphEdgeLabel(D, 1, 2);
[ 42 ]
gap> D := ChainDigraph(IsMutableDigraph, 5);
<mutable digraph with 5 vertices, 4 edges>
gap> DigraphEdgeLabel(D, 2, 3);
1
gap> SetDigraphEdgeLabel(D, 4, 5, [1729]);
gap> DigraphEdgeLabel(D, 4, 5);
[ 1729 ]
gap> InducedSubdigraph(D, [4, 5]);
<mutable digraph with 2 vertices, 1 edge>
gap> DigraphEdgeLabel(D, 1, 2);
[ 1729 ]
</pre></div>

<a id="X7C24851087D4A8FB" name="X7C24851087D4A8FB"></a>

<h5>5.1-14 DigraphEdgeLabels</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DigraphEdgeLabels</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ SetDigraphEdgeLabels</code>( <var class="Arg">digraph</var>, <var class="Arg">labels</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ SetDigraphEdgeLabels</code>( <var class="Arg">digraph</var>, <var class="Arg">func</var> )</td><td class="tdright">( operation )</td></tr></table></div>
If <var class="Arg">digraph</var> is a digraph without multiple edges, then <code class="code">DigraphEdgeLabels</code> returns a copy of the labels of the edges in <var class="Arg">digraph</var> as a list of lists <code class="code">labels</code> such that <code class="code">labels[i][j]</code> is the label on the edge from vertex <code class="code">i</code> to vertex <code class="code">OutNeighbours(digraph)[i][j]</code>. <code class="code">SetDigraphEdgeLabels</code> can be used to set the labels of the edges in <var class="Arg">digraph</var> without multiple edges to the list <var class="Arg">labels</var> of lists of arbitrary GAP objects such that <code class="code">list[i][j]</code> is the label on the edge from vertex <code class="code">i</code> to the vertex <code class="code">OutNeighbours(digraph>[i][j]</code>. Alternatively <code class="code">SetDigraphEdgeLabels</code> can be called with binary function <var class="Arg">func</var> that as its second argument that when passed two vertices <code class="code">i</code> and <code class="code">j</code> returns the label for the edge between vertex <code class="code">i</code> and vertex <code class="code">j</code>.

The label of an edge can be changed an arbitrary number of times. If no label has been set for an edge, then the default value is <code class="code">1</code>.

Induced subdigraphs, and some other operations which create new digraphs from old ones, inherit their labels from their parents.

<div class="example"><pre>
gap> D := DigraphFromDigraph6String("&DHUEe_");
<immutable digraph with 5 vertices, 11 edges>
gap> DigraphEdgeLabels(D);
[ [ 1 ], [ 1, 1, 1 ], [ 1 ], [ 1, 1, 1 ], [ 1, 1, 1 ] ]
gap> SetDigraphEdgeLabel(D, 2, 1, "d");
gap> DigraphEdgeLabels(D);
[ [ 1 ], [ "d", 1, 1 ], [ 1 ], [ 1, 1, 1 ], [ 1, 1, 1 ] ]
gap> D := InducedSubdigraph(D, [1, 2, 3]);
<immutable digraph with 3 vertices, 4 edges>
gap> DigraphEdgeLabels(D);
[ [ 1 ], [ "d", 1 ], [ 1 ] ]
gap> OutNeighbours(D);
[ [ 3 ], [ 1, 3 ], [ 1 ] ]
gap> D := CompleteBipartiteDigraph(IsMutableDigraph, 2, 3);
<mutable digraph with 5 vertices, 12 edges>
gap> DigraphEdgeLabels(D);
[ [ 1, 1, 1 ], [ 1, 1, 1 ], [ 1, 1 ], [ 1, 1 ], [ 1, 1 ] ]
gap> SetDigraphEdgeLabel(D, 2, 4, "a");
gap> DigraphEdgeLabels(D);
[ [ 1, 1, 1 ], [ 1, "a", 1 ], [ 1, 1 ], [ 1, 1 ], [ 1, 1 ] ]
gap> InducedSubdigraph(D, [1, 2, 3, 4]);
<mutable digraph with 4 vertices, 8 edges>
gap> DigraphEdgeLabels(D);
[ [ 1, 1 ], [ 1, "a" ], [ 1, 1 ], [ 1, 1 ] ]
gap> OutNeighbors(D);
[ [ 3, 4 ], [ 3, 4 ], [ 1, 2 ], [ 1, 2 ] ]
</pre></div>

<a id="X7EFAF01B7A155157" name="X7EFAF01B7A155157"></a>

<h5>5.1-15 DigraphInEdges</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DigraphInEdges</code>( <var class="Arg">digraph</var>, <var class="Arg">vertex</var> )</td><td class="tdright">( operation )</td></tr></table></div>
Returns: A list of edges.

<code class="code">DigraphInEdges</code> returns the list of all edges of <var class="Arg">digraph</var> which have <var class="Arg">vertex</var> as their range.

<div class="example"><pre>
gap> D := Digraph([[2, 2], [3, 3], [4, 4], [1, 1]]);
<immutable multidigraph with 4 vertices, 8 edges>
gap> DigraphInEdges(D, 2);
[ [ 1, 2 ], [ 1, 2 ] ]
</pre></div>

<a id="X7BECFE6687ECD028" name="X7BECFE6687ECD028"></a>

<h5>5.1-16 DigraphOutEdges</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DigraphOutEdges</code>( <var class="Arg">digraph</var>, <var class="Arg">vertex</var> )</td><td class="tdright">( operation )</td></tr></table></div>
Returns: A list of edges.

<code class="code">DigraphOutEdges</code> returns the list of all edges of <var class="Arg">digraph</var> which have <var class="Arg">vertex</var> as their source.

<div class="example"><pre>
gap> D := Digraph([[2, 2], [3, 3], [4, 4], [1, 1]]);
<immutable multidigraph with 4 vertices, 8 edges>
gap> DigraphOutEdges(D, 2);
[ [ 2, 3 ], [ 2, 3 ] ]
</pre></div>

<a id="X7BB8ED88835F07B4" name="X7BB8ED88835F07B4"></a>

<h5>5.1-17 IsDigraphEdge</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsDigraphEdge</code>( <var class="Arg">digraph</var>, <var class="Arg">list</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsDigraphEdge</code>( <var class="Arg">digraph</var>, <var class="Arg">u</var>, <var class="Arg">v</var> )</td><td class="tdright">( operation )</td></tr></table></div>
Returns: <code class="keyw">true</code> or <code class="keyw">false</code>.

In the first form, this function returns <code class="keyw">true</code> if and only if the list <var class="Arg">list</var> specifies an edge in the digraph <var class="Arg">digraph</var>. Specifically, this operation returns <code class="keyw">true</code> if <var class="Arg">list</var> is a pair of positive integers where <var class="Arg">list</var><code class="code">[1]</code> is the source and <var class="Arg">list</var><code class="code">[2]</code> is the range of an edge in <var class="Arg">digraph</var>, and <code class="keyw">false</code> otherwise.

The second form simply returns <code class="keyw">true</code> if <code class="code">[<var class="Arg">u</var>, <var class="Arg">v</var>]</code> is an edge in <var class="Arg">digraph</var>, and <code class="keyw">false</code> otherwise.

<div class="example"><pre>
gap> D := Digraph([[2, 2], [6], [], [3], [], [1]]);
<immutable multidigraph with 6 vertices, 5 edges>
gap> IsDigraphEdge(D, [1, 1]);
false
gap> IsDigraphEdge(D, [1, 2]);
true
gap> IsDigraphEdge(D, [1, 8]);
false
</pre></div>

<a id="X848FED0B7B4ACD1F" name="X848FED0B7B4ACD1F"></a>

<h5>5.1-18 IsMatching</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsMatching</code>( <var class="Arg">digraph</var>, <var class="Arg">list</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsMaximalMatching</code>( <var class="Arg">digraph</var>, <var class="Arg">list</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsMaximumMatching</code>( <var class="Arg">digraph</var>, <var class="Arg">list</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsPerfectMatching</code>( <var class="Arg">digraph</var>, <var class="Arg">list</var> )</td><td class="tdright">( operation )</td></tr></table></div>
Returns: <code class="keyw">true</code> or <code class="keyw">false</code>.

If <var class="Arg">digraph</var> is a digraph and <var class="Arg">list</var> is a list of pairs of vertices of <var class="Arg">digraph</var>, then <code class="code">IsMatching</code> returns <code class="keyw">true</code> if <var class="Arg">list</var> is a matching of <var class="Arg">digraph</var>. The operation <code class="code">IsMaximalMatching</code> returns <code class="keyw">true</code> if <var class="Arg">list</var> is a maximal matching, <code class="code">IsMaximumMatching</code> returns <code class="keyw">true</code> if <var class="Arg">list</var> is a maximum matching and <code class="code">IsPerfectMatching</code> returns <code class="keyw">true</code> if <var class="Arg">list</var> is a perfect, matching of <var class="Arg">digraph</var>, respectively. Otherwise, each of these operations return <code class="keyw">false</code>.

A matching <code class="code">M</code> of a digraph <var class="Arg">digraph</var> is a subset of the edges of <var class="Arg">digraph</var>, i.e. <code class="code">DigraphEdges(<var class="Arg">digraph</var>)</code>, such that no pair of distinct edges in <code class="code">M</code> are incident to the same vertex of <var class="Arg">digraph</var>. Note that this definition allows a matching to contain loops. See <code class="func">DigraphHasLoops</code> (<a href="chap6_mj.html#X7D92935C7D535187">6.2-1</a>). The matching <code class="code">M</code> is maximal if it is contained in no larger matching of the digraph, is maximum if it has the greatest cardinality among all matchings and is perfect if every vertex of the digraph is incident to an edge in the matching. Every maximum or perfect matching is maximal. Note, however, that not every perfect matching of digraphs with loops is maximum.

<div class="example"><pre>
gap> D := Digraph([[1, 2], [1, 2], [2, 3, 4], [3, 5], [1]]);
<immutable digraph with 5 vertices, 10 edges>
gap> IsMatching(D, [[2, 1], [3, 2]]);
false
gap> edges := [[3, 2]];;
gap> IsMatching(D, edges);
true
gap> IsMaximalMatching(D, edges);
false
gap> edges := [[2, 1], [3, 4]];;
gap> IsMaximalMatching(D, edges);
true
gap> IsPerfectMatching(D, edges);
false
gap> edges := [[1, 2], [3, 3], [4, 5]];;
gap> IsPerfectMatching(D, edges);
true
gap> IsMaximumMatching(D, edges);
false
gap> edges := [[1, 1], [2, 2], [3, 3], [4, 5]];;
gap> IsMaximumMatching(D, edges);
true
</pre></div>

<a id="X7B7A67277B1C9A02" name="X7B7A67277B1C9A02"></a>

<h5>5.1-19 DigraphMaximalMatching</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DigraphMaximalMatching</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
Returns: A list of pairs of vertices.

This function returns a maximal matching of the digraph <var class="Arg">digraph</var>.

For the definition of a maximal matching, see <code class="func">IsMaximalMatching</code> (<a href="chap5_mj.html#X848FED0B7B4ACD1F">5.1-18</a>).

<div class="example"><pre>
gap> D := DigraphFromDiSparse6String(".IeAoXCJU@|SHAe?d");
<immutable digraph with 10 vertices, 13 edges>
gap> M := DigraphMaximalMatching(D);; IsMaximalMatching(D, M);
true
gap> D := RandomDigraph(100);;
gap> IsMaximalMatching(D, DigraphMaximalMatching(D));
true
gap> D := GeneralisedPetersenGraph(IsMutableDigraph, 9, 2);
<mutable digraph with 18 vertices, 54 edges>
gap> IsMaximalMatching(D, DigraphMaximalMatching(D));
true
</pre></div>

<a id="X78E9847A858788D1" name="X78E9847A858788D1"></a>

<h5>5.1-20 DigraphMaximumMatching</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DigraphMaximumMatching</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
Returns: A list of pairs of vertices.

This function returns a maximum matching of the digraph <var class="Arg">digraph</var>.

For the definition of a maximum matching, see <code class="func">IsMaximumMatching</code> (<a href="chap5_mj.html#X848FED0B7B4ACD1F">5.1-18</a>). If <var class="Arg">digraph</var> is bipartite (see <code class="func">IsBipartiteDigraph</code> (<a href="chap6_mj.html#X860CFB0C8665F356">6.2-3</a>)), then the algorithm used has complexity <code class="code">O(m*sqrt(n))</code>. Otherwise for general graphs the complexity is <code class="code">O(m*n*log(n))</code>. Here <code class="code">n</code> is the number of vertices and <code class="code">m</code> is the number of edges.

<div class="example"><pre>
gap> D := DigraphFromDigraph6String("&I@EA_A?AdDp[_c??OO");
<immutable digraph with 10 vertices, 23 edges>
gap> M := DigraphMaximumMatching(D);; IsMaximalMatching(D, M);
true
gap> Length(M);
5
gap> D := Digraph([[5, 6, 7, 8], [6, 7, 8], [7, 8], [8], 
> [], [], [], []]);;
gap> M := DigraphMaximumMatching(D);
[ [ 1, 5 ], [ 2, 6 ], [ 3, 7 ], [ 4, 8 ] ]
gap> D := GeneralisedPetersenGraph(IsMutableDigraph, 9, 2);
<mutable digraph with 18 vertices, 54 edges>
gap> M := DigraphMaximumMatching(D);;
gap> IsMaximalMatching(D, M);
true
gap> Length(M);
9
</pre></div>

<a id="X7D7CE8328187D0DF" name="X7D7CE8328187D0DF"></a>

<h4>5.2 Neighbours and degree</h4>

<a id="X7DC2CD70830BEE60" name="X7DC2CD70830BEE60"></a>

<h5>5.2-1 AdjacencyMatrix</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ AdjacencyMatrix</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ AdjacencyMatrixMutableCopy</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( operation )</td></tr></table></div>
Returns: A square matrix of non-negative integers.

This function returns the adjacency matrix <code class="code">mat</code> of the digraph <var class="Arg">digraph</var>. The value of the matrix entry <code class="code">mat[i][j]</code> is the number of edges in <var class="Arg">digraph</var> with source <code class="code">i</code> and range <code class="code">j</code>. If <var class="Arg">digraph</var> has no vertices, then the empty list is returned.

The function <code class="code">AdjacencyMatrix</code> returns an immutable list of lists, whereas the function <code class="code">AdjacencyMatrixMutableCopy</code> returns a copy of <code class="code">AdjacencyMatrix</code> that is a mutable list of mutable lists.

<div class="example"><pre>
gap> gr := Digraph([
> [2, 2, 2], [1, 3, 6, 8, 9, 10], [4, 6, 8],
> [1, 2, 3, 9], [3, 3], [3, 5, 6, 10], [1, 2, 7],
> [1, 2, 3, 10, 5, 6, 10], [1, 3, 4, 5, 8, 10],
> [2, 3, 4, 6, 7, 10]]);
<immutable multidigraph with 10 vertices, 44 edges>
gap> mat := AdjacencyMatrix(gr);;
gap> Display(mat);
[ [ 0, 3, 0, 0, 0, 0, 0, 0, 0, 0 ],
 [ 1, 0, 1, 0, 0, 1, 0, 1, 1, 1 ],
 [ 0, 0, 0, 1, 0, 1, 0, 1, 0, 0 ],
 [ 1, 1, 1, 0, 0, 0, 0, 0, 1, 0 ],
 [ 0, 0, 2, 0, 0, 0, 0, 0, 0, 0 ],
 [ 0, 0, 1, 0, 1, 1, 0, 0, 0, 1 ],
 [ 1, 1, 0, 0, 0, 0, 1, 0, 0, 0 ],
 [ 1, 1, 1, 0, 1, 1, 0, 0, 0, 2 ],
 [ 1, 0, 1, 1, 1, 0, 0, 1, 0, 1 ],
 [ 0, 1, 1, 1, 0, 1, 1, 0, 0, 1 ] ]
gap> D := CycleDigraph(IsMutableDigraph, 3);
<mutable digraph with 3 vertices, 3 edges>
gap> Display(AdjacencyMatrix(D));
[ [ 0, 1, 0 ],
 [ 0, 0, 1 ],
 [ 1, 0, 0 ] ]
</pre></div>

<a id="X87FA0A727CDB060B" name="X87FA0A727CDB060B"></a>

<h5>5.2-2 CharacteristicPolynomial</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ CharacteristicPolynomial</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
Returns: A polynomial with integer coefficients.

This function returns the characteristic polynomial of the digraph <var class="Arg">digraph</var>. That is it returns the characteristic polynomial of the adjacency matrix of the digraph <var class="Arg">digraph</var>

<div class="example"><pre>
gap> D := Digraph([
> [2, 2, 2], [1, 3, 6, 8, 9, 10], [4, 6, 8],
> [1, 2, 3, 9], [3, 3], [3, 5, 6, 10], [1, 2, 7],
> [1, 2, 3, 10, 5, 6, 10], [1, 3, 4, 5, 8, 10],
> [2, 3, 4, 6, 7, 10]]);
<immutable multidigraph with 10 vertices, 44 edges>
gap> CharacteristicPolynomial(D);
x_1^10-3*x_1^9-7*x_1^8-x_1^7+14*x_1^6+x_1^5-26*x_1^4+51*x_1^3-10*x_1^2\
+18*x_1-30
gap> D := CompleteDigraph(5);
<immutable complete digraph with 5 vertices>
gap> CharacteristicPolynomial(D);
x_1^5-10*x_1^3-20*x_1^2-15*x_1-4
gap> D := CycleDigraph(IsMutableDigraph, 3);
<mutable digraph with 3 vertices, 3 edges>
gap> CharacteristicPolynomial(D);
x_1^3-1
</pre></div>

<a id="X8507DC4F794780C1" name="X8507DC4F794780C1"></a>

<h5>5.2-3 BooleanAdjacencyMatrix</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ BooleanAdjacencyMatrix</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ BooleanAdjacencyMatrixMutableCopy</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( operation )</td></tr></table></div>
Returns: A square matrix of booleans.

If <var class="Arg">digraph</var> is a digraph with a positive number of vertices <code class="code">n</code>, then <code class="code">BooleanAdjacencyMatrix(</code><var class="Arg">digraph</var><code class="code">)</code> returns the boolean adjacency matrix <code class="code">mat</code> of <var class="Arg">digraph</var>. The value of the matrix entry <code class="code">mat[j][i]</code> is <code class="keyw">true</code> if and only if there exists an edge in <var class="Arg">digraph</var> with source <code class="code">j</code> and range <code class="code">i</code>. If <var class="Arg">digraph</var> has no vertices, then the empty list is returned.

Note that the boolean adjacency matrix loses information about multiple edges.

The attribute <code class="code">BooleanAdjacencyMatrix</code> returns an immutable list of immutable lists, whereas the function <code class="code">BooleanAdjacencyMatrixMutableCopy</code> returns a copy of the <code class="code">BooleanAdjacencyMatrix</code> that is a mutable list of mutable lists.

<div class="example"><pre>
gap> gr := Digraph([[3, 4], [2, 3], [1, 2, 4], [4]]);
<immutable digraph with 4 vertices, 8 edges>
gap> PrintArray(BooleanAdjacencyMatrix(gr));
[ [ false, false, true, true ],
 [ false, true, true, false ],
 [ true, true, false, true ],
 [ false, false, false, true ] ]
gap> gr := CycleDigraph(4);;
gap> PrintArray(BooleanAdjacencyMatrix(gr));
[ [ false, true, false, false ],
 [ false, false, true, false ],
 [ false, false, false, true ],
 [ true, false, false, false ] ]
gap> BooleanAdjacencyMatrix(EmptyDigraph(0));
[ ]
gap> D := CycleDigraph(IsMutableDigraph, 3);
<mutable digraph with 3 vertices, 3 edges>
gap> PrintArray(BooleanAdjacencyMatrix(D));
[ [ false, true, false ],
 [ false, false, true ],
 [ true, false, false ] ]
</pre></div>

<a id="X7AFCE34A7A04D5C1" name="X7AFCE34A7A04D5C1"></a>

<h5>5.2-4 DigraphAdjacencyFunction</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DigraphAdjacencyFunction</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
Returns: A function.

If <var class="Arg">digraph</var> is a digraph, then <code class="code">DigraphAdjacencyFunction</code> returns a function which takes two integer parameters <code class="code">x, y</code> and returns <code class="keyw">true</code> if there exists an edge from vertex <code class="code">x</code> to vertex <code class="code">y</code> in <var class="Arg">digraph</var> and <code class="keyw">false</code> if not.

<div class="example"><pre>
gap> digraph := Digraph([[1, 2], [3], []]);
<immutable digraph with 3 vertices, 3 edges>
gap> foo := DigraphAdjacencyFunction(digraph);
function( u, v ) ... end
gap> foo(1, 1);
true
gap> foo(1, 2);
true
gap> foo(1, 3);
false
gap> foo(3, 1);
false
gap> gr := Digraph(["a", "b", "c"],
> ["a", "b", "b"],
> ["b", "a", "a"]);
<immutable multidigraph with 3 vertices, 3 edges>
gap> foo := DigraphAdjacencyFunction(gr);
function( u, v ) ... end
gap> foo(1, 2);
true
gap> foo(3, 2);
false
gap> foo(3, 1);
false
gap> D := CycleDigraph(IsMutableDigraph, 3);
<mutable digraph with 3 vertices, 3 edges>
gap> foo := DigraphAdjacencyFunction(D);
function( u, v ) ... end
gap> foo(1, 2);
true
gap> foo(2, 1);
false
</pre></div>

<a id="X7FDEBF3279759961" name="X7FDEBF3279759961"></a>

<h5>5.2-5 DigraphRange</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DigraphRange</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DigraphSource</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
Returns: A list of positive integers.

<code class="code">DigraphRange</code> and <code class="code">DigraphSource</code> return the range and source of the digraph <var class="Arg">digraph</var>. More precisely, position <code class="code">i</code> in <code class="code">DigraphSource(<var class="Arg">digraph</var>)</code> and <code class="code">DigraphRange(<var class="Arg">digraph</var>)</code> give, respectively, the source and range of the <code class="code">i</code>th edge of <var class="Arg">digraph</var>.

<div class="example"><pre>
gap> gr := Digraph([
> [2, 1, 3, 5], [1, 3, 4], [2, 3], [2], [1, 2, 3, 4]]);
<immutable digraph with 5 vertices, 14 edges>
gap> DigraphSource(gr);
[ 1, 1, 1, 1, 2, 2, 2, 3, 3, 4, 5, 5, 5, 5 ]
gap> DigraphRange(gr);
[ 2, 1, 3, 5, 1, 3, 4, 2, 3, 2, 1, 2, 3, 4 ]
gap> DigraphEdges(gr);
[ [ 1, 2 ], [ 1, 1 ], [ 1, 3 ], [ 1, 5 ], [ 2, 1 ], [ 2, 3 ],
 [ 2, 4 ], [ 3, 2 ], [ 3, 3 ], [ 4, 2 ], [ 5, 1 ], [ 5, 2 ],
 [ 5, 3 ], [ 5, 4 ] ]
gap> D := CycleDigraph(IsMutableDigraph, 3);
<mutable digraph with 3 vertices, 3 edges>
gap> DigraphRange(D);
[ 2, 3, 1 ]
gap> DigraphSource(D);
[ 1, 2, 3 ]
</pre></div>

<a id="X7E9880767AE68E00" name="X7E9880767AE68E00"></a>

<h5>5.2-6 OutNeighbours</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ OutNeighbours</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ OutNeighbors</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ OutNeighboursMutableCopy</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ OutNeighborsMutableCopy</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( operation )</td></tr></table></div>
Returns: The adjacencies of a digraph.

<code class="code">OutNeighbours</code> returns the list <code class="code">out</code> of out-neighbours of each vertex of the digraph <var class="Arg">digraph</var>. More specifically, a vertex <code class="code">j</code> appears in <code class="code">out[i]</code> each time there exists the edge <code class="code">[i, j]</code> in <var class="Arg">digraph</var>.

The function <code class="code">OutNeighbours</code> returns an immutable list of lists, whereas the function <code class="code">OutNeighboursMutableCopy</code> returns a copy of <code class="code">OutNeighbours</code> which is a mutable list of mutable lists.

Note that the entries of <code class="code">out</code> are not guaranteed to be sorted in any particular order.

<div class="example"><pre>
gap> gr := Digraph(["a", "b", "c"],
> ["a", "b", "b"],
> ["b", "a", "c"]);
<immutable digraph with 3 vertices, 3 edges>
gap> OutNeighbours(gr);
[ [ 2 ], [ 1, 3 ], [ ] ]
gap> gr := Digraph([[1, 2, 3], [2, 1], [3]]);
<immutable digraph with 3 vertices, 6 edges>
gap> OutNeighbours(gr);
[ [ 1, 2, 3 ], [ 2, 1 ], [ 3 ] ]
gap> gr := DigraphByAdjacencyMatrix([
> [1, 2, 1],
> [1, 1, 0],
> [0, 0, 1]]);
<immutable multidigraph with 3 vertices, 7 edges>
gap> OutNeighbours(gr);
[ [ 1, 2, 2, 3 ], [ 1, 2 ], [ 3 ] ]
gap> OutNeighboursMutableCopy(gr);
[ [ 1, 2, 2, 3 ], [ 1, 2 ], [ 3 ] ]
gap> D := CycleDigraph(IsMutableDigraph, 3);
<mutable digraph with 3 vertices, 3 edges>
gap> OutNeighbours(D);
[ [ 2 ], [ 3 ], [ 1 ] ]
</pre></div>

<a id="X85C7AA5A81DA6E11" name="X85C7AA5A81DA6E11"></a>

<h5>5.2-7 InNeighbours</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ InNeighbours</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ InNeighbors</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ InNeighboursMutableCopy</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ InNeighborsMutableCopy</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( operation )</td></tr></table></div>
Returns: A list of lists of vertices.

<code class="code">InNeighbours</code> returns the list <code class="code">inn</code> of in-neighbours of each vertex of the digraph <var class="Arg">digraph</var>. More specifically, a vertex <code class="code">j</code> appears in <code class="code">inn[i]</code> each time there exists an edge <code class="code">[j,i]</code> in <var class="Arg">digraph</var>.

The function <code class="code">InNeighbours</code> returns an immutable list of lists, whereas the function <code class="code">InNeighboursMutableCopy</code> returns a copy of <code class="code">InNeighbours</code> which is a mutable list of mutable lists.

Note that the entries of <code class="code">inn</code> are not necessarily sorted into ascending order, particularly if <var class="Arg">digraph</var> was constructed via <code class="func">DigraphByInNeighbours</code> (<a href="chap3_mj.html#X81BC49B57EAADEFB">3.1-11</a>).

<div class="example"><pre>
gap> gr := Digraph(["a", "b", "c"],
> ["a", "b", "b"],
> ["b", "a", "c"]);
<immutable digraph with 3 vertices, 3 edges>
gap> InNeighbours(gr);
[ [ 2 ], [ 1 ], [ 2 ] ]
gap> gr := Digraph([[1, 2, 3], [2, 1], [3]]);
<immutable digraph with 3 vertices, 6 edges>
gap> InNeighbours(gr);
[ [ 1, 2 ], [ 1, 2 ], [ 1, 3 ] ]
gap> gr := DigraphByAdjacencyMatrix([
> [1, 2, 1],
> [1, 1, 0],
> [0, 0, 1]]);
<immutable multidigraph with 3 vertices, 7 edges>
gap> InNeighbours(gr);
[ [ 1, 2 ], [ 1, 1, 2 ], [ 1, 3 ] ]
gap> InNeighboursMutableCopy(gr);
[ [ 1, 2 ], [ 1, 1, 2 ], [ 1, 3 ] ]
gap> D := CycleDigraph(IsMutableDigraph, 3);
<mutable digraph with 3 vertices, 3 edges>
gap> InNeighbours(D);
[ [ 3 ], [ 1 ], [ 2 ] ]
</pre></div>

<a id="X7F5ACE807D1BC2E2" name="X7F5ACE807D1BC2E2"></a>

<h5>5.2-8 OutDegrees</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ OutDegrees</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ OutDegreeSequence</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ OutDegreeSet</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
Returns: A list of non-negative integers.

Given a digraph <var class="Arg">digraph</var> with \(n\) vertices, the function <code class="code">OutDegrees</code> returns an immutable list <code class="code">out</code> of length \(n\), such that for a vertex <code class="code">i</code> in <var class="Arg">digraph</var>, the value of <code class="code">out[i]</code> is the out-degree of vertex <code class="code">i</code>. See <code class="func">OutDegreeOfVertex</code> (<a href="chap5_mj.html#X7A09EB648070276D">5.2-10</a>).

The function <code class="code">OutDegreeSequence</code> returns the same list, after it has been sorted into non-increasing order.

The function <code class="code">OutDegreeSet</code> returns the same list, sorted into increasing order with duplicate entries removed.

<div class="example"><pre>
gap> D := Digraph([[1, 3, 2, 2], [], [2, 1], []]);
<immutable multidigraph with 4 vertices, 6 edges>
gap> OutDegrees(D);
[ 4, 0, 2, 0 ]
gap> OutDegreeSequence(D);
[ 4, 2, 0, 0 ]
gap> OutDegreeSet(D);
[ 0, 2, 4 ]
gap> D := CycleDigraph(IsMutableDigraph, 3);
<mutable digraph with 3 vertices, 3 edges>
gap> OutDegrees(D);
[ 1, 1, 1 ]
</pre></div>

<a id="X7ADDFBFD7A365775" name="X7ADDFBFD7A365775"></a>

<h5>5.2-9 InDegrees</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ InDegrees</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ InDegreeSequence</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ InDegreeSet</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
Returns: A list of non-negative integers.

Given a digraph <var class="Arg">digraph</var> with \(n\) vertices, the function <code class="code">InDegrees</code> returns an immutable list <code class="code">inn</code> of length \(n\), such that for a vertex <code class="code">i</code> in <var class="Arg">digraph</var>, the value of <code class="code">inn[i]</code> is the in-degree of vertex <code class="code">i</code>. See <code class="func">InDegreeOfVertex</code> (<a href="chap5_mj.html#X7C9CD0527CB9E6EF">5.2-12</a>).

The function <code class="code">InDegreeSequence</code> returns the same list, after it has been sorted into non-increasing order.

The function <code class="code">InDegreeSet</code> returns the same list, sorted into increasing order with duplicate entries removed.

<div class="example"><pre>
gap> D := Digraph([[1, 3, 2, 2, 4], [], [2, 1, 4], []]);
<immutable multidigraph with 4 vertices, 8 edges>
gap> InDegrees(D);
[ 2, 3, 1, 2 ]
gap> InDegreeSequence(D);
[ 3, 2, 2, 1 ]
gap> InDegreeSet(D);
[ 1, 2, 3 ]
gap> D := CycleDigraph(IsMutableDigraph, 3);
<mutable digraph with 3 vertices, 3 edges>
gap> InDegrees(D);
[ 1, 1, 1 ]
</pre></div>

<a id="X7A09EB648070276D" name="X7A09EB648070276D"></a>

<h5>5.2-10 OutDegreeOfVertex</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ OutDegreeOfVertex</code>( <var class="Arg">digraph</var>, <var class="Arg">vertex</var> )</td><td class="tdright">( operation )</td></tr></table></div>
Returns: The non-negative integer.

This operation returns the out-degree of the vertex <var class="Arg">vertex</var> in the digraph <var class="Arg">digraph</var>. The out-degree of <var class="Arg">vertex</var> is the number of edges in <var class="Arg">digraph</var> whose source is <var class="Arg">vertex</var>.

<div class="example"><pre>
gap> D := Digraph([
> [2, 2, 1], [1, 4], [2, 2, 4, 2], [1, 1, 2, 2, 1, 2, 2]]);
<immutable multidigraph with 4 vertices, 16 edges>
gap> OutDegreeOfVertex(D, 1);
3
gap> OutDegreeOfVertex(D, 2);
2
gap> OutDegreeOfVertex(D, 3);
4
gap> OutDegreeOfVertex(D, 4);
7
</pre></div>

<a id="X83315B0186850806" name="X83315B0186850806"></a>

<h5>5.2-11 OutNeighboursOfVertex</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ OutNeighboursOfVertex</code>( <var class="Arg">digraph</var>, <var class="Arg">vertex</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ OutNeighborsOfVertex</code>( <var class="Arg">digraph</var>, <var class="Arg">vertex</var> )</td><td class="tdright">( operation )</td></tr></table></div>
Returns: A list of vertices.

This operation returns the list <code class="code">out</code> of vertices of the digraph <var class="Arg">digraph</var>. A vertex <code class="code">i</code> appears in the list <code class="code">out</code> each time there exists an edge with source <var class="Arg">vertex</var> and range <code class="code">i</code> in <var class="Arg">digraph</var>; in particular, this means that <code class="code">out</code> may contain duplicates.

<div class="example"><pre>
gap> D := Digraph([
> [2, 2, 3], [1, 3, 4], [2, 2, 3], [1, 1, 2, 2, 1, 2, 2]]);
<immutable multidigraph with 4 vertices, 16 edges>
gap> OutNeighboursOfVertex(D, 1);
[ 2, 2, 3 ]
gap> OutNeighboursOfVertex(D, 3);
[ 2, 2, 3 ]
</pre></div>

<a id="X7C9CD0527CB9E6EF" name="X7C9CD0527CB9E6EF"></a>

<h5>5.2-12 InDegreeOfVertex</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ InDegreeOfVertex</code>( <var class="Arg">digraph</var>, <var class="Arg">vertex</var> )</td><td class="tdright">( operation )</td></tr></table></div>
Returns: A non-negative integer.

This operation returns the in-degree of the vertex <var class="Arg">vertex</var> in the digraph <var class="Arg">digraph</var>. The in-degree of <var class="Arg">vertex</var> is the number of edges in <var class="Arg">digraph</var> whose range is <var class="Arg">vertex</var>.

<div class="example"><pre>
gap> D := Digraph([
> [2, 2, 1], [1, 4], [2, 2, 4, 2], [1, 1, 2, 2, 1, 2, 2]]);
<immutable multidigraph with 4 vertices, 16 edges>
gap> InDegreeOfVertex(D, 1);
5
gap> InDegreeOfVertex(D, 2);
9
gap> InDegreeOfVertex(D, 3);
0
gap> InDegreeOfVertex(D, 4);
2
</pre></div>

<a id="X7C0DA18B8291F302" name="X7C0DA18B8291F302"></a>

<h5>5.2-13 InNeighboursOfVertex</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ InNeighboursOfVertex</code>( <var class="Arg">digraph</var>, <var class="Arg">vertex</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ InNeighborsOfVertex</code>( <var class="Arg">digraph</var>, <var class="Arg">vertex</var> )</td><td class="tdright">( operation )</td></tr></table></div>
Returns: A list of positive vertices.

This operation returns the list <code class="code">inn</code> of vertices of the digraph <var class="Arg">digraph</var>. A vertex <code class="code">i</code> appears in the list <code class="code">inn</code> each time there exists an edge with source <code class="code">i</code> and range <var class="Arg">vertex</var> in <var class="Arg">digraph</var>; in particular, this means that <code class="code">inn</code> may contain duplicates.

<div class="example"><pre>
gap> D := Digraph([
> [2, 2, 3], [1, 3, 4], [2, 2, 3], [1, 1, 2, 2, 1, 2, 2]]);
<immutable multidigraph with 4 vertices, 16 edges>
gap> InNeighboursOfVertex(D, 1);
[ 2, 4, 4, 4 ]
gap> InNeighboursOfVertex(D, 2);
[ 1, 1, 3, 3, 4, 4, 4, 4 ]
</pre></div>

<a id="X83271F607BD809CF" name="X83271F607BD809CF"></a>

<h5>5.2-14 DigraphLoops</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DigraphLoops</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
Returns: A list of vertices.

If <var class="Arg">digraph</var> is a digraph, then <code class="code">DigraphLoops</code> returns the list consisting of the <code class="func">DigraphVertices</code> (<a href="chap5_mj.html#X7C45F7D878D896AC">5.1-1</a>) of <var class="Arg">digraph</var> at which there is a loop. See <code class="func">DigraphHasLoops</code> (<a href="chap6_mj.html#X7D92935C7D535187">6.2-1</a>).

<div class="example"><pre>
gap> D := Digraph([[2], [3], []]);
<immutable digraph with 3 vertices, 2 edges>
gap> DigraphHasLoops(D);
false
gap> DigraphLoops(D);
[ ]
gap> D := Digraph([[3, 5], [1], [2, 4, 3], [4], [2, 1]]);
<immutable digraph with 5 vertices, 9 edges>
gap> DigraphLoops(D);
[ 3, 4 ]
gap> D := Digraph(IsMutableDigraph, [[1], [1]]);
<mutable digraph with 2 vertices, 2 edges>
gap> DigraphLoops(D);
[ 1 ]
</pre></div>

<a id="X7BEAE1C78267F54D" name="X7BEAE1C78267F54D"></a>

<h5>5.2-15 DegreeMatrix</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DegreeMatrix</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
Returns: A square matrix of non-negative integers.

Returns the out-degree matrix <code class="code">mat</code> of the digraph <var class="Arg">digraph</var>. The value of the <code class="code">i</code>th diagonal matrix entry is the out-degree of the vertex <code class="code">i</code> in <var class="Arg">digraph</var>. All off-diagonal entries are <code class="code">0</code>. If <var class="Arg">digraph</var> has no vertices, then the empty list is returned.

See <code class="func">OutDegrees</code> (<a href="chap5_mj.html#X7F5ACE807D1BC2E2">5.2-8</a>) for more information.

<div class="example"><pre>
gap> D := Digraph([[1, 2, 3], [4], [1, 3, 4], []]);
<immutable digraph with 4 vertices, 7 edges>
gap> PrintArray(DegreeMatrix(D));
[ [ 3, 0, 0, 0 ],
 [ 0, 1, 0, 0 ],
 [ 0, 0, 3, 0 ],
 [ 0, 0, 0, 0 ] ]
gap> D := CycleDigraph(5);;
gap> PrintArray(DegreeMatrix(D));
[ [ 1, 0, 0, 0, 0 ],
 [ 0, 1, 0, 0, 0 ],
 [ 0, 0, 1, 0, 0 ],
 [ 0, 0, 0, 1, 0 ],
 [ 0, 0, 0, 0, 1 ] ]
gap> DegreeMatrix(EmptyDigraph(0));
[ ]
gap> D := CycleDigraph(IsMutableDigraph, 3);
<mutable digraph with 3 vertices, 3 edges>
gap> Display(DegreeMatrix(D));
[ [ 1, 0, 0 ],
 [ 0, 1, 0 ],
 [ 0, 0, 1 ] ]
</pre></div>

<a id="X865390B08331936B" name="X865390B08331936B"></a>

<h5>5.2-16 LaplacianMatrix</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ LaplacianMatrix</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
Returns: A square matrix of integers.

Returns the out-degree Laplacian matrix <code class="code">mat</code> of the digraph <var class="Arg">digraph</var>. The out-degree Laplacian matrix is defined as <code class="code">DegreeMatrix(digraph) - AdjacencyMatrix(digraph)</code>. If <var class="Arg">digraph</var> has no vertices, then the empty list is returned.

See <code class="func">DegreeMatrix</code> (<a href="chap5_mj.html#X7BEAE1C78267F54D">5.2-15</a>) and <code class="func">AdjacencyMatrix</code> (<a href="chap5_mj.html#X7DC2CD70830BEE60">5.2-1</a>) for more information.

<div class="example"><pre>
gap> gr := Digraph([[1, 2, 3], [4], [1, 3, 4], []]);
<immutable digraph with 4 vertices, 7 edges>
gap> PrintArray(LaplacianMatrix(gr));
[ [ 2, -1, -1, 0 ],
 [ 0, 1, 0, -1 ],
 [ -1, 0, 2, -1 ],
 [ 0, 0, 0, 0 ] ]
gap> LaplacianMatrix(EmptyDigraph(0));
[ ]
gap> D := CycleDigraph(IsMutableDigraph, 3);
<mutable digraph with 3 vertices, 3 edges>
gap> Display(LaplacianMatrix(D));
[ [ 1, -1, 0 ],
 [ 0, 1, -1 ],
 [ -1, 0, 1 ] ]
</pre></div>

<a id="X86424F167BD4F629" name="X86424F167BD4F629"></a>

<h4>5.3 Orders</h4>

<a id="X7DDB33B686B3A2C6" name="X7DDB33B686B3A2C6"></a>

<h5>5.3-1 PartialOrderDigraphMeetOfVertices</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ PartialOrderDigraphMeetOfVertices</code>( <var class="Arg">digraph</var>, <var class="Arg">u</var>, <var class="Arg">v</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ PartialOrderDigraphJoinOfVertices</code>( <var class="Arg">digraph</var>, <var class="Arg">u</var>, <var class="Arg">v</var> )</td><td class="tdright">( operation )</td></tr></table></div>
Returns: A positive integer or <code class="keyw">fail</code>

If the first argument is a partial order digraph <code class="func">IsPartialOrderDigraph</code> (<a href="chap6_mj.html#X82BAE6D37D49A145">6.4-2</a>) then these operations return the meet, or the join, of the two input vertices. If the meet (or join) is does not exist then <code class="keyw">fail</code> is returned. The meet (or join) is guaranteed to exist when the first argument satisfies <code class="func">IsMeetSemilatticeDigraph</code> (<a href="chap6_mj.html#X78D3E17B7F737516">6.4-3</a>) (or <code class="func">IsJoinSemilatticeDigraph</code> (<a href="chap6_mj.html#X78D3E17B7F737516">6.4-3</a>)) - see the documentation for these properties for the definition of the meet (or the join).

<div class="example"><pre>
gap> D := Digraph([[1], [1, 2], [1, 3], [1, 2, 3, 4]]);
<immutable digraph with 4 vertices, 9 edges>
gap> PartialOrderDigraphMeetOfVertices(D, 2, 3);
4
gap> PartialOrderDigraphJoinOfVertices(D, 2, 3);
1
gap> PartialOrderDigraphMeetOfVertices(D, 1, 2);
2
gap> PartialOrderDigraphJoinOfVertices(D, 3, 4);
3
gap> D := Digraph([[1], [2], [1, 2, 3], [1, 2, 4]]);
<immutable digraph with 4 vertices, 8 edges>
gap> PartialOrderDigraphMeetOfVertices(D, 3, 4);
fail
gap> PartialOrderDigraphJoinOfVertices(D, 3, 4);
fail
gap> PartialOrderDigraphMeetOfVertices(D, 1, 2);
fail
gap> PartialOrderDigraphJoinOfVertices(D, 1, 2);
fail
</pre></div>

<a id="X824B9896798530F6" name="X824B9896798530F6"></a>

<h5>5.3-2 NonUpperSemimodularPair</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ NonUpperSemimodularPair</code>( <var class="Arg">D</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ NonLowerSemimodularPair</code>( <var class="Arg">D</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
Returns: A pair of vertices or <code class="keyw">fail</code>.

<code class="code">NonUpperSemimodularPair</code> returns a pair of vertices in the digraph <var class="Arg">D</var> that witnesses the fact that <var class="Arg">D</var> does not represent an upper semimodular lattice, if such a pair exists.

If the digraph <var class="Arg">D</var> does not satisfy <code class="func">IsLatticeDigraph</code> (<a href="chap6_mj.html#X78D3E17B7F737516">6.4-3</a>), then an error is given. Otherwise if the digraph <var class="Arg">D</var> does satisfy <code class="func">IsLatticeDigraph</code> (<a href="chap6_mj.html#X78D3E17B7F737516">6.4-3</a>), then either a non-upper semimodular pair of vertices is returned, or <code class="keyw">fail</code> is returned if no such pair exists (meaning that <var class="Arg">D</var> is an upper semimodular lattice.

<code class="code">NonLowerSemimodularPair</code> behaves in the analogous way to <code class="code">NonUpperSemimodularPair</code> with respect to lower semimodularity.

See <code class="func">IsUpperSemimodularDigraph</code> (<a href="chap6_mj.html#X7DEDCD177E5AE824">6.4-7</a>) and <code class="func">IsLowerSemimodularDigraph</code> (<a href="chap6_mj.html#X7DEDCD177E5AE824">6.4-7</a>) for the definition of upper semimodularity of a lattice.

<div class="example"><pre>
gap> D := DigraphFromDigraph6String(
> "&M~~sc`lYUZO__KIBboC_@h?U_?_GL?A_?c");
<immutable digraph with 14 vertices, 66 edges>
gap> NonLowerSemimodularPair(D);
[ 10, 9 ]
gap> NonUpperSemimodularPair(D);
fail
</pre></div>

<a id="X8537F4088400DC48" name="X8537F4088400DC48"></a>

<h4>5.4 Reachability and connectivity</h4>

<a id="X7F16B9EB8398459C" name="X7F16B9EB8398459C"></a>

<h5>5.4-1 DigraphDiameter</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DigraphDiameter</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
Returns: An integer or <code class="code">fail</code>.

This function returns the diameter of the digraph <var class="Arg">digraph</var>.

If a digraph <var class="Arg">digraph</var> is strongly connected and has at least 1 vertex, then the diameter is the maximum shortest distance between any pair of distinct vertices. Otherwise then the diameter of <var class="Arg">digraph</var> is undefined, and this function returns the value <code class="code">fail</code>.

See <code class="func">DigraphShortestDistances</code> (<a href="chap5_mj.html#X81F99BC67E9D050F">5.4-3</a>).

<div class="example"><pre>
gap> D := Digraph([[2], [3], [4, 5], [5], [1, 2, 3, 4, 5]]);
<immutable digraph with 5 vertices, 10 edges>
gap> DigraphDiameter(D);
3
gap> D := ChainDigraph(2);
<immutable chain digraph with 2 vertices>
gap> DigraphDiameter(D);
fail
gap> IsStronglyConnectedDigraph(D);
false
gap> D := GeneralisedPetersenGraph(IsMutableDigraph, 6, 2);
<mutable digraph with 12 vertices, 36 edges>
gap> DigraphDiameter(D);
4
</pre></div>

<a id="X8104A9D37BCD8A05" name="X8104A9D37BCD8A05"></a>

<h5>5.4-2 DigraphShortestDistance</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DigraphShortestDistance</code>( <var class="Arg">digraph</var>, <var class="Arg">u</var>, <var class="Arg">v</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DigraphShortestDistance</code>( <var class="Arg">digraph</var>, <var class="Arg">list</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DigraphShortestDistance</code>( <var class="Arg">digraph</var>, <var class="Arg">list1</var>, <var class="Arg">list2</var> )</td><td class="tdright">( operation )</td></tr></table></div>
Returns: An integer or <code class="keyw">fail</code>

If there is a directed path in the digraph <var class="Arg">digraph</var> between vertex <var class="Arg">u</var> and vertex <var class="Arg">v</var>, then this operation returns the length of the shortest such directed path. If no such directed path exists, then this operation returns <code class="keyw">fail</code>. See Section <a href="chap1_mj.html#X84541F61810C741D">1.1-1</a> for the definition of a directed path.

If the second form is used, then <var class="Arg">list</var> should be a list of length two, containing two positive integers which correspond to the vertices <var class="Arg">u</var> and <var class="Arg">v</var>.

Note that as usual, a vertex is considered to be at distance 0 from itself .

If the third form is used, then <var class="Arg">list1</var> and <var class="Arg">list2</var> are both lists of vertices. The shortest directed path between <var class="Arg">list1</var> and <var class="Arg">list2</var> is then the length of the shortest directed path which starts with a vertex in <var class="Arg">list1</var> and terminates at a vertex in <var class="Arg">list2</var>, if such directed path exists. If <var class="Arg">list1</var> and <var class="Arg">list2</var> have non-empty intersection, the operation returns <code class="code">0</code>.

<div class="example"><pre>
gap> D := Digraph([[2], [3], [1, 4], [1, 3], [5]]);
<immutable digraph with 5 vertices, 7 edges>
gap> DigraphShortestDistance(D, 1, 3);
2
gap> DigraphShortestDistance(D, [3, 3]);
0
gap> DigraphShortestDistance(D, 5, 2);
fail
gap> DigraphShortestDistance(D, [1, 2], [4, 5]);
2
gap> DigraphShortestDistance(D, [1, 3], [3, 5]);
0
</pre></div>

<a id="X81F99BC67E9D050F" name="X81F99BC67E9D050F"></a>

<h5>5.4-3 DigraphShortestDistances</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DigraphShortestDistances</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
Returns: A square matrix.

If <var class="Arg">digraph</var> is a digraph with \(n\) vertices, then this function returns an \(n \times n\) matrix <code class="code">mat</code>, where each entry is either a non-negative integer, or <code class="keyw">fail</code>. If \(n = 0\), then an empty list is returned.

If there is a directed path from vertex <code class="code">i</code> to vertex <code class="code">j</code>, then the value of <code class="code">mat[i][j]</code> is the length of the shortest such directed path. If no such directed path exists, then the value of <code class="code">mat[i][j]</code> is <code class="code">fail</code>. We use the convention that the distance from every vertex to itself is <code class="code">0</code>, i.e. <code class="code">mat[i][i] = 0</code> for all vertices <code class="code">i</code>.

The method used in this function is a version of the Floyd-Warshall algorithm, and has complexity \(O(n^3)\).

<div class="example"><pre>
gap> D := Digraph([[1, 2], [3], [1, 2], [4]]);
<immutable digraph with 4 vertices, 6 edges>
gap> mat := DigraphShortestDistances(D);;
gap> PrintArray(mat);
[ [ 0, 1, 2, fail ],
 [ 2, 0, 1, fail ],
 [ 1, 1, 0, fail ],
 [ fail, fail, fail, 0 ] ]
gap> D := CycleDigraph(IsMutableDigraph, 3);
<mutable digraph with 3 vertices, 3 edges>
gap> DigraphShortestDistances(D);
[ [ 0, 1, 2 ], [ 2, 0, 1 ], [ 1, 2, 0 ] ]
</pre></div>

<a id="X8223718079D98A82" name="X8223718079D98A82"></a>

<h5>5.4-4 DigraphLongestDistanceFromVertex</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DigraphLongestDistanceFromVertex</code>( <var class="Arg">digraph</var>, <var class="Arg">v</var> )</td><td class="tdright">( operation )</td></tr></table></div>
Returns: An integer, or <code class="keyw">infinity</code>.

If <var class="Arg">digraph</var> is a digraph and <var class="Arg">v</var> is a vertex in <var class="Arg">digraph</var>, then this operation returns the length of the longest directed walk in <var class="Arg">digraph</var> which begins at vertex <var class="Arg">v</var>. See Section <a href="chap1_mj.html#X84541F61810C741D">1.1-1</a> for the definitions of directed walk, directed cycle, and loop.

<ul>
<li>If there exists a directed walk starting at vertex <var class="Arg">v</var> which traverses a loop or a directed cycle, then we consider there to be a walk of infinite length from <var class="Arg">v</var> (realised by repeatedly traversing the loop/directed cycle), and so the result is <code class="keyw">infinity</code>. To disallow walks using loops, try using <code class="func">DigraphRemoveLoops</code> (<a href="chap3_mj.html#X79324AF7818C0C02">3.3-25</a>):

<code class="code">DigraphLongestDistanceFromVertex(DigraphRemoveLoops(<var class="Arg">digraph</var>,<var class="Arg">v</var>))</code>.

</li>
<li>Otherwise, if all directed walks starting at vertex <var class="Arg">v</var> have finite length, then the length of the longest such walk is returned.

</li>
</ul>
Note that the result is <code class="code">0</code> if and only if <var class="Arg">v</var> is a sink of <var class="Arg">digraph</var>. See <code class="func">DigraphSinks</code> (<a href="chap5_mj.html#X85D5E08280914EE4">5.1-8</a>).

<div class="example"><pre>
gap> D := Digraph([[2], [3, 4], [], [5], [], [6]]);
<immutable digraph with 6 vertices, 5 edges>
gap> DigraphLongestDistanceFromVertex(D, 1);
3
gap> DigraphLongestDistanceFromVertex(D, 3);
0
gap> 3 in DigraphSinks(D);
true
gap> DigraphLongestDistanceFromVertex(D, 6);
infinity
</pre></div>

<a id="X7CB7DDCD84621D38" name="X7CB7DDCD84621D38"></a>

<h5>5.4-5 DigraphDistanceSet</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DigraphDistanceSet</code>( <var class="Arg">digraph</var>, <var class="Arg">vertex</var>, <var class="Arg">distance</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DigraphDistanceSet</code>( <var class="Arg">digraph</var>, <var class="Arg">vertex</var>, <var class="Arg">distances</var> )</td><td class="tdright">( operation )</td></tr></table></div>
Returns: A list of vertices

This operation returns the list of all vertices in digraph <var class="Arg">digraph</var> such that the shortest distance to a vertex <var class="Arg">vertex</var> is <var class="Arg">distance</var> or is in the list <var class="Arg">distances</var>.

<var class="Arg">digraph</var> should be a digraph, <var class="Arg">vertex</var> should be a positive integer, <var class="Arg">distance</var> should be a non-negative integer, and <var class="Arg">distances</var> should be a list of non-negative integers.

<div class="example"><pre>
gap> D := Digraph([[2], [3], [1, 4], [1, 3]]);
<immutable digraph with 4 vertices, 6 edges>
gap> DigraphDistanceSet(D, 2, [1, 2]);
[ 3, 1, 4 ]
gap> DigraphDistanceSet(D, 3, 1);
[ 1, 4 ]
gap> DigraphDistanceSet(D, 2, 0);
[ 2 ]
</pre></div>

<a id="X79A3DA4078CF3C90" name="X79A3DA4078CF3C90"></a>

<h5>5.4-6 DigraphGirth</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DigraphGirth</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
Returns: An integer, or <code class="keyw">infinity</code>.

This attribute returns the girth of the digraph <var class="Arg">digraph</var>. The girth of a digraph is the length of its shortest simple circuit. See Section <a href="chap1_mj.html#X84541F61810C741D">1.1-1</a> for the definitions of simple circuit, directed cycle, and loop.

If <var class="Arg">digraph</var> has no directed cycles, then this function will return <code class="keyw">infinity</code>. If <var class="Arg">digraph</var> contains a loop, then this function will return <code class="code">1</code>.

In the worst case, the method used in this function is a version of the Floyd-Warshall algorithm, and has complexity <code class="code">O(<var class="Arg">n</var> ^ 3)</code>, where <var class="Arg">n</var> is the number of vertices in <var class="Arg">digraph</var>. If the digraph has known automorphisms [see <code class="func">DigraphGroup</code> (<a href="chap7_mj.html#X803ACEDA7BBAC5B3">7.2-10</a>)], then the performance is likely to be better.

For symmetric digraphs, see also <code class="func">DigraphUndirectedGirth</code> (<a href="chap5_mj.html#X84688B337BDDBB09">5.4-8</a>).

<div class="example"><pre>
gap> D := Digraph([[1], [1]]);
<immutable digraph with 2 vertices, 2 edges>
gap> DigraphGirth(D);
1
gap> D := Digraph([[2, 3], [3], [4], []]);
<immutable digraph with 4 vertices, 4 edges>
gap> DigraphGirth(D);
infinity
gap> D := Digraph([[2, 3], [3], [4], [1]]);
<immutable digraph with 4 vertices, 5 edges>
gap> DigraphGirth(D);
3
gap> D := GeneralisedPetersenGraph(IsMutableDigraph, 6, 2);
<mutable digraph with 12 vertices, 36 edges>
gap> DigraphGirth(D);
2
</pre></div>

<a id="X8374B7357EC189C1" name="X8374B7357EC189C1"></a>

<h5>5.4-7 DigraphOddGirth</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DigraphOddGirth</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
Returns: An integer, or <code class="keyw">infinity</code>.

This attribute returns the odd girth of the digraph <var class="Arg">digraph</var>. The odd girth of a digraph is the length of its shortest simple circuit of odd length. See Section <a href="chap1_mj.html#X84541F61810C741D">1.1-1</a> for the definitions of simple circuit, directed cycle, and loop.

If <var class="Arg">digraph</var> has no directed cycles of odd length, then this function will return <code class="keyw">infinity</code>, even if <var class="Arg">digraph</var> has a directed cycle of even length. If <var class="Arg">digraph</var> contains a loop, then this function will return <code class="code">1</code>.

See also <code class="func">DigraphGirth</code> (<a href="chap5_mj.html#X79A3DA4078CF3C90">5.4-6</a>).

<div class="example"><pre>
gap> D := Digraph([[2], [3, 1], [1]]);
<immutable digraph with 3 vertices, 4 edges>
gap> DigraphOddGirth(D);
3
gap> D := CycleDigraph(4);
<immutable cycle digraph with 4 vertices>
gap> DigraphOddGirth(D);
infinity
gap> D := Digraph([[2], [3], [], [3], [4]]);
<immutable digraph with 5 vertices, 4 edges>
gap> DigraphOddGirth(D);
infinity
gap> D := CycleDigraph(IsMutableDigraph, 4);
<mutable digraph with 4 vertices, 4 edges>
gap> DigraphDisjointUnion(D, CycleDigraph(5));
<mutable digraph with 9 vertices, 9 edges>
gap> DigraphOddGirth(D);
5
</pre></div>

<a id="X84688B337BDDBB09" name="X84688B337BDDBB09"></a>

<h5>5.4-8 DigraphUndirectedGirth</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DigraphUndirectedGirth</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
Returns: An integer or <code class="keyw">infinity</code>.

If <var class="Arg">digraph</var> is a symmetric digraph, then this function returns the girth of <var class="Arg">digraph</var> when treated as an undirected graph (i.e. each pair of edges \([i, j]\) and \([j, i]\) is treated as a single edge between \(i\) and \(j\)).

The girth of an undirected graph is the length of its shortest simple cycle, i.e. the shortest non-trivial path starting and ending at the same vertex and passing through no vertex or edge more than once.

If <var class="Arg">digraph</var> has no cycles, then this function will return <code class="keyw">infinity</code>.

<div class="example"><pre>
gap> D := Digraph([[2, 4], [1, 3], [2, 4], [1, 3]]);
<immutable digraph with 4 vertices, 8 edges>
gap> DigraphUndirectedGirth(D);
4
gap> D := Digraph([[2], [1, 3], [2]]);
<immutable digraph with 3 vertices, 4 edges>
gap> DigraphUndirectedGirth(D);
infinity
gap> D := Digraph([[1], [], [4], [3]]);
<immutable digraph with 4 vertices, 3 edges>
gap> DigraphUndirectedGirth(D);
1
gap> D := GeneralisedPetersenGraph(IsMutableDigraph, 9, 2);
<mutable digraph with 18 vertices, 54 edges>
gap> DigraphUndirectedGirth(D);
5
</pre></div>

<a id="X842FAD6A7B835977" name="X842FAD6A7B835977"></a>

<h5>5.4-9 DigraphConnectedComponents</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DigraphConnectedComponents</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DigraphNrConnectedComponents</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
Returns: A record.

This function returns the record <code class="code">wcc</code> corresponding to the weakly connected components of the digraph <var class="Arg">digraph</var>. Two vertices of <var class="Arg">digraph</var> are in the same weakly connected component whenever they are equal, or there exists a directed path (ignoring the orientation of edges) between them. More formally, two vertices are in the same weakly connected component of <var class="Arg">digraph</var> if and only if they are in the same strongly connected component (see <code class="func">DigraphStronglyConnectedComponents</code> (<a href="chap5_mj.html#X833ECD6B7A84944C">5.4-11</a>)) of the <code class="func">DigraphSymmetricClosure</code> (<a href="chap3_mj.html#X874883DD7DD450C4">3.3-12</a>) of <var class="Arg">digraph</var>.

The set of weakly connected components is a partition of the vertex set of <var class="Arg">digraph</var>.

The record <code class="code">wcc</code> has 2 components: <code class="code">comps</code> and <code class="code">id</code>. The component <code class="code">comps</code> is a list of the weakly connected components of <var class="Arg">digraph</var> (each of which is a list of vertices). The component <code class="code">id</code> is a list such that the vertex <code class="code">i</code> is an element of the weakly connected component <code class="code">comps[id[i]]</code>.

The method used in this function has complexity \(O(m+n)\), where \(m\) is the number of edges and \(n\) is the number of vertices in the digraph.

<code class="code">DigraphNrConnectedComponents(<var class="Arg">digraph</var>)</code> is simply a shortcut for <code class="code">Length(DigraphConnectedComponents(<var class="Arg">digraph</var>).comps)</code>, and is no more efficient.

<div class="example"><pre>
gap> gr := Digraph([[2], [3, 1], []]);
<immutable digraph with 3 vertices, 3 edges>
gap> DigraphConnectedComponents(gr);
rec( comps := [ [ 1, 2, 3 ] ], id := [ 1, 1, 1 ] )
gap> gr := Digraph([[1], [1, 2], []]);
<immutable digraph with 3 vertices, 3 edges>
gap> DigraphConnectedComponents(gr);
rec( comps := [ [ 1, 2 ], [ 3 ] ], id := [ 1, 1, 2 ] )
gap> DigraphNrConnectedComponents(gr);
2
gap> gr := EmptyDigraph(0);
<immutable empty digraph with 0 vertices>
gap> DigraphConnectedComponents(gr);
rec( comps := [ ], id := [ ] )
gap> D := CycleDigraph(IsMutableDigraph, 2);
<mutable digraph with 2 vertices, 2 edges>
gap> G := CycleDigraph(3);
<immutable cycle digraph with 3 vertices>
gap> DigraphDisjointUnion(D, G);
<mutable digraph with 5 vertices, 5 edges>
gap> DigraphConnectedComponents(D);
rec( comps := [ [ 1, 2 ], [ 3, 4, 5 ] ], id := [ 1, 1, 2, 2, 2 ] )
</pre></div>

<a id="X8484EC557810CD31" name="X8484EC557810CD31"></a>

<h5>5.4-10 DigraphConnectedComponent</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DigraphConnectedComponent</code>( <var class="Arg">digraph</var>, <var class="Arg">vertex</var> )</td><td class="tdright">( operation )</td></tr></table></div>
Returns: A list of vertices.

If <var class="Arg">vertex</var> is a vertex in the digraph <var class="Arg">digraph</var>, then this operation returns the connected component of <var class="Arg">vertex</var> in <var class="Arg">digraph</var>. See <code class="func">DigraphConnectedComponents</code> (<a href="chap5_mj.html#X842FAD6A7B835977">5.4-9</a>) for more information.

<div class="example"><pre>
gap> D := Digraph([[3], [2], [1, 2], [4]]);
<immutable digraph with 4 vertices, 5 edges>
gap> DigraphConnectedComponent(D, 3);
[ 1, 2, 3 ]
gap> DigraphConnectedComponent(D, 2);
[ 1, 2, 3 ]
gap> DigraphConnectedComponent(D, 4);
[ 4 ]
</pre></div>

<a id="X833ECD6B7A84944C" name="X833ECD6B7A84944C"></a>

<h5>5.4-11 DigraphStronglyConnectedComponents</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DigraphStronglyConnectedComponents</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DigraphNrStronglyConnectedComponents</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
Returns: A record.

This function returns the record <code class="code">scc</code> corresponding to the strongly connected components of the digraph <var class="Arg">digraph</var>. Two vertices of <var class="Arg">digraph</var> are in the same strongly connected component whenever they are equal, or there is a directed path from each vertex to the other. The set of strongly connected components is a partition of the vertex set of <var class="Arg">digraph</var>.

The record <code class="code">scc</code> has 2 components: <code class="code">comps</code> and <code class="code">id</code>. The component <code class="code">comps</code> is a list of the strongly connected components of <var class="Arg">digraph</var> (each of which is a list of vertices). The component <code class="code">id</code> is a list such that the vertex <code class="code">i</code> is an element of the strongly connected component <code class="code">comps[id[i]]</code>.

The method used in this function is a non-recursive version of Gabow's Algorithm <a href="chapBib_mj.html#biBGab00">[Gab00]</a> and has complexity \(O(m+n)\) where \(m\) is the number of edges (counting multiple edges as one) and \(n\) is the number of vertices in the digraph.

<code class="code">DigraphNrStronglyConnectedComponents(<var class="Arg">digraph</var>)</code> is simply a shortcut for <code class="code">Length(DigraphStronglyConnectedComponents(<var class="Arg">digraph</var>).comps)</code>, and is no more efficient.

<div class="example"><pre>
gap> gr := Digraph([[2], [3, 1], []]);
<immutable digraph with 3 vertices, 3 edges>
gap> DigraphStronglyConnectedComponents(gr);
rec( comps := [ [ 3 ], [ 1, 2 ] ], id := [ 2, 2, 1 ] )
gap> DigraphNrStronglyConnectedComponents(gr);
2
gap> D := DigraphDisjointUnion(CycleDigraph(4), CycleDigraph(5));
<immutable digraph with 9 vertices, 9 edges>
gap> DigraphStronglyConnectedComponents(D);
rec( comps := [ [ 1, 2, 3, 4 ], [ 5, 6, 7, 8, 9 ] ],
 id := [ 1, 1, 1, 1, 2, 2, 2, 2, 2 ] )
gap> DigraphNrStronglyConnectedComponents(D);
2
gap> D := CycleDigraph(IsMutableDigraph, 2);
<mutable digraph with 2 vertices, 2 edges>
gap> G := CycleDigraph(3);
<immutable cycle digraph with 3 vertices>
gap> DigraphDisjointUnion(D, G);
<mutable digraph with 5 vertices, 5 edges>
gap> DigraphStronglyConnectedComponents(D);
rec( comps := [ [ 1, 2 ], [ 3, 4, 5 ] ], id := [ 1, 1, 2, 2, 2 ] )
</pre></div>

<a id="X7EFCB5017D662254" name="X7EFCB5017D662254"></a>

<h5>5.4-12 DigraphStronglyConnectedComponent</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DigraphStronglyConnectedComponent</code>( <var class="Arg">digraph</var>, <var class="Arg">vertex</var> )</td><td class="tdright">( operation )</td></tr></table></div>
Returns: A list of vertices.

If <var class="Arg">vertex</var> is a vertex in the digraph <var class="Arg">digraph</var>, then this operation returns the strongly connected component of <var class="Arg">vertex</var> in <var class="Arg">digraph</var>. See <code class="func">DigraphStronglyConnectedComponents</code> (<a href="chap5_mj.html#X833ECD6B7A84944C">5.4-11</a>) for more information.

<div class="example"><pre>
gap> D := Digraph([[3], [2], [1, 2], [3]]);
<immutable digraph with 4 vertices, 5 edges>
gap> DigraphStronglyConnectedComponent(D, 3);
[ 1, 3 ]
gap> DigraphStronglyConnectedComponent(D, 2);
[ 2 ]
gap> DigraphStronglyConnectedComponent(D, 4);
[ 4 ]
</pre></div>

<a id="X7F1B5A2782F598B1" name="X7F1B5A2782F598B1"></a>

<h5>5.4-13 DigraphBicomponents</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DigraphBicomponents</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
Returns: A pair of lists of vertices, or <code class="keyw">fail</code>.

If <var class="Arg">digraph</var> is a bipartite digraph, i.e. if it satisfies <code class="func">IsBipartiteDigraph</code> (<a href="chap6_mj.html#X860CFB0C8665F356">6.2-3</a>), then <code class="code">DigraphBicomponents</code> returns a pair of bicomponents of <var class="Arg">digraph</var>. Otherwise, <code class="code">DigraphBicomponents</code> returns <code class="keyw">fail</code>.

For a bipartite digraph, the vertices can be partitioned into two non-empty sets such that the source and range of any edge are in distinct sets. The parts of this partition are called bicomponents of <var class="Arg">digraph</var>. Equivalently, a pair of bicomponents of <var class="Arg">digraph</var> consists of the color-classes of a 2-coloring of <var class="Arg">digraph</var>.

For a bipartite digraph with at least 3 vertices, there is a unique pair of bicomponents of bipartite if and only if the digraph is connected. See <code class="func">IsConnectedDigraph</code> (<a href="chap6_mj.html#X83C08C0B7EC1A91F">6.6-3</a>) for more information.

<div class="example"><pre>
gap> D := CycleDigraph(3);
<immutable cycle digraph with 3 vertices>
gap> DigraphBicomponents(D);
fail
gap> D := ChainDigraph(5);
<immutable chain digraph with 5 vertices>
gap> DigraphBicomponents(D);
[ [ 1, 3, 5 ], [ 2, 4 ] ]
gap> D := Digraph([[5], [1, 4], [5], [5], []]);
<immutable digraph with 5 vertices, 5 edges>
gap> DigraphBicomponents(D);
[ [ 1, 3, 4 ], [ 2, 5 ] ]
gap> D := CompleteBipartiteDigraph(IsMutableDigraph, 2, 3);
<mutable digraph with 5 vertices, 12 edges>
gap> DigraphBicomponents(D);
[ [ 1, 2 ], [ 3, 4, 5 ] ]
</pre></div>

<a id="X7DDE06E47E605DD7" name="X7DDE06E47E605DD7"></a>

<h5>5.4-14 ArticulationPoints</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ ArticulationPoints</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
Returns: A list of vertices.

A connected digraph is biconnected if it is still connected (in the sense of <code class="func">IsConnectedDigraph</code> (<a href="chap6_mj.html#X83C08C0B7EC1A91F">6.6-3</a>)) when any vertex is removed. If the digraph <var class="Arg">digraph</var> is not biconnected but is connected, then any vertex <code class="code">v</code> of <var class="Arg">digraph</var> whose removal makes the resulting digraph disconnected is called an articulation point.

<code class="code">ArticulationPoints</code> returns a list of the articulation points of <var class="Arg">digraph</var>, if any, and, in particular, returns the empty list if <var class="Arg">digraph</var> is not connected.

Multiple edges are ignored by this method.

The method used in this operation has complexity \(O(m+n)\) where \(m\) is the number of edges and \(n\) is the number of vertices in the digraph.

If <var class="Arg">D</var> has a bridge (see <code class="func">Bridges</code> (<a href="chap5_mj.html#X84D5A125848BD800">5.4-16</a>)), then a node incident to the bridge is an articulation point if and only if it has degree at least \(2\). It follows that if <var class="Arg">D</var> has a bridge and at least \(3\) nodes, then at least one of the nodes incident to the bridge is an articulation point. The converse does not hold, there are digraphs with articulation points, but no bridges.

See also <code class="func">IsBiconnectedDigraph</code> (<a href="chap6_mj.html#X838FAF2D825977BE">6.6-4</a>) and <code class="func">IsBridgelessDigraph</code> (<a href="chap6_mj.html#X7D2A6572820B7F24">6.6-5</a>).

<div class="example"><pre>
gap> ArticulationPoints(CycleDigraph(5));
[ ]
gap> D := Digraph([[2, 7], [3, 5], [4], [2], [6], [1], []]);;
gap> ArticulationPoints(D);
[ 1, 2 ]
gap> ArticulationPoints(ChainDigraph(5));
[ 2, 3, 4 ]
gap> ArticulationPoints(NullDigraph(5));
[ ]
gap> D := ChainDigraph(IsMutableDigraph, 4);
<mutable digraph with 4 vertices, 3 edges>
gap> ArticulationPoints(D);
[ 2, 3 ]
</pre></div>

<a id="X803459AB86AB9BE2" name="X803459AB86AB9BE2"></a>

<h5>5.4-15 MinimalCyclicEdgeCut</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ MinimalCyclicEdgeCut</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
Returns: A list of edges or <code class="keyw">fail</code>.

A cyclic edge cut of <var class="Arg">digraph</var> is a set of edges such that deleting these edges results in at least two connected components having a cycle. This method computes the cyclic edge cut with minimal cardinality for cubic graphs with at least 8 vertices. The cyclic edge cut is returned as a list of undirected edges.

If the given digraph is not cubic, not connected, has less than 8 vertices or does not have a cyclic edge cut, the method returns <code class="keyw">fail</code>. Multiple edges of <var class="Arg">digraph</var> are ignored by this method and note that <var class="Arg">digraph</var> is identified as an undirected graph.

The method used in this method has complexity \(O(n^2*log^2(n)) \) where \(n\) is the number of vertices in the digraph.

<div class="example"><pre>
gap> MinimalCyclicEdgeCut(HypercubeGraph(3));
[ [ 1, 5 ], [ 2, 6 ], [ 4, 8 ], [ 3, 7 ] ]
gap> MinimalCyclicEdgeCut(CompleteDigraph(4));
fail
</pre></div>

<a id="X84D5A125848BD800" name="X84D5A125848BD800"></a>

<h5>5.4-16 Bridges</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Bridges</code>( <var class="Arg">D</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
Returns: A (possibly empty) list of edges.

A connected digraph is 2-edge-connected if it is still connected (in the sense of <code class="func">IsConnectedDigraph</code> (<a href="chap6_mj.html#X83C08C0B7EC1A91F">6.6-3</a>)) when any edge is removed. If the digraph <var class="Arg">D</var> is not 2-edge-connected but is connected, then any edge <code class="code">[u, v]</code> of <var class="Arg">D</var> whose removal makes the resulting digraph disconnected is called a bridge.

<code class="code">Bridges</code> returns a list of the bridges of <var class="Arg">D</var>, if any, and, in particular, returns the empty list if <var class="Arg">D</var> is not connected.

Multiple edges are ignored by this method.

The method used in this operation has complexity \(O(m+n)\) where \(m\) is the number of edges and \(n\) is the number of vertices in the digraph.

If <var class="Arg">D</var> has a bridge, then a node incident to the bridge is an articulation point (see <code class="func">ArticulationPoints</code> (<a href="chap5_mj.html#X7DDE06E47E605DD7">5.4-14</a>)) if and only if it has degree at least \(2\). It follows that if <var class="Arg">D</var> has a bridge and at least \(3\) nodes, then at least one of the nodes incident to the bridge is an articulation point. The converse does not hold, there are digraphs with articulation points, but no bridges.

See also <code class="func">IsBiconnectedDigraph</code> (<a href="chap6_mj.html#X838FAF2D825977BE">6.6-4</a>) and <code class="func">IsBridgelessDigraph</code> (<a href="chap6_mj.html#X7D2A6572820B7F24">6.6-5</a>).

<div class="example"><pre>
gap> D := Digraph([[2, 5], [1, 3, 4, 5], [2, 4], [2, 3], [1, 2]]);
<immutable digraph with 5 vertices, 12 edges>
gap> Bridges(D);
[ ]
gap> D := Digraph([[2], [3], [4], [2]]);
<immutable digraph with 4 vertices, 4 edges>
gap> Bridges(D);
[ [ 1, 2 ] ]
gap> Bridges(ChainDigraph(2));
[ [ 1, 2 ] ]
gap> ArticulationPoints(ChainDigraph(2));
[ ]
</pre></div>

<a id="X865590147BD1C507" name="X865590147BD1C507"></a>

<h5>5.4-17 StrongOrientation</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ StrongOrientation</code>( <var class="Arg">D</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ StrongOrientationAttr</code>( <var class="Arg">D</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
Returns: A digraph or <code class="keyw">fail</code>.

A strong orientation of a connected symmetric digraph <var class="Arg">D</var> (if it exists) is a strongly connected subdigraph <code class="code">C</code> of <var class="Arg">D</var> such that for every edge <code class="code">[u, v]</code> of <var class="Arg">D</var> either <code class="code">[u, v]</code> or <code class="code">[v, u]</code> is an edge of <code class="code">C</code> but not both. Robbin's Theorem states that a digraph admits a strong orientation if and only if it is bridgeless (see <code class="func">IsBridgelessDigraph</code> (<a href="chap6_mj.html#X7D2A6572820B7F24">6.6-5</a>)).

This operation returns a strong orientation of the digraph <var class="Arg">D</var> if <var class="Arg">D</var> is symmetric and <var class="Arg">D</var> admits a strong orientation. If <var class="Arg">D</var> is symmetric but does not admit a strong orientation, then <code class="keyw">fail</code> is returned. If <var class="Arg">D</var> is not symmetric, then an error is given.

If <var class="Arg">D</var> is immutable, <code class="code">StrongOrientation(<var class="Arg">D</var>)</code> returns an immutable digraph, and if <var class="Arg">D</var> is mutable, then <code class="code">StrongOrientation(<var class="Arg">D</var>)</code> returns a mutable digraph.

The method used in this operation has complexity \(O(m+n)\) where \(m\) is the number of edges and \(n\) is the number of vertices in the digraph.

<div class="example"><pre>
gap> StrongOrientation(DigraphSymmetricClosure(CycleDigraph(5))) 
> = CycleDigraph(5);
true
gap> D := DigraphSymmetricClosure(Digraph(
> [[2, 7], [3, 5], [4], [2], [6], [1], []]));;
gap> IsBridgelessDigraph(D);
false
gap> StrongOrientation(D);
fail
gap> StrongOrientation(NullDigraph(0));
<immutable empty digraph with 0 vertices>
gap> StrongOrientation(DigraphDisjointUnion(CompleteDigraph(3), 
> CompleteDigraph(3)));
fail
</pre></div>

<a id="X853D0B0981A33433" name="X853D0B0981A33433"></a>

<h5>5.4-18 DigraphPeriod</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DigraphPeriod</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
Returns: An integer.

This function returns the period of the digraph <var class="Arg">digraph</var>.

If a digraph <var class="Arg">digraph</var> has at least one directed cycle, then the period is the greatest positive integer which divides the lengths of all directed cycles of <var class="Arg">digraph</var>. If <var class="Arg">digraph</var> has no directed cycles, then this function returns \(0\). See Section <a href="chap1_mj.html#X84541F61810C741D">1.1-1</a> for the definition of a directed cycle.

A digraph with a period of \(1\) is said to be aperiodic. See <code class="func">IsAperiodicDigraph</code> (<a href="chap6_mj.html#X80E883967EBE839E">6.6-7</a>).

<div class="example"><pre>
gap> D := Digraph([[6], [1], [2], [3], [4, 4], [5]]);
<immutable multidigraph with 6 vertices, 7 edges>
gap> DigraphPeriod(D);
6
gap> D := Digraph([[2], [3, 5], [4], [5], [1, 2]]);
<immutable digraph with 5 vertices, 7 edges>
gap> DigraphPeriod(D);
1
gap> D := ChainDigraph(2);
<immutable chain digraph with 2 vertices>
gap> DigraphPeriod(D);
0
gap> IsAcyclicDigraph(D);
true
gap> D := GeneralisedPetersenGraph(IsMutableDigraph, 5, 2);
<mutable digraph with 10 vertices, 30 edges>
gap> DigraphPeriod(D);
1
</pre></div>

<a id="X864A31A8809F61C2" name="X864A31A8809F61C2"></a>

<h5>5.4-19 DigraphFloydWarshall</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DigraphFloydWarshall</code>( <var class="Arg">digraph</var>, <var class="Arg">func</var>, <var class="Arg">nopath</var>, <var class="Arg">edge</var> )</td><td class="tdright">( operation )</td></tr></table></div>
Returns: A matrix.

If <var class="Arg">digraph</var> is a digraph with \(n\) vertices, then this operation returns an \(n \times n\) matrix <code class="code">mat</code> containing the output of a generalised version of the Floyd-Warshall algorithm, applied to <var class="Arg">digraph</var>.

The operation <code class="code">DigraphFloydWarshall</code> is customised by the arguments <var class="Arg">func</var>, <var class="Arg">nopath</var>, and <var class="Arg">edge</var>. The arguments <var class="Arg">nopath</var> and <var class="Arg">edge</var> can be arbitrary GAP objects. The argument <var class="Arg">func</var> must be a function which accepts 4 arguments: the matrix <code class="code">mat</code>, followed by 3 positive integers. The function <var class="Arg">func</var> is where the work to calculate the desired outcome must be performed.

This method initialises the matrix <code class="code">mat</code> by setting entry <code class="code">mat[i][j]</code> to equal <var class="Arg">edge</var> if there is an edge with source <code class="code">i</code> and range <code class="code">j</code>, and by setting entry <code class="code">mat[i][j]</code> to equal <var class="Arg">nopath</var> otherwise. The final part of <code class="code">DigraphFloydWarshall</code> then calls the function <var class="Arg">func</var> inside three nested for loops, over the vertices of <var class="Arg">digraph</var>:

<div class="example"><pre>
for i in DigraphsVertices(digraph) do
 for j in DigraphsVertices(digraph) do
 for k in DigraphsVertices(digraph) do
 func(mat, i, j, k);
 od;
 od;
od;
</pre></div>

The matrix <code class="code">mat</code> is then returned as the result. An example of using <code class="code">DigraphFloydWarshall</code> to calculate the shortest (non-zero) distances between the vertices of a digraph is shown below:

<div class="example"><pre>
gap> D := DigraphFromDigraph6String("&EAHQeDB");
<immutable digraph with 6 vertices, 12 edges>
gap> func := function(mat, i, j, k)
> if mat[i][k] <> -1 and mat[k][j] <> -1 then
> if (mat[i][j] = -1) or (mat[i][j] > mat[i][k] + mat[k][j]) then
> mat[i][j] := mat[i][k] + mat[k][j];
> fi;
> fi;
> end;
function( mat, i, j, k ) ... end
gap> shortest_distances := DigraphFloydWarshall(D, func, -1, 1);;
gap> Display(shortest_distances);
[ [ 3, -1, -1, 2, 1, 2 ],
 [ 4, 2, 1, 3, 2, 1 ],
 [ 3, 1, 2, 2, 1, 2 ],
 [ 1, -1, -1, 1, 1, 2 ],
 [ 2, -1, -1, 1, 2, 1 ],
 [ 3, -1, -1, 2, 1, 1 ] ]
</pre></div>

<a id="X7FBAB09E7C0BE5CF" name="X7FBAB09E7C0BE5CF"></a>

<h5>5.4-20 IsReachable</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsReachable</code>( <var class="Arg">digraph</var>, <var class="Arg">u</var>, <var class="Arg">v</var> )</td><td class="tdright">( operation )</td></tr></table></div>
Returns: <code class="keyw">true</code> or <code class="keyw">false</code>.

This operation returns <code class="keyw">true</code> if there exists a non-trivial directed walk from vertex <var class="Arg">u</var> to vertex <var class="Arg">v</var> in the digraph <var class="Arg">digraph</var>, and <code class="keyw">false</code> if there does not exist such a directed walk. See Section <a href="chap1_mj.html#X84541F61810C741D">1.1-1</a> for the definition of a non-trivial directed walk.

The method for <code class="code">IsReachable</code> has worst case complexity of \(O(m + n)\) where \(m\) is the number of edges and \(n\) the number of vertices in <var class="Arg">digraph</var>.

<div class="example"><pre>
gap> D := Digraph([[2], [3], [2, 3]]);
<immutable digraph with 3 vertices, 4 edges>
gap> IsReachable(D, 1, 3);
true
gap> IsReachable(D, 2, 1);
false
gap> IsReachable(D, 3, 3);
true
gap> IsReachable(D, 1, 1);
false
</pre></div>

<a id="X7ECD22877AEA89CC" name="X7ECD22877AEA89CC"></a>

<h5>5.4-21 IsDigraphPath</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsDigraphPath</code>( <var class="Arg">D</var>, <var class="Arg">v</var>, <var class="Arg">a</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsDigraphPath</code>( <var class="Arg">D</var>, <var class="Arg">list</var> )</td><td class="tdright">( operation )</td></tr></table></div>
Returns: <code class="keyw">true</code> or <code class="keyw">false</code>.

This function returns <code class="keyw">true</code> if the arguments <var class="Arg">v</var> and <var class="Arg">a </var> describe a path in the digraph <var class="Arg">D</var>. A directed path (or directed cycle) of non-zero length <code class="code">n-1</code>, \((v_1, e_1, v_2, e_2, ..., e_{n-1}, v_n)\), is represented by a pair of lists <code class="code">[<var class="Arg">v</var>, <var class="Arg">a</var>]</code> as follows:

<ul>
<li><var class="Arg">v</var> is the list \([v_1, v_2, ..., v_n]\).

</li>
<li><var class="Arg">a</var> is the list of positive integers \([a_1, a_2, ..., a_{n-1}]\) where for each each \(i < n\), \(a_i\) is the position of \(v_{i+1}\) in <code class="code">OutNeighboursOfVertex(</code><var class="Arg">D</var><code class="code">,</code>\(v_i\)<code class="code">)</code> corresponding to the edge \(e_i\). This can be useful if the position of a vertex in a list of out-neighours is significant, for example in orbit digraphs.

</li>
</ul>
If the arguments to <code class="code">IsDigraphPath</code> are a digraph <var class="Arg">D</var> and list <var class="Arg">list</var>, then this is equivalent to calling <code class="code">IsDigraphPath(<var class="Arg">D</var>, <var class="Arg">list</var>[1], <var class="Arg">list</var>[2])</code>.

<div class="example"><pre>
gap> D := Digraph(IsMutableDigraph, Combinations([1 .. 5]), IsSubset);
<mutable digraph with 32 vertices, 243 edges>
gap> DigraphReflexiveTransitiveReduction(D);
<mutable digraph with 32 vertices, 80 edges>
gap> MakeImmutable(D);
<immutable digraph with 32 vertices, 80 edges>
gap> IsDigraphPath(D, [32, 31, 33], [1, 1]);
false
gap> IsDigraphPath(D, [1], []);
true
gap> IsDigraphPath(D, [6, 9, 16, 17], [3, 3, 2]);
true
gap> IsDigraphPath(D, DigraphPath(D, 6, 1));
true
</pre></div>

<a id="X7F255A2A84CB868C" name="X7F255A2A84CB868C"></a>

<h5>5.4-22 VerticesReachableFrom</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ VerticesReachableFrom</code>( <var class="Arg">digraph</var>, <var class="Arg">root</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ VerticesReachableFrom</code>( <var class="Arg">digraph</var>, <var class="Arg">list</var> )</td><td class="tdright">( operation )</td></tr></table></div>
Returns: A list.

This operation returns a list of the vertices <code class="code">v</code>, for which there exists a non-trivial directed walk from the vertex <var class="Arg">root</var>, or any of the list of vertices <var class="Arg">list</var>, to vertex <code class="code">v</code> in the digraph <var class="Arg">digraph</var>. See Section <a href="chap1_mj.html#X84541F61810C741D">1.1-1</a> for the definition of a non-trivial directed walk.

The method for <code class="code">VerticesReachableFrom</code> has worst case complexity of \(O(m + n)\) where \(m\) is the number of edges and \(n\) the number of vertices in <var class="Arg">digraph</var>.

This function returns an error if <var class="Arg">root</var>, or any vertex in <var class="Arg">list</var>, is not a vertices of <var class="Arg">digraph</var>.

<div class="example"><pre>
gap> D := CompleteDigraph(5);
<immutable complete digraph with 5 vertices>
gap> VerticesReachableFrom(D, 1);
[ 1, 2, 3, 4, 5 ]
gap> VerticesReachableFrom(D, 3);
[ 1, 2, 3, 4, 5 ]
gap> D := EmptyDigraph(5);
<immutable empty digraph with 5 vertices>
gap> VerticesReachableFrom(D, 1);
[ ]
gap> VerticesReachableFrom(D, 3);
[ ]
gap> VerticesReachableFrom(D, [1, 2, 3, 4]);
[ ]
gap> VerticesReachableFrom(D, [3, 4, 5]);
[ ]
gap> D := CycleDigraph(4);
<immutable cycle digraph with 4 vertices>
gap> VerticesReachableFrom(D, 1);
[ 1, 2, 3, 4 ]
gap> VerticesReachableFrom(D, 3);
[ 1, 2, 3, 4 ]
gap> D := ChainDigraph(5);
<immutable chain digraph with 5 vertices>
gap> VerticesReachableFrom(D, 1);
[ 2, 3, 4, 5 ]
gap> VerticesReachableFrom(D, 3);
[ 4, 5 ]
gap> VerticesReachableFrom(D, 5);
[ ]
gap> VerticesReachableFrom(D, [3, 4]);
[ 4, 5 ]
</pre></div>

<a id="X8039170B82A32257" name="X8039170B82A32257"></a>

<h5>5.4-23 DigraphPath</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DigraphPath</code>( <var class="Arg">digraph</var>, <var class="Arg">u</var>, <var class="Arg">v</var> )</td><td class="tdright">( operation )</td></tr></table></div>
Returns: A pair of lists, or <code class="keyw">fail</code>.

If there exists a non-trivial directed path (or a non-trivial cycle, in the case that <var class="Arg">u</var> <code class="code">=</code> <var class="Arg">v</var>) from vertex <var class="Arg">u</var> to vertex <var class="Arg">v</var> in the digraph <var class="Arg">digraph</var>, then this operation returns such a directed path (or directed cycle). Otherwise, this operation returns <code class="keyw">fail</code>. See Section <a href="chap1_mj.html#X84541F61810C741D">Definitions</a> for the definition of a directed path and a directed cycle.

A directed path (or directed cycle) of non-zero length <code class="code">n-1</code>, \((v_1, e_1, v_2, e_2, ..., e_{n-1}, v_n)\), is represented by a pair of lists <code class="code">[v,a]</code> as follows:

<ul>
<li><code class="code">v</code> is the list \([v_1, v_2, ..., v_n]\).

</li>
<li><code class="code">a</code> is the list of positive integers \([a_1, a_2, ..., a_{n-1}]\) where for each each \(i < n\), \(a_i\) is the position of \(v_{i+1}\) in <code class="code">OutNeighboursOfVertex(</code><var class="Arg">digraph</var><code class="code">,</code>\(v_i\)<code class="code">)</code> corresponding to the edge \(e_i\). This can be useful if the position of a vertex in a list of out-neighours is significant, for example in orbit digraphs.

</li>
</ul>
The method for <code class="code">DigraphPath</code> has worst case complexity of \(O(m + n)\) where \(m\) is the number of edges and \(n\) the number of vertices in <var class="Arg">digraph</var>.

See also <code class="func">IsDigraphPath</code> (<a href="chap5_mj.html#X7ECD22877AEA89CC">5.4-21</a>).

<div class="example"><pre>
gap> D := Digraph([[2], [3], [2, 3]]);
<immutable digraph with 3 vertices, 4 edges>
gap> DigraphPath(D, 1, 3);
[ [ 1, 2, 3 ], [ 1, 1 ] ]
gap> DigraphPath(D, 2, 1);
fail
gap> DigraphPath(D, 3, 3);
[ [ 3, 3 ], [ 2 ] ]
gap> DigraphPath(D, 1, 1);
fail
</pre></div>

<a id="X80E9D645843973A6" name="X80E9D645843973A6"></a>

<h5>5.4-24 DigraphShortestPath</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DigraphShortestPath</code>( <var class="Arg">digraph</var>, <var class="Arg">u</var>, <var class="Arg">v</var> )</td><td class="tdright">( operation )</td></tr></table></div>
Returns: A pair of lists, or <code class="keyw">fail</code>.

Returns a shortest directed path in the digraph <var class="Arg">digraph</var> from vertex <var class="Arg">u</var> to vertex <var class="Arg">v</var>, if such a path exists. If <code class="code"><var class="Arg">u</var> = <var class="Arg">v</var></code>, then the shortest non-trivial cycle is returned, again, if it exists. Otherwise, this operation returns <code class="keyw">fail</code>. See Section <a href="chap1_mj.html#X84541F61810C741D">Definitions</a> for the definition of a directed path and a directed cycle.

See <code class="func">DigraphPath</code> (<a href="chap5_mj.html#X8039170B82A32257">5.4-23</a>) for details on the output. The method for <code class="code">DigraphShortestPath</code> has worst case complexity of \(O(m + n)\) where \(m\) is the number of edges and \(n\) the number of vertices in <var class="Arg">digraph</var>.

<div class="example"><pre>
gap> D := Digraph([[1, 2], [3], [2, 4], [1], [2, 4]]);
<immutable digraph with 5 vertices, 8 edges>
gap> DigraphShortestPath(D, 5, 1);
[ [ 5, 4, 1 ], [ 2, 1 ] ]
gap> DigraphShortestPath(D, 3, 3);
[ [ 3, 2, 3 ], [ 1, 1 ] ]
gap> DigraphShortestPath(D, 5, 5);
fail
gap> DigraphShortestPath(D, 1, 1);
[ [ 1, 1 ], [ 1 ] ]
</pre></div>

<a id="X7C45396C808308C4" name="X7C45396C808308C4"></a>

<h5>5.4-25 DigraphRandomWalk</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DigraphRandomWalk</code>( <var class="Arg">digraph</var>, <var class="Arg">v</var>, <var class="Arg">t</var> )</td><td class="tdright">( operation )</td></tr></table></div>
Returns: A pair of lists.

Returns a directed path corresponding to a random walk in the digraph <var class="Arg">digraph</var>, starting at vertex <var class="Arg">v</var> and having length no more than <var class="Arg">t</var>.

A random walk is defined as follows. The path begins at <var class="Arg">v</var>, and at each step it follows a random edge leaving the current vertex. It continues through the digraph in this way until it has traversed <var class="Arg">t</var> edges, or until it reaches a vertex with no out-edges (a sink) and therefore cannot continue.

The output has the same form as that of <code class="func">DigraphPath</code> (<a href="chap5_mj.html#X8039170B82A32257">5.4-23</a>).

<div class="example"><pre>
gap> D := Digraph([[1, 2], [3], [2, 4], [1], [2, 4]]); 
<immutable digraph with 5 vertices, 8 edges>
gap> DigraphRandomWalk(D, 1, 4);
[ [ 1, 2, 3, 2, 3 ], [ 2, 1, 1, 1 ] ]
</pre></div>

<a id="X787459247B2005E6" name="X787459247B2005E6"></a>

<h5>5.4-26 DigraphAbsorptionProbabilities</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DigraphAbsorptionProbabilities</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
Returns: A matrix of rational numbers.

A random walk of infinite length through a finite digraph may pass through several different strongly connected components (SCCs). However, with probability 1 it must eventually reach an SCC which it can never leave, because the SCC has no out-edges leading to other SCCs. We may say that such an SCC has absorbed the random walk, and we can calculate the probability of each SCC absorbing a walk starting at a given vertex.

<code class="code">DigraphAbsorptionProbabilities</code> returns an \(m \times n\) matrix <code class="code">mat</code>, where \(m\) is the number of vertices in <code class="code">digraph</code> and \(n\) is the number of strongly connected components. Each entry <code class="code">mat[i][j]</code> is a rational number representing the probability that an unbounded random walk starting at vertex <code class="code">i</code> will be absorbed by strongly connected component <code class="code">j</code> – that is, the probability that it will reach the component and never leave.

Strongly connected components are indexed in the order given by <code class="func">DigraphStronglyConnectedComponents</code> (<a href="chap5_mj.html#X833ECD6B7A84944C">5.4-11</a>). See also <code class="func">DigraphRandomWalk</code> (<a href="chap5_mj.html#X7C45396C808308C4">5.4-25</a>) and <code class="func">DigraphAbsorptionExpectedSteps</code> (<a href="chap5_mj.html#X7B0A62CF7F6F23E9">5.4-27</a>).

<div class="example"><pre>
gap> gr := Digraph([[2, 3, 4], [3], [2], []]);
<immutable digraph with 4 vertices, 5 edges>
gap> DigraphStronglyConnectedComponents(gr).comps;
[ [ 2, 3 ], [ 4 ], [ 1 ] ]
gap> DigraphAbsorptionProbabilities(gr);
[ [ 2/3, 1/3, 0 ], [ 1, 0, 0 ], [ 1, 0, 0 ], [ 0, 1, 0 ] ]
</pre></div>

<a id="X7B0A62CF7F6F23E9" name="X7B0A62CF7F6F23E9"></a>

<h5>5.4-27 DigraphAbsorptionExpectedSteps</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DigraphAbsorptionExpectedSteps</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
Returns: A list of rational numbers.

A random walk of unbounded length through a finite digraph may pass through several different strongly connected components (SCCs). However, with probability 1 it must eventually reach an SCC which it can never leave, because the SCC has no out-edges leading to other SCCs. When this happens, we say the walk has been absorbed.

<code class="code">DigraphAbsorptionExpectedSteps</code> returns a list <code class="code">L</code> with length equal to the number of vertices of <var class="Arg">digraph</var>, where <code class="code">L[v]</code> is the expected number of steps a random walk starting at vertex <code class="code">v</code> should take before it is absorbed – that is, the expected number of steps to reach an SCC that it can never leave.

See also <code class="func">DigraphRandomWalk</code> (<a href="chap5_mj.html#X7C45396C808308C4">5.4-25</a>) and <code class="func">DigraphAbsorptionProbabilities</code> (<a href="chap5_mj.html#X787459247B2005E6">5.4-26</a>).

<div class="example"><pre>
gap> gr := Digraph([[2], [3, 4], [], [2]]);
<immutable digraph with 4 vertices, 4 edges>
gap> DigraphAbsorptionExpectedSteps(gr);
[ 4, 3, 0, 4 ]
</pre></div>

<a id="X7FE79CB278CE6991" name="X7FE79CB278CE6991"></a>

<h5>5.4-28 Dominators</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Dominators</code>( <var class="Arg">digraph</var>, <var class="Arg">root</var> )</td><td class="tdright">( operation )</td></tr></table></div>
Returns: A list of lists.

<code class="code">Dominators</code> takes a <var class="Arg">digraph</var> and a root <var class="Arg">root</var> and returns the dominators of each vertex with respect to the root. The output is returned as a list of length <code class="code">DigraphNrVertices(<var class="Arg">Digraph</var>)</code>, whose <var class="Arg">i</var>th entry is a list with the dominators of vertex <var class="Arg">i</var> of the <var class="Arg">digraph</var>. If there is no path from the root to a specific vertex, the output will contain a hole in the corresponding position. The dominators of a vertex \(u\) are the vertices that are contained in every path from the \(root\) to \(u\), not including \(u\) itself. The method for this operation is an implementation of an algorithm by Thomas Lengauer and Robert Endre Tarjan <a href="chapBib_mj.html#biBLT79">[LT79]</a>. The complexity of this algorithm is \(O(mlog n)\) where \(m\) is the number of edges and \(n\) is the number of nodes in the subdigraph induced by the nodes in <var class="Arg">digraph</var> reachable from <var class="Arg">root</var>.

<div class="example"><pre>
gap> D := Digraph([[2], [3, 6], [2, 4], [1], [], [3]]);
<immutable digraph with 6 vertices, 7 edges>
gap> Dominators(D, 1);
[ , [ 1 ], [ 2, 1 ], [ 3, 2, 1 ],, [ 2, 1 ] ]
gap> Dominators(D, 2);
[ [ 4, 3, 2 ],, [ 2 ], [ 3, 2 ],, [ 2 ] ]
gap> Dominators(D, 3);
[ [ 4, 3 ], [ 3 ],, [ 3 ],, [ 2, 3 ] ]
gap> Dominators(D, 4);
[ [ 4 ], [ 1, 4 ], [ 2, 1, 4 ],,, [ 2, 1, 4 ] ]
gap> Dominators(D, 5);
[ ]
gap> Dominators(D, 6);
[ [ 4, 3, 6 ], [ 3, 6 ], [ 6 ], [ 3, 6 ] ]
</pre></div>

<a id="X7D66A0FB7F6100FB" name="X7D66A0FB7F6100FB"></a>

<h5>5.4-29 DominatorTree</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DominatorTree</code>( <var class="Arg">digraph</var>, <var class="Arg">root</var> )</td><td class="tdright">( operation )</td></tr></table></div>
Returns: A record.

<code class="code">DominatorTree</code> takes a <var class="Arg">digraph</var> and a <var class="Arg">root</var> vertex and returns a record with the following components:

<dl>
<dt>idom</dt>
<dd>the immediate dominators of the vertices with respect to the root.

</dd>
<dt>preorder</dt>
<dd>the preorder values of the vertices defined by the depth first search executed on the digraph.

</dd>
</dl>
The immediate dominator of a vertex \(u\) is the unique dominator of \(u\) that is dominated by all other dominators of \(u\). The algorithm is an implementation of the fast algorithm written by Thomas Lengauer and Robert Endre Tarjan <a href="chapBib_mj.html#biBLT79">[LT79]</a>. The complexity of this algorithm is \(O(mlog n)\) where \(m\) is the number of edges and \(n\) is the number of nodes in the subdigraph induced by the nodes in <var class="Arg">digraph</var> reachable from <var class="Arg">root</var>.

<div class="example"><pre>
gap> D := Digraph([[2, 3], [4, 6], [4, 5], [3, 5], [1, 6], [2, 3]]);
<immutable digraph with 6 vertices, 12 edges>
gap> DominatorTree(D, 1);
rec( idom := [ fail, 1, 1, 1, 1, 1 ],
 preorder := [ 1, 2, 4, 3, 5, 6 ] )
gap> DominatorTree(D, 5);
rec( idom := [ 5, 5, 5, 5, fail, 5 ],
 preorder := [ 5, 1, 2, 4, 3, 6 ] )
gap> D := CompleteDigraph(5);
<immutable complete digraph with 5 vertices>
gap> DominatorTree(D, 1);
rec( idom := [ fail, 1, 1, 1, 1 ], preorder := [ 1, 2, 3, 4, 5 ] )
gap> DominatorTree(D, 2);
rec( idom := [ 2, fail, 2, 2, 2 ], preorder := [ 2, 1, 3, 4, 5 ] )
</pre></div>

<a id="X7C0416FE7A69CA2C" name="X7C0416FE7A69CA2C"></a>

<h5>5.4-30 IteratorOfPaths</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IteratorOfPaths</code>( <var class="Arg">digraph</var>, <var class="Arg">u</var>, <var class="Arg">v</var> )</td><td class="tdright">( operation )</td></tr></table></div>
Returns: An iterator.

If <var class="Arg">digraph</var> is a digraph or a list of adjacencies which defines a digraph - see <code class="func">OutNeighbours</code> (<a href="chap5_mj.html#X7E9880767AE68E00">5.2-6</a>) - then this operation returns an iterator of the non-trivial directed paths (or directed cycles, in the case that <var class="Arg">u</var> <code class="code">=</code> <var class="Arg">v</var>) in <var class="Arg">digraph</var> from the vertex <var class="Arg">u</var> to the vertex <var class="Arg">v</var>.

See <code class="func">DigraphPath</code> (<a href="chap5_mj.html#X8039170B82A32257">5.4-23</a>) for more information about the representation of a directed path or directed cycle which is used, and see <a href="/home/runner/gap/doc/ref/chap30_mj.html#X85A3F00985453F95">Reference: Iterators</a> for more information about iterators. See Section <a href="chap1_mj.html#X84541F61810C741D">Definitions</a> for the definition of a directed path and a directed cycle.

<div class="example"><pre>
gap> D := Digraph([[1, 4, 4, 2], [3, 5], [2, 3], [1, 2], [4]]);
<immutable multidigraph with 5 vertices, 11 edges>
gap> iter := IteratorOfPaths(D, 1, 4);
<iterator>
gap> NextIterator(iter);
[ [ 1, 4 ], [ 2 ] ]
gap> NextIterator(iter);
[ [ 1, 4 ], [ 3 ] ]
gap> NextIterator(iter);
[ [ 1, 2, 5, 4 ], [ 4, 2, 1 ] ]
gap> IsDoneIterator(iter);
true
gap> iter := IteratorOfPaths(D, 4, 3);
<iterator>
gap> NextIterator(iter);
[ [ 4, 1, 2, 3 ], [ 1, 4, 1 ] ]
</pre></div>

<a id="X7ECD16838704FAAA" name="X7ECD16838704FAAA"></a>

<h5>5.4-31 DigraphAllSimpleCircuits</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DigraphAllSimpleCircuits</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
Returns: A list of lists of vertices.

If <var class="Arg">digraph</var> is a digraph, then <code class="code">DigraphAllSimpleCircuits</code> returns a list of the simple circuits in <var class="Arg">digraph</var>.

See Section <a href="chap1_mj.html#X84541F61810C741D">1.1-1</a> for the definition of a simple circuit, and related notions. Note that a loop is a simple circuit.

For a digraph without multiple edges, a simple circuit is uniquely determined by its subsequence of vertices. However this is not the case for a multidigraph. The attribute <code class="code">DigraphAllSimpleCircuits</code> ignores multiple edges, and identifies a simple circuit using only its subsequence of vertices. For example, although the simple circuits \((v, e, v)\) and \((v, e', v)\) (for distinct edges \(e\) and \(e'\)) are mathematically distinct, <code class="code">DigraphAllSimpleCircuits</code> considers them to be the same.

With this approach, a directed circuit of length <code class="code">n</code> can be determined by a list of its first <code class="code">n</code> vertices. Thus a simple circuit \((v_1, e_1, v_2, e_2, ..., e_{n-1}, v_n, e_{n+1}, v_1)\) can be represented as the list \([v_1, \ldots, v_n]\), or any cyclic permutation thereof. For each simple circuit of <var class="Arg">digraph</var>, <code class="code">DigraphAllSimpleCircuits(<var class="Arg">digraph</var>)</code> includes precisely one such list to represent the circuit.

<div class="example"><pre>
gap> D := Digraph([[], [3], [2, 4], [5, 4], [4]]);
<immutable digraph with 5 vertices, 6 edges>
gap> DigraphAllSimpleCircuits(D);
[ [ 4 ], [ 4, 5 ], [ 2, 3 ] ]
gap> D := ChainDigraph(10);;
gap> DigraphAllSimpleCircuits(D);
[ ]
gap> D := Digraph([[3], [1], [1]]);
<immutable digraph with 3 vertices, 3 edges>
gap> DigraphAllSimpleCircuits(D);
[ [ 1, 3 ] ]
gap> D := Digraph([[1, 1]]);
<immutable multidigraph with 1 vertex, 2 edges>
gap> DigraphAllSimpleCircuits(D);
[ [ 1 ] ]
gap> D := CycleDigraph(IsMutableDigraph, 3);
<mutable digraph with 3 vertices, 3 edges>
gap> DigraphAllSimpleCircuits(D);
[ [ 1, 2, 3 ] ]
</pre></div>

<a id="X7C735C4E86BDD5F6" name="X7C735C4E86BDD5F6"></a>

<h5>5.4-32 DigraphLongestSimpleCircuit</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DigraphLongestSimpleCircuit</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
Returns: A list of vertices, or <code class="keyw">fail</code>.

If <var class="Arg">digraph</var> is a digraph, then <code class="code">DigraphLongestSimpleCircuit</code> returns the longest simple circuit in <var class="Arg">digraph</var>. See Section <a href="chap1_mj.html#X84541F61810C741D">1.1-1</a> for the definition of simple circuit, and the definition of length for a simple circuit.

This attribute computes <code class="code">DigraphAllSimpleCircuits(</code><var class="Arg">digraph</var><code class="code">)</code> to find all the simple circuits of <var class="Arg">digraph</var>, and returns one of maximal length. A simple circuit is represented as a list of vertices, in the same way as described in <code class="func">DigraphAllSimpleCircuits</code> (<a href="chap5_mj.html#X7ECD16838704FAAA">5.4-31</a>).

If <var class="Arg">digraph</var> has no simple circuits, then this attribute returns <code class="keyw">fail</code>. If <var class="Arg">digraph</var> has multiple simple circuits of maximal length, then this attribute returns one of them.

<div class="example"><pre>
gap> D := Digraph([[], [3], [2, 4], [5, 4], [4]]);;
gap> DigraphLongestSimpleCircuit(D);
[ 4, 5 ]
gap> D := ChainDigraph(10);;
gap> DigraphLongestSimpleCircuit(D);
fail
gap> D := Digraph([[3], [1], [1, 4], [1, 1]]);;
gap> DigraphLongestSimpleCircuit(D);
[ 1, 3, 4 ]
gap> D := GeneralisedPetersenGraph(IsMutableDigraph, 4, 1);
<mutable digraph with 8 vertices, 24 edges>
gap> DigraphLongestSimpleCircuit(D);
[ 1, 2, 3, 4, 8, 7, 6, 5 ]
</pre></div>

<a id="X7F9EDAA8854FB538" name="X7F9EDAA8854FB538"></a>

<h5>5.4-33 DigraphAllUndirectedSimpleCircuits</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DigraphAllUndirectedSimpleCircuits</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
Returns: A list of lists of vertices.

If <var class="Arg">digraph</var> is a digraph, then <code class="code">DigraphAllUndirectedSimpleCircuits</code> returns a list of the undirected simple circuits in <var class="Arg">digraph</var>.

See Section <a href="chap1_mj.html#X84541F61810C741D">1.1-1</a> for the definition of a simple circuit, and related notions. Note that a loop is a simple circuit. A simple circuit is undirected if the orientation of the edges in the circuit does not matter.

The attribute <code class="code">DigraphAllUndirectedSimpleCircuitss</code> ignores multiple edges, and identifies a undirected simple circuit using only its subsequence of vertices. See Section <a href="chap5_mj.html#X7ECD16838704FAAA">5.4-31</a> for more details on simple circuits.

<div class="example"><pre>
gap> D := ChainDigraph(10);;
gap> DigraphAllUndirectedSimpleCircuits(D);
[ ]
gap> D := Digraph([[1, 1]]);
<immutable multidigraph with 1 vertex, 2 edges>
gap> DigraphAllUndirectedSimpleCircuits(D);
[ [ 1 ] ]
gap> D := CycleDigraph(IsMutableDigraph, 3);
<mutable digraph with 3 vertices, 3 edges>
gap> DigraphAllUndirectedSimpleCircuits(D);
[ [ 1, 2, 3 ] ]
gap> D := DigraphSymmetricClosure(CycleDigraph(IsMutableDigraph, 3));
<mutable digraph with 3 vertices, 6 edges>
gap> DigraphAllUndirectedSimpleCircuits(D);
[ [ 1, 2, 3 ] ]
</pre></div>

<a id="X7F0AC5617CE5E9DD" name="X7F0AC5617CE5E9DD"></a>

<h5>5.4-34 DigraphAllChordlessCycles</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DigraphAllChordlessCycles</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DigraphAllChordlessCyclesOfMaximalLength</code>( <var class="Arg">digraph</var>, <var class="Arg">maxLength</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
Returns: A list of lists of vertices.

If <var class="Arg">digraph</var> is a digraph, then <code class="code">DigraphAllChordlessCycles</code> returns a list of the chordless cycles in <var class="Arg">digraph</var>. The method <code class="code">DigraphAllChordlessCyclesOfMaximalLength</code> returns a list of all chordless cycles in <var class="Arg">digraph</var> of length at most <var class="Arg">maxLength</var>

A chordless cycle \(C\) is a undirected simple circuit (see Section <a href="chap1_mj.html#X84541F61810C741D">1.1-1</a> ) where each pair of vertices in \(C\) are not connected by an edge not in \(C\). Here, cycles of length two are ignored.

For a digraph without multiple edges, a simple circuit is uniquely determined by its subsequence of vertices. However this is not the case for a multidigraph. The attribute <code class="code">DigraphAllChordlessCycles</code> ignores multiple edges, and identifies a simple circuit using only its subsequence of vertices. See Section <a href="chap5_mj.html#X7ECD16838704FAAA">5.4-31</a> for more details.

This method uses the algorithms described in <a href="chapBib_mj.html#biBUS14">[US14]</a>.

<div class="example"><pre>
gap> D := ChainDigraph(10);;
gap> DigraphAllChordlessCycles(D);
[ ]
gap> D := Digraph([[1, 1]]);
<immutable multidigraph with 1 vertex, 2 edges>
gap> DigraphAllChordlessCycles(D);
[ ]
gap> D := CycleDigraph(3);;
gap> DigraphAllChordlessCycles(D);
[ [ 2, 1, 3 ] ]
gap> D := CompleteDigraph(4);
<immutable complete digraph with 4 vertices>
gap> DigraphAllChordlessCycles(D);
[ [ 2, 1, 3 ], [ 2, 1, 4 ], [ 3, 1, 4 ], [ 3, 2, 4 ] ]
</pre></div>

<a id="X805F15398735AD7D" name="X805F15398735AD7D"></a>

<h5>5.4-35 FacialWalks</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ FacialWalks</code>( <var class="Arg">digraph</var>, <var class="Arg">list</var> )</td><td class="tdright">( operation )</td></tr></table></div>
Returns: A list of lists of vertices.

If <var class="Arg">digraph</var> is an Eulerian digraph and <var class="Arg">list</var> is a rotation system of <var class="Arg">digraph</var>, then <code class="code">FacialWalks</code> returns a list of the facial walks in <var class="Arg">digraph</var>.

A rotation system defines for each vertex the ordering of the out-neighbours. For example, the method <a href="chap5_mj.html#X84E3947E7D39BA64">5.7-3</a> computes for a planar digraph <var class="Arg">D</var> the rotation system of a planar embedding of <var class="Arg">D</var>. The facial walks of <var class="Arg">digraph</var> are closed walks and they are defined by the rotation system <var class="Arg">list</var>. They describe the boundaries of the faces of the embedding of <var class="Arg">digraph</var> given by the rotation system <var class="Arg">list</var>. The operation <code class="code">FacialWalks</code> ignores multiple edges and loops.

Here are some examples for planar embeddings:

<div class="example"><pre>
gap> D1 := CycleDigraph(4);;
gap> planar := PlanarEmbedding(D1);
[ [ 2 ], [ 3 ], [ 4 ], [ 1 ] ]
gap> FacialWalks(D1, planar);
[ [ 1, 2, 3, 4 ] ]
gap> nonPlanar := [[2, 4], [1, 3], [2, 4], [1, 3]];;
gap> FacialWalks(D1, nonPlanar);
[ [ 1, 2, 3, 4 ] ]
gap> D2 := CompleteMultipartiteDigraph([2, 2, 2]);;
gap> rotationSystem := PlanarEmbedding(D2);
[ [ 3, 5, 4, 6 ], [ 6, 4, 5, 3 ], [ 6, 2, 5, 1 ], [ 1, 5, 2, 6 ],
 [ 1, 3, 2, 4 ], [ 1, 4, 2, 3 ] ]
gap> FacialWalks(D2, rotationSystem);
[ [ 1, 3, 6 ], [ 1, 4, 5 ], [ 1, 5, 3 ], [ 1, 6, 4 ], [ 2, 3, 5 ],
 [ 2, 4, 6 ], [ 2, 5, 4 ], [ 2, 6, 3 ] ]
</pre></div>

Here is an example of a non-planar digraph with a corresponding rotation system:

<div class="example"><pre>
gap> D3 := CompleteMultipartiteDigraph([3, 3]);;
gap> rot := [[6, 5, 4], [6, 5, 4], [6, 5, 4], [1, 2, 3],
> [1, 2, 3], [1, 2, 3]];
[ [ 6, 5, 4 ], [ 6, 5, 4 ], [ 6, 5, 4 ], [ 1, 2, 3 ], [ 1, 2, 3 ],
 [ 1, 2, 3 ] ]
gap> FacialWalks(D3, rot);
[ [ 1, 4, 2, 6, 3, 5 ], [ 1, 5, 2, 4, 3, 6 ], [ 1, 6, 2, 5, 3, 4 ] ]
</pre></div>

<a id="X870E04307C5F213F" name="X870E04307C5F213F"></a>

<h5>5.4-36 DigraphLayers</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DigraphLayers</code>( <var class="Arg">digraph</var>, <var class="Arg">vertex</var> )</td><td class="tdright">( operation )</td></tr></table></div>
Returns: A list.

This operation returns a list <code class="keyw">list</code> such that <code class="keyw">list[i]</code> is the list of vertices whose minimum distance from the vertex <var class="Arg">vertex</var> in <var class="Arg">digraph</var> is <code class="keyw">i - 1</code>. Vertex <var class="Arg">vertex</var> is assumed to be at distance <code class="keyw">0</code> from itself.

<div class="example"><pre>
gap> D := CompleteDigraph(4);;
gap> DigraphLayers(D, 1);
[ [ 1 ], [ 2, 3, 4 ] ]
</pre></div>

<a id="X7B2E42327DA118E0" name="X7B2E42327DA118E0"></a>

<h5>5.4-37 DigraphDegeneracy</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DigraphDegeneracy</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
Returns: A non-negative integer, or <code class="keyw">fail</code>.

If <var class="Arg">digraph</var> is a symmetric digraph without multiple edges - see <code class="func">IsSymmetricDigraph</code> (<a href="chap6_mj.html#X81B3EA7887219860">6.2-14</a>) and <code class="func">IsMultiDigraph</code> (<a href="chap6_mj.html#X7BB84CFC7E8B2B26">6.2-11</a>) - then this attribute returns the degeneracy of <var class="Arg">digraph</var>.

The degeneracy of a digraph is the least integer <code class="code">k</code> such that every induced of <var class="Arg">digraph</var> contains a vertex whose number of neighbours (excluding itself) is at most <code class="code">k</code>. Note that this means that loops are ignored.

If <var class="Arg">digraph</var> is not symmetric or has multiple edges then this attribute returns <code class="keyw">fail</code>.

<div class="example"><pre>
gap> D := DigraphSymmetricClosure(ChainDigraph(5));;
gap> DigraphDegeneracy(D);
1
gap> D := CompleteDigraph(5);;
gap> DigraphDegeneracy(D);
4
gap> D := Digraph([[1], [2, 4, 5], [3, 4], [2, 3, 4], [2], []]);
<immutable digraph with 6 vertices, 10 edges>
gap> DigraphDegeneracy(D);
1
gap> D := GeneralisedPetersenGraph(IsMutableDigraph, 10, 3);
<mutable digraph with 20 vertices, 60 edges>
gap> DigraphDegeneracy(D);
3
</pre></div>

<a id="X827C2BD17A4547E3" name="X827C2BD17A4547E3"></a>

<h5>5.4-38 DigraphDegeneracyOrdering</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DigraphDegeneracyOrdering</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
Returns: A list of integers, or <code class="keyw">fail</code>.

If <var class="Arg">digraph</var> is a digraph for which <code class="code">DigraphDegeneracy(</code><var class="Arg">digraph</var><code class="code">)</code> is a non-negative integer <code class="code">k</code> - see <code class="func">DigraphDegeneracy</code> (<a href="chap5_mj.html#X7B2E42327DA118E0">5.4-37</a>) - then this attribute returns a degeneracy ordering of the vertices of the vertices of <var class="Arg">digraph</var>.

A degeneracy ordering of <var class="Arg">digraph</var> is a list <code class="code">ordering</code> of the vertices of <var class="Arg">digraph</var> ordered such that for any position <code class="code">i</code> of the list, the vertex <code class="code">ordering[i]</code> has at most <code class="code">k</code> neighbours in later position of the list.

If <code class="code">DigraphDegeneracy(</code><var class="Arg">digraph</var><code class="code">)</code> returns <code class="keyw">fail</code>, then this attribute returns <code class="keyw">fail</code>.

<div class="example"><pre>
gap> D := DigraphSymmetricClosure(ChainDigraph(5));;
gap> DigraphDegeneracyOrdering(D);
[ 5, 4, 3, 2, 1 ]
gap> D := CompleteDigraph(5);;
gap> DigraphDegeneracyOrdering(D);
[ 5, 4, 3, 2, 1 ]
gap> D := Digraph([[1], [2, 4, 5], [3, 4], [2, 3, 4], [2], []]);
<immutable digraph with 6 vertices, 10 edges>
gap> DigraphDegeneracyOrdering(D);
[ 1, 6, 5, 2, 4, 3 ]
gap> D := GeneralisedPetersenGraph(IsMutableDigraph, 3, 1);
<mutable digraph with 6 vertices, 18 edges>
gap> DigraphDegeneracyOrdering(D);
[ 6, 5, 4, 1, 3, 2 ]
</pre></div>

<a id="X863FDFC4839A3B82" name="X863FDFC4839A3B82"></a>

<h5>5.4-39 HamiltonianPath</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ HamiltonianPath</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
Returns: A list or <code class="keyw">fail</code>.

Returns a Hamiltonian path if one exists, <code class="keyw">fail</code> if not.

A Hamiltonian path of a digraph with <code class="code">n</code> vertices is directed cycle of length <code class="code">n</code>. If <var class="Arg">digraph</var> is a digraph that contains a Hamiltonian path, then this function returns one, described in the form used by <code class="func">DigraphAllSimpleCircuits</code> (<a href="chap5_mj.html#X7ECD16838704FAAA">5.4-31</a>). Note if <var class="Arg">digraph</var> has 0 or 1 vertices, then <code class="code">HamiltonianPath</code> returns <code class="code">[]</code> or <code class="code">[1]</code>, respectively.

The method used in this attribute has the same worst case complexity as <code class="func">DigraphMonomorphism</code> (<a href="chap7_mj.html#X82D0FCD87D47ACA8">7.3-4</a>).

<div class="example"><pre>
gap> D := Digraph([[]]);
<immutable empty digraph with 1 vertex>
gap> HamiltonianPath(D);
[ 1 ]
gap> D := Digraph([[2], [1]]);
<immutable digraph with 2 vertices, 2 edges>
gap> HamiltonianPath(D);
[ 1, 2 ]
gap> D := Digraph([[3], [], [2]]);
<immutable digraph with 3 vertices, 2 edges>
gap> HamiltonianPath(D);
fail
gap> D := Digraph([[2], [3], [1]]);
<immutable digraph with 3 vertices, 3 edges>
gap> HamiltonianPath(D);
[ 1, 2, 3 ]
gap> D := GeneralisedPetersenGraph(IsMutableDigraph, 5, 2);
<mutable digraph with 10 vertices, 30 edges>
gap> HamiltonianPath(D);
fail
</pre></div>

<a id="X82F30D5681466BC6" name="X82F30D5681466BC6"></a>

<h5>5.4-40 NrSpanningTrees</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ NrSpanningTrees</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
Returns: An integer.

Returns the number of spanning trees of the symmetric digraph <var class="Arg">digraph</var>. <code class="code">NrSpanningTrees</code> will return an error if <var class="Arg">digraph</var> is not a symmetric digraph.

See <code class="func">IsSymmetricDigraph</code> (<a href="chap6_mj.html#X81B3EA7887219860">6.2-14</a>) and <code class="func">IsUndirectedSpanningTree</code> (<a href="chap4_mj.html#X833C3299787E2309">4.1-2</a>) for more information.

<div class="example"><pre>
gap> D := CompleteDigraph(5);
<immutable complete digraph with 5 vertices>
gap> NrSpanningTrees(D);
125
gap> D := DigraphSymmetricClosure(CycleDigraph(24));;
gap> NrSpanningTrees(D);
24
gap> NrSpanningTrees(EmptyDigraph(0));
0
gap> D := GeneralisedPetersenGraph(IsMutableDigraph, 9, 2);
<mutable digraph with 18 vertices, 54 edges>
gap> NrSpanningTrees(D);
1134225
</pre></div>

<a id="X79352A8286D1D8F6" name="X79352A8286D1D8F6"></a>

<h5>5.4-41 DigraphDijkstra</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DigraphDijkstra</code>( <var class="Arg">digraph</var>, <var class="Arg">source</var>, <var class="Arg">target</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DigraphDijkstra</code>( <var class="Arg">digraph</var>, <var class="Arg">source</var> )</td><td class="tdright">( operation )</td></tr></table></div>
Returns: Two lists.

If <var class="Arg">digraph</var> is a digraph and <var class="Arg">source</var> and <var class="Arg">target</var> are vertices of <var class="Arg">digraph</var>, then <code class="code">DigraphDijkstra</code> calculates the length of the shortest path from <var class="Arg">source</var> to <var class="Arg">target</var> and returns two lists. Each element of the first list is the distance of the corresponding element from <var class="Arg">source</var>. If a vertex was not visited in the process of calculating the shortest distance to <var class="Arg">target</var> or if there is no path connecting that vertex with <var class="Arg">source</var>, then the corresponding distance is <code class="keyw">infinity</code>. Each element of the second list gives the previous vertex in the shortest path from <var class="Arg">source</var> to the corresponding vertex. For <var class="Arg">source</var> and for any vertices that remained unvisited this will be <code class="code">-1</code>.

If the optional second argument <var class="Arg">target</var> is not present, then <code class="code">DigraphDijkstra</code> returns the shortest path from <var class="Arg">source</var> to every vertex that is reachable from <var class="Arg">source</var>.

<div class="example"><pre>
gap> mat := [[0, 1, 1], [0, 0, 1], [0, 0, 0]];
[ [ 0, 1, 1 ], [ 0, 0, 1 ], [ 0, 0, 0 ] ]
gap> D := DigraphByAdjacencyMatrix(mat);
<immutable digraph with 3 vertices, 3 edges>
gap> DigraphDijkstra(D, 2, 3);
[ [ infinity, 0, 1 ], [ -1, -1, 2 ] ]
gap> DigraphDijkstra(D, 1, 3);
[ [ 0, 1, 1 ], [ -1, 1, 1 ] ]
gap> DigraphDijkstra(D, 1, 2);
[ [ 0, 1, 1 ], [ -1, 1, 1 ] ]
</pre></div>

<a id="X794CD6037D4CF58C" name="X794CD6037D4CF58C"></a>

<h5>5.4-42 DigraphCycleBasis</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DigraphCycleBasis</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( operation )</td></tr></table></div>
Returns: A list and a list of GF(2) vectors

If <var class="Arg">digraph</var> is a symmetric loopless digraph with no multiple edges, then <code class="code">DigraphCycleBasis</code> calculates the fundamental cycle basis of <var class="Arg">digraph</var> and returns a list of edges and a list of a basis vectors. If <var class="Arg">digraph</var> contains a loop, this function will return an error. If <var class="Arg">digraph</var> is a multi-digraph, then multiple edges incident to the same vertices are treated as a single edge by this function. See <code class="func">IsSymmetricDigraph</code> (<a href="chap6_mj.html#X81B3EA7887219860">6.2-14</a>), <code class="func">DigraphHasLoops</code> (<a href="chap6_mj.html#X7D92935C7D535187">6.2-1</a>), and <code class="func">IsMultiDigraph</code> (<a href="chap6_mj.html#X7BB84CFC7E8B2B26">6.2-11</a>). The first list returned contains the out-neighours that provide the ordering on the edges with the symmetric edges appearing only once; these are the same as OutNeighbours(MaximalAntiSymmetricSubdigraph(G)). See <code class="func">MaximalAntiSymmetricSubdigraph</code> (<a href="chap3_mj.html#X79BA6A66846D5A95">3.3-6</a>) <code class="func">OutNeighbours</code> (<a href="chap5_mj.html#X7E9880767AE68E00">5.2-6</a>). The second list returned contains the basis vectors of the cycle space of the digraph. These vectors belongs to \((GF(2))^m\) where \(m\) is the length of the list of edges.

A graph is eulerian if every vertex has an even degree. A cycle space of a graph is a subspace of \((GF(2))^m\) representing the set of all eulerian subgraphs without isolated vertices. An eulerian subgraph without isolated vertices can be uniquely identified using the edges that is contains. Therefore, given some ordering on the edges of the graph, a subgraph can be represented by a vector in \((GF(2))^m\) where the \(i\)-th entry is \(1\) if the \(i\)-th edge is in the subgraph and \(0\) otherwise. In this function, the ordering of the edges is returned as the first list which corresponds to <code class="code">OutNeighbours(MaximalAntiSymmetricSubdigraph(G))</code>. See <code class="func">MaximalAntiSymmetricSubdigraph</code> (<a href="chap3_mj.html#X79BA6A66846D5A95">3.3-6</a>) and <code class="func">OutNeighbours</code> (<a href="chap5_mj.html#X7E9880767AE68E00">5.2-6</a>). The first basis vector for the complete digraph with 4 vertices shown below represents the edges <code class="code">[1, 2]</code>, <code class="code">[1, 3]</code> and <code class="code">[2, 3]</code> i.e. cycle subgraph between the vertices <code class="code">1</code>, <code class="code">2</code> and <code class="code">3</code> The cycle space is closed under the symmetric difference of the edges of the graph. This nicely corresponds to the addition of vectors in \((GF(2))^m\) which makes the vector space formulation of the cycle space very natural.

A cycle basis is a basis of the cycle space. A fundamental cycle basis is a special kind of basis of the cycle space where there is a specific spanning tree (forest, when the graph is disconnected) of the graph and each basis corresponds to the unique cycle created by adding an edge outside the spanning tree of the graph to the spanning tree. In this function, the spanning forest is rooted in the vertex with the smallest label for each connected component of the graph.

The fundamental cycle basis is unique up to reordering of the basis vectors. The number of basis vectors in the fundamental cycle basis is \(m - n + c\), where \(m\) is the number of edges, \(n\) is the number of vertices, and \(c\) is the number of connected components. See <code class="func">DigraphConnectedComponents</code> (<a href="chap5_mj.html#X842FAD6A7B835977">5.4-9</a>).

This function performs a depth first traversal of the input digraph with complexity \(O(m + n)\) and the complexity of the computation of the basis is \(O(m^2)\) where \(m\) is the number of edges in the input digraph.

<div class="example"><pre>
gap> D := CycleGraph(4);
<immutable symmetric digraph with 4 vertices, 8 edges>
gap> res := DigraphCycleBasis(D);
[ [ [ 2, 4 ], [ 3 ], [ 4 ], [ ] ], [ <a GF2 vector of length 4> ] ]
gap> List(res[2][1]);
[ Z(2)^0, Z(2)^0, Z(2)^0, Z(2)^0 ]
gap> D := CompleteDigraph(4); 
<immutable complete digraph with 4 vertices>
gap> res := DigraphCycleBasis(D);
[ [ [ 2, 3, 4 ], [ 3, 4 ], [ 4 ], [ ] ],
 [ <a GF2 vector of length 6>, <a GF2 vector of length 6>,
 <a GF2 vector of length 6> ] ]
gap> List(res[2][1]); 
[ Z(2)^0, 0*Z(2), Z(2)^0, 0*Z(2), Z(2)^0, 0*Z(2) ]
gap> List(res[2][2]);
[ 0*Z(2), Z(2)^0, Z(2)^0, 0*Z(2), 0*Z(2), Z(2)^0 ]
gap> List(res[2][3]);
[ Z(2)^0, Z(2)^0, 0*Z(2), Z(2)^0, 0*Z(2), 0*Z(2) ]
</pre></div>

<a id="X835AAF9085BC9D84" name="X835AAF9085BC9D84"></a>

<h5>5.4-43 DigraphIsKing</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DigraphIsKing</code>( <var class="Arg">D</var>, <var class="Arg">v</var>, <var class="Arg">k</var> )</td><td class="tdright">( operation )</td></tr></table></div>
Returns: <code class="keyw">true</code> or <code class="keyw">false</code>.

If <var class="Arg">D</var> is a tournament and <var class="Arg">v</var> is a vertex in the tournament, then this operation returns <code class="keyw">true</code> if every other vertex of <var class="Arg">D</var> is reachable from <var class="Arg">v</var> by a path of length at most <var class="Arg">k</var>. Otherwise, an error is given. If <code class="keyw">true</code> is returned, then the vertex, <var class="Arg">v</var>, is a <var class="Arg">k</var>-king.

<div class="example"><pre>
gap> gr := Digraph([[2, 3, 4], [3, 5], [5], [2, 3], [1, 4]]);
<immutable digraph with 5 vertices, 10 edges>
gap> DigraphIsKing(gr, 2, 2);
true
gap> DigraphIsKing(gr, 3, 2);
false
gap> OutNeighboursOfVertex(gr, 3);
[ 5 ]
gap> OutNeighboursOfVertex(gr, 5);
[ 1, 4 ]
gap> Union(last, last2);
[ 1, 4, 5 ]
gap> DigraphIsKing(gr, 3, 4);
true</pre></div>

<a id="X7A17B9B67AC50561" name="X7A17B9B67AC50561"></a>

<h5>5.4-44 DigraphKings</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DigraphKings</code>( <var class="Arg">D</var>, <var class="Arg">n</var> )</td><td class="tdright">( operation )</td></tr></table></div>
Returns: A list.

If <var class="Arg">D</var> is a tournament, then this operation returns a list of the <var class="Arg">n</var>-kings in the tournament (see <code class="func">DigraphIsKing</code> (<a href="chap5_mj.html#X835AAF9085BC9D84">5.4-43</a>)).

If <var class="Arg">D</var> is not tournament, then an error is given (see <code class="func">IsTournament</code> (<a href="chap6_mj.html#X7DD8D1A185EBE865">6.2-15</a>)). If the tournament contains a source, then the source is the only 2-king (see <code class="func">DigraphSources</code> (<a href="chap5_mj.html#X7F5C6268839BE98C">5.1-9</a>)). The number of 2-kings in a tournament without a source is at least three. A tournament cannot have exactly two 2-kings.

<div class="example"><pre>
gap> gr := Digraph([[2, 3, 4], [3, 5], [5], [2, 3], [1, 4]]);
<immutable digraph with 5 vertices, 10 edges>
gap> DigraphKings(gr, 2);
[ 1, 2, 5 ]
gap> gr := Digraph([[2, 3, 4, 5], [3, 5], [5], [2, 3], [4]]);
<immutable digraph with 5 vertices, 10 edges>
gap> DigraphSources(gr);
[ 1 ]
gap> DigraphKings(gr, 2);
[ 1 ]</pre></div>

<a id="X82F900777D677F55" name="X82F900777D677F55"></a>

<h4>5.5 Cayley graphs of groups</h4>

<a id="X7A000B1D7CCF7093" name="X7A000B1D7CCF7093"></a>

<h5>5.5-1 GroupOfCayleyDigraph</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ GroupOfCayleyDigraph</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ SemigroupOfCayleyDigraph</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
Returns: A group or semigroup.

If <var class="Arg">digraph</var> is an immutable Cayley graph of a group <code class="code">G</code> and <var class="Arg">digraph</var> belongs to the category <code class="func">IsCayleyDigraph</code> (<a href="chap3_mj.html#X7E749324800B38A5">3.1-4</a>), then <code class="code">GroupOfCayleyDigraph</code> returns <code class="code">G</code>.

If <var class="Arg">digraph</var> is a Cayley graph of a semigroup <code class="code">S</code> and <var class="Arg">digraph</var> belongs to the category <code class="func">IsCayleyDigraph</code> (<a href="chap3_mj.html#X7E749324800B38A5">3.1-4</a>), then <code class="code">SemigroupOfCayleyDigraph</code> returns <code class="code">S</code>.

See also <code class="func">GeneratorsOfCayleyDigraph</code> (<a href="chap5_mj.html#X8528455987D7D2BF">5.5-2</a>).

<div class="example"><pre>
gap> G := DihedralGroup(IsPermGroup, 8);
Group([ (1,2,3,4), (2,4) ])
gap> digraph := CayleyDigraph(G);
<immutable digraph with 8 vertices, 16 edges>
gap> GroupOfCayleyDigraph(digraph) = G;
true
</pre></div>

<a id="X8528455987D7D2BF" name="X8528455987D7D2BF"></a>

<h5>5.5-2 GeneratorsOfCayleyDigraph</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ GeneratorsOfCayleyDigraph</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
Returns: A list of generators.

If <var class="Arg">digraph</var> is an immutable Cayley graph of a group or semigroup with respect to a set of generators <code class="code">gens</code> and <var class="Arg">digraph</var> belongs to the category <code class="func">IsCayleyDigraph</code> (<a href="chap3_mj.html#X7E749324800B38A5">3.1-4</a>), then <code class="code">GeneratorsOfCayleyDigraph</code> return the list of generators <code class="code">gens</code> over which <var class="Arg">digraph</var> is defined.

See also <code class="func">GroupOfCayleyDigraph</code> (<a href="chap5_mj.html#X7A000B1D7CCF7093">5.5-1</a>) or <code class="func">SemigroupOfCayleyDigraph</code> (<a href="chap5_mj.html#X7A000B1D7CCF7093">5.5-1</a>).

<div class="example"><pre>
gap> G := DihedralGroup(IsPermGroup, 8);
Group([ (1,2,3,4), (2,4) ])
gap> digraph := CayleyDigraph(G);
<immutable digraph with 8 vertices, 16 edges>
gap> GeneratorsOfCayleyDigraph(digraph) = GeneratorsOfGroup(G);
true
gap> digraph := CayleyDigraph(G, [()]);
<immutable digraph with 8 vertices, 8 edges>
gap> GeneratorsOfCayleyDigraph(digraph) = [()];
true</pre></div>

<a id="X790FD6647ECCAE3C" name="X790FD6647ECCAE3C"></a>

<h4>5.6 Associated semigroups</h4>

<a id="X87D5C60D7B0C1309" name="X87D5C60D7B0C1309"></a>

<h5>5.6-1 AsSemigroup</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ AsSemigroup</code>( <var class="Arg">filt</var>, <var class="Arg">digraph</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ AsMonoid</code>( <var class="Arg">filt</var>, <var class="Arg">digraph</var> )</td><td class="tdright">( operation )</td></tr></table></div>
Returns: A semilattice of partial perms.

The operation <code class="code">AsSemigroup</code> requires that <var class="Arg">filt</var> be equal to <code class="func">IsPartialPermSemigroup</code> (<a href="/home/runner/gap/doc/ref/chap54_mj.html#X7D161674800B50E0">Reference: IsPartialPermSemigroup</a>). If <var class="Arg">digraph</var> is a <code class="func">IsJoinSemilatticeDigraph</code> (<a href="chap6_mj.html#X78D3E17B7F737516">6.4-3</a>) or <code class="func">IsLatticeDigraph</code> (<a href="chap6_mj.html#X78D3E17B7F737516">6.4-3</a>) then <code class="code">AsSemigroup</code> returns a semigroup of partial perms which is isomorphic to the semigroup whose elements are the vertices of <var class="Arg">digraph</var> with the binary operation <code class="func">PartialOrderDigraphJoinOfVertices</code> (<a href="chap5_mj.html#X7DDB33B686B3A2C6">5.3-1</a>). If <var class="Arg">digraph</var> satisfies <code class="func">IsMeetSemilatticeDigraph</code> (<a href="chap6_mj.html#X78D3E17B7F737516">6.4-3</a>) but not <code class="func">IsJoinSemilatticeDigraph</code> (<a href="chap6_mj.html#X78D3E17B7F737516">6.4-3</a>) then <code class="code">AsSemigroup</code> returns a semigroup of partial perms which is isomorphic to the semigroup whose elements are the vertices of <var class="Arg">digraph</var> with the binary operation <code class="func">PartialOrderDigraphMeetOfVertices</code> (<a href="chap5_mj.html#X7DDB33B686B3A2C6">5.3-1</a>).

The operation <code class="code">AsMonoid</code> behaves similarly to <code class="code">AsSemigroup</code> except that <var class="Arg">filt</var> may also be equal to <code class="func">IsPartialPermMonoid</code> (<a href="/home/runner/gap/doc/ref/chap54_mj.html#X7D161674800B50E0">Reference: IsPartialPermMonoid</a>), <var class="Arg">digraph</var> must satisfy <code class="func">IsLatticeDigraph</code> (<a href="chap6_mj.html#X78D3E17B7F737516">6.4-3</a>), and the output satisfies <code class="func">IsMonoid</code> (<a href="/home/runner/gap/doc/ref/chap51_mj.html#X861C523483C6248C">Reference: IsMonoid</a>).

The output of both of these operations is guaranteed to be of minimal degree (see <code class="func">DegreeOfPartialPermSemigroup</code> (<a href="/home/runner/gap/doc/ref/chap54_mj.html#X7D7F0BAB82F0D820">Reference: DegreeOfPartialPermSemigroup</a>)). Furthermore the <code class="func">GeneratorsOfSemigroup</code> (<a href="/home/runner/gap/doc/ref/chap51_mj.html#X78147A247963F23B">Reference: GeneratorsOfSemigroup</a>) of the output is guaranteed to be the unique generating set of minimal size.

<div class="example"><pre>
gap> di := Digraph([[1], [1, 2], [1, 3], [1, 4], [1, 2, 3, 5]]);
<immutable digraph with 5 vertices, 11 edges>
gap> S := AsSemigroup(IsPartialPermSemigroup, di);
<partial perm semigroup of rank 3 with 4 generators>
gap> ForAll(Elements(S), IsIdempotent);
true
gap> IsInverseSemigroup(S);
true
gap> Size(S);
5
gap> di := Digraph([[1], [1, 2], [1, 2, 3]]);
<immutable digraph with 3 vertices, 6 edges>
gap> M := AsMonoid(IsPartialPermMonoid, di);
<partial perm monoid of rank 2 with 3 generators>
gap> Size(M);
3</pre></div>

<a id="X7C6D5EC27C51066B" name="X7C6D5EC27C51066B"></a>

<h5>5.6-2 AsSemigroup</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ AsSemigroup</code>( <var class="Arg">filt</var>, <var class="Arg">Y</var>, <var class="Arg">gps</var>, <var class="Arg">homs</var> )</td><td class="tdright">( operation )</td></tr></table></div>
Returns: A Clifford semigroup of partial perms.

The operation <code class="code">AsSemigroup</code> requires that <var class="Arg">filt</var> be equal to <code class="func">IsPartialPermSemigroup</code> (<a href="/home/runner/gap/doc/ref/chap54_mj.html#X7D161674800B50E0">Reference: IsPartialPermSemigroup</a>). If <var class="Arg">Y</var> is a <code class="func">IsJoinSemilatticeDigraph</code> (<a href="chap6_mj.html#X78D3E17B7F737516">6.4-3</a>) or <code class="func">IsMeetSemilatticeDigraph</code> (<a href="chap6_mj.html#X78D3E17B7F737516">6.4-3</a>), <var class="Arg">gps</var> is a list of groups corresponding to each vertex, and <var class="Arg">homs</var> is a list containing for each edge <code class="code">(i, j)</code> in the transitive reduction of <var class="Arg">digraph</var> a triple <code class="code">[i, j, hom]</code> where <code class="code">hom</code> is a group homomorphism from <code class="code">gps[i]</code> to <code class="code">gps[j]</code>, and the diagram of homomorphisms commutes, then <code class="code">AsSemigroup</code> returns a semigroup of partial perms which is isomorphic to the strong semilattice of groups \(S[Y; gps; homs]\).

<div class="example"><pre>
gap> G1 := AlternatingGroup(4);;
gap> G2 := SymmetricGroup(2);;
gap> G3 := SymmetricGroup(3);;
gap> gr := Digraph([[1, 3], [2, 3], [3]]);;
gap> sgn := function(x)
> if SignPerm(x) = 1 then
> return ();
> fi;
> return (1, 2);
> end;;
gap> hom13 := GroupHomomorphismByFunction(G1, G3, sgn);;
gap> hom23 := GroupHomomorphismByFunction(G2, G3, sgn);;
gap> T := AsSemigroup(IsPartialPermSemigroup,
> gr,
> [G1, G2, G3], [[1, 3, hom13], [2, 3, hom23]]);;
gap> Size(T);
20
gap> D := GreensDClasses(T);;
gap> List(D, Size);
[ 6, 12, 2 ]
</pre></div>

<a id="X7E2305528492DDC0" name="X7E2305528492DDC0"></a>

<h4>5.7 Planarity</h4>

<a id="X7DC478637E8C190D" name="X7DC478637E8C190D"></a>

<h5>5.7-1 KuratowskiPlanarSubdigraph</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ KuratowskiPlanarSubdigraph</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
Returns: A list or <code class="keyw">fail</code>.

<code class="code">KuratowskiPlanarSubdigraph</code> returns the immutable list of lists of out-neighbours of an induced subdigraph (excluding multiple edges and loops) of the digraph <var class="Arg">digraph</var> that witnesses the fact that <var class="Arg">digraph</var> is not planar, or <code class="keyw">fail</code> if <var class="Arg">digraph</var> is planar. In other words, <code class="code">KuratowskiPlanarSubdigraph</code> returns the out-neighbours of a subdigraph of <var class="Arg">digraph</var> that is homeomorphic to the complete graph with <code class="code">5</code> vertices, or to the complete bipartite graph with vertex sets of sizes <code class="code">3</code> and <code class="code">3</code>.

The directions and multiplicities of any edges in <var class="Arg">digraph</var> are ignored when considering whether or not <var class="Arg">digraph</var> is planar.

See also <code class="func">IsPlanarDigraph</code> (<a href="chap6_mj.html#X8606D415858C40AA">6.7-1</a>) and <code class="func">SubdigraphHomeomorphicToK33</code> (<a href="chap5_mj.html#X806D2D6B85E0B269">5.7-5</a>).

This method uses the reference implementation in <a href="https://github.com/graph-algorithms/edge-addition-planarity-suite">edge-addition-planarity-suite</a> by John Boyer of the algorithms described in <a href="chapBib_mj.html#biBBM06">[BM06]</a>.

<div class="example"><pre>
gap> D := Digraph([[3, 5, 10], [8, 9, 10], [1, 4], [3, 6], 
> [1, 7, 11], [4, 7], [6, 8], [2, 7], [2, 11], [1, 2], [5, 9]]);
<immutable digraph with 11 vertices, 25 edges>
gap> KuratowskiPlanarSubdigraph(D);
fail
gap> D := Digraph([[2, 4, 7, 9, 10], [1, 3, 4, 6, 9, 10], [6, 10], 
> [2, 5, 8, 9], [1, 2, 3, 4, 6, 7, 9, 10], [3, 4, 5, 7, 9, 10], 
> [3, 4, 5, 6, 9, 10], [3, 4, 5, 7, 9], [2, 3, 5, 6, 7, 8], [3, 5]]);
<immutable digraph with 10 vertices, 50 edges>
gap> IsPlanarDigraph(D);
false
gap> KuratowskiPlanarSubdigraph(D);
[ [ 2, 9, 7 ], [ 1, 3 ], [ 6 ], [ 5, 9 ], [ 6, 4 ], [ 3, 5 ], [ 4 ],
 [ 7, 9, 3 ], [ 8 ], [ ] ]
gap> D := Digraph(IsMutableDigraph, [[3, 5, 10], [8, 9, 10], [1, 4],
> [3, 6], [1, 7, 11], [4, 7], [6, 8], [2, 7], [2, 11], [1, 2], [5, 9]]);
<mutable digraph with 11 vertices, 25 edges>
gap> KuratowskiPlanarSubdigraph(D);
fail
gap> D := Digraph(IsMutableDigraph, [[2, 4, 7, 9, 10],
> [1, 3, 4, 6, 9, 10], [6, 10], [2, 5, 8, 9],
> [1, 2, 3, 4, 6, 7, 9, 10], [3, 4, 5, 7, 9, 10],
> [3, 4, 5, 6, 9, 10], [3, 4, 5, 7, 9], [2, 3, 5, 6, 7, 8], [3, 5]]);
<mutable digraph with 10 vertices, 50 edges>
gap> IsPlanarDigraph(D);
false
gap> KuratowskiPlanarSubdigraph(D);
[ [ 2, 9, 7 ], [ 1, 3 ], [ 6 ], [ 5, 9 ], [ 6, 4 ], [ 3, 5 ], [ 4 ],
 [ 7, 9, 3 ], [ 8 ], [ ] ]
</pre></div>

<a id="X78E8F09A8286501B" name="X78E8F09A8286501B"></a>

<h5>5.7-2 KuratowskiOuterPlanarSubdigraph</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ KuratowskiOuterPlanarSubdigraph</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
Returns: A list or <code class="keyw">fail</code>.

<code class="code">KuratowskiOuterPlanarSubdigraph</code> returns the immutable list of immutable lists of out-neighbours of an induced subdigraph (excluding multiple edges and loops) of the digraph <var class="Arg">digraph</var> that witnesses the fact that <var class="Arg">digraph</var> is not outer planar, or <code class="keyw">fail</code> if <var class="Arg">digraph</var> is outer planar. In other words, <code class="code">KuratowskiOuterPlanarSubdigraph</code> returns the out-neighbours of a subdigraph of <var class="Arg">digraph</var> that is homeomorphic to the complete graph with <code class="code">4</code> vertices, or to the complete bipartite graph with vertex sets of sizes <code class="code">2</code> and <code class="code">3</code>.

The directions and multiplicities of any edges in <var class="Arg">digraph</var> are ignored when considering whether or not <var class="Arg">digraph</var> is outer planar.

See also <code class="func">IsOuterPlanarDigraph</code> (<a href="chap6_mj.html#X8251E8B187E7F059">6.7-2</a>), <code class="func">SubdigraphHomeomorphicToK4</code> (<a href="chap5_mj.html#X806D2D6B85E0B269">5.7-5</a>), and <code class="func">SubdigraphHomeomorphicToK23</code> (<a href="chap5_mj.html#X806D2D6B85E0B269">5.7-5</a>).

This method uses the reference implementation in <a href="https://github.com/graph-algorithms/edge-addition-planarity-suite">edge-addition-planarity-suite</a> by John Boyer of the algorithms described in <a href="chapBib_mj.html#biBBM06">[BM06]</a>.

<div class="example"><pre>
gap> D := Digraph([[3, 5, 10], [8, 9, 10], [1, 4], [3, 6], 
> [1, 7, 11], [4, 7], [6, 8], [2, 7], [2, 11], [1, 2], [5, 9]]);
<immutable digraph with 11 vertices, 25 edges>
gap> KuratowskiOuterPlanarSubdigraph(D);
[ [ 3, 5, 10 ], [ 9, 8, 10 ], [ 4, 1 ], [ 6, 3 ], [ 1, 11 ],
 [ 7, 4 ], [ 8, 6 ], [ 2, 7 ], [ 11, 2 ], [ 2, 1 ], [ 5, 9 ] ]
gap> D := Digraph([[2, 4, 7, 9, 10], [1, 3, 4, 6, 9, 10], [6, 10], 
> [2, 5, 8, 9], [1, 2, 3, 4, 6, 7, 9, 10], [3, 4, 5, 7, 9, 10], 
> [3, 4, 5, 6, 9, 10], [3, 4, 5, 7, 9], [2, 3, 5, 6, 7, 8], [3, 5]]);
<immutable digraph with 10 vertices, 50 edges>
gap> IsOuterPlanarDigraph(D);
false
gap> KuratowskiOuterPlanarSubdigraph(D);
[ [ ], [ ], [ ], [ 8, 9 ], [ ], [ ], [ 9, 4 ], [ 7, 9, 4 ],
 [ 8, 7 ], [ ] ]
gap> D := Digraph(IsMutableDigraph, [[3, 5, 10], [8, 9, 10], [1, 4],
> [3, 6], [1, 7, 11], [4, 7], [6, 8], [2, 7], [2, 11], [1, 2], [5, 9]]);
<mutable digraph with 11 vertices, 25 edges>
gap> KuratowskiOuterPlanarSubdigraph(D);
[ [ 3, 5, 10 ], [ 9, 8, 10 ], [ 4, 1 ], [ 6, 3 ], [ 1, 11 ],
 [ 7, 4 ], [ 8, 6 ], [ 2, 7 ], [ 11, 2 ], [ 2, 1 ], [ 5, 9 ] ]
gap> D := Digraph(IsMutableDigraph, [[2, 4, 7, 9, 10],
> [1, 3, 4, 6, 9, 10], [6, 10], [2, 5, 8, 9],
> [1, 2, 3, 4, 6, 7, 9, 10], [3, 4, 5, 7, 9, 10],
> [3, 4, 5, 6, 9, 10], [3, 4, 5, 7, 9], [2, 3, 5, 6, 7, 8], [3, 5]]);
<mutable digraph with 10 vertices, 50 edges>
gap> IsOuterPlanarDigraph(D);
false
gap> KuratowskiOuterPlanarSubdigraph(D);
[ [ ], [ ], [ ], [ 8, 9 ], [ ], [ ], [ 9, 4 ], [ 7, 9, 4 ],
 [ 8, 7 ], [ ] ]</pre></div>

<a id="X84E3947E7D39BA64" name="X84E3947E7D39BA64"></a>

<h5>5.7-3 PlanarEmbedding</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ PlanarEmbedding</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
Returns: A list or <code class="keyw">fail</code>.

If <var class="Arg">digraph</var> is a planar digraph, then <code class="code">PlanarEmbedding</code> returns the immutable list of lists of out-neighbours of <var class="Arg">digraph</var> (excluding multiple edges and loops) such that each vertex's neighbours are given in clockwise order. If <var class="Arg">digraph</var> is not planar, then <code class="keyw">fail</code> is returned.

The directions and multiplicities of any edges in <var class="Arg">digraph</var> are ignored by <code class="code">PlanarEmbedding</code>.

See also <code class="func">IsPlanarDigraph</code> (<a href="chap6_mj.html#X8606D415858C40AA">6.7-1</a>).

This method uses the reference implementation in <a href="https://github.com/graph-algorithms/edge-addition-planarity-suite">edge-addition-planarity-suite</a> by John Boyer of the algorithms described in <a href="chapBib_mj.html#biBBM06">[BM06]</a>.

<div class="example"><pre>
gap> D := Digraph([[3, 5, 10], [8, 9, 10], [1, 4], [3, 6], 
> [1, 7, 11], [4, 7], [6, 8], [2, 7], [2, 11], [1, 2], [5, 9]]);
<immutable digraph with 11 vertices, 25 edges>
gap> PlanarEmbedding(D);
[ [ 3, 10, 5 ], [ 10, 8, 9 ], [ 4, 1 ], [ 6, 3 ], [ 1, 11, 7 ],
 [ 7, 4 ], [ 8, 6 ], [ 7, 2 ], [ 2, 11 ], [ 1, 2 ], [ 9, 5 ] ]
gap> D := Digraph([[2, 4, 7, 9, 10], [1, 3, 4, 6, 9, 10], [6, 10], 
> [2, 5, 8, 9], [1, 2, 3, 4, 6, 7, 9, 10], [3, 4, 5, 7, 9, 10], 
> [3, 4, 5, 6, 9, 10], [3, 4, 5, 7, 9], [2, 3, 5, 6, 7, 8], [3, 5]]);
<immutable digraph with 10 vertices, 50 edges>
gap> PlanarEmbedding(D);
fail
gap> D := Digraph(IsMutableDigraph, [[3, 5, 10], [8, 9, 10], [1, 4],
> [3, 6], [1, 7, 11], [4, 7], [6, 8], [2, 7], [2, 11], [1, 2], [5, 9]]);
<mutable digraph with 11 vertices, 25 edges>
gap> PlanarEmbedding(D);
[ [ 3, 10, 5 ], [ 10, 8, 9 ], [ 4, 1 ], [ 6, 3 ], [ 1, 11, 7 ],
 [ 7, 4 ], [ 8, 6 ], [ 7, 2 ], [ 2, 11 ], [ 1, 2 ], [ 9, 5 ] ]
gap> D := Digraph(IsMutableDigraph, [[2, 4, 7, 9, 10],
> [1, 3, 4, 6, 9, 10], [6, 10], [2, 5, 8, 9],
> [1, 2, 3, 4, 6, 7, 9, 10], [3, 4, 5, 7, 9, 10],
> [3, 4, 5, 6, 9, 10], [3, 4, 5, 7, 9], [2, 3, 5, 6, 7, 8], [3, 5]]);
<mutable digraph with 10 vertices, 50 edges>
gap> PlanarEmbedding(D);
fail
</pre></div>

<a id="X85DFB8C18088711F" name="X85DFB8C18088711F"></a>

<h5>5.7-4 OuterPlanarEmbedding</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ OuterPlanarEmbedding</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
Returns: A list or <code class="keyw">fail</code>.

If <var class="Arg">digraph</var> is an outer planar digraph, then <code class="code">OuterPlanarEmbedding</code> returns the immutable list of lists of out-neighbours of <var class="Arg">digraph</var> (excluding multiple edges and loops) such that each vertex's neighbours are given in clockwise order. If <var class="Arg">digraph</var> is not outer planar, then <code class="keyw">fail</code> is returned.

The directions and multiplicities of any edges in <var class="Arg">digraph</var> are ignored by <code class="code">OuterPlanarEmbedding</code>.

See also <code class="func">IsOuterPlanarDigraph</code> (<a href="chap6_mj.html#X8251E8B187E7F059">6.7-2</a>).

This method uses the reference implementation in <a href="https://github.com/graph-algorithms/edge-addition-planarity-suite">edge-addition-planarity-suite</a> by John Boyer of the algorithms described in <a href="chapBib_mj.html#biBBM06">[BM06]</a>.

<div class="example"><pre>
gap> D := Digraph([[3, 5, 10], [8, 9, 10], [1, 4], [3, 6], 
> [1, 7, 11], [4, 7], [6, 8], [2, 7], [2, 11], [1, 2], [5, 9]]);
<immutable digraph with 11 vertices, 25 edges>
gap> OuterPlanarEmbedding(D);
fail
gap> D := Digraph([[2, 4, 7, 9, 10], [1, 3, 4, 6, 9, 10], [6, 10], 
> [2, 5, 8, 9], [1, 2, 3, 4, 6, 7, 9, 10], [3, 4, 5, 7, 9, 10], 
> [3, 4, 5, 6, 9, 10], [3, 4, 5, 7, 9], [2, 3, 5, 6, 7, 8], [3, 5]]);
<immutable digraph with 10 vertices, 50 edges>
gap> OuterPlanarEmbedding(D);
fail
gap> OuterPlanarEmbedding(CompleteBipartiteDigraph(2, 2));
[ [ 3, 4 ], [ 4, 3 ], [ 2, 1 ], [ 1, 2 ] ]
gap> D := Digraph(IsMutableDigraph, [[3, 5, 10], [8, 9, 10], [1, 4],
> [3, 6], [1, 7, 11], [4, 7], [6, 8], [2, 7], [2, 11], [1, 2], [5, 9]]);
<mutable digraph with 11 vertices, 25 edges>
gap> OuterPlanarEmbedding(D);
fail
gap> D := Digraph(IsMutableDigraph, [[2, 4, 7, 9, 10],
> [1, 3, 4, 6, 9, 10], [6, 10], [2, 5, 8, 9],
> [1, 2, 3, 4, 6, 7, 9, 10], [3, 4, 5, 7, 9, 10],
> [3, 4, 5, 6, 9, 10], [3, 4, 5, 7, 9], [2, 3, 5, 6, 7, 8], [3, 5]]);
<mutable digraph with 10 vertices, 50 edges>
gap> OuterPlanarEmbedding(D);
fail
gap> OuterPlanarEmbedding(CompleteBipartiteDigraph(2, 2));
[ [ 3, 4 ], [ 4, 3 ], [ 2, 1 ], [ 1, 2 ] ]
</pre></div>

<a id="X806D2D6B85E0B269" name="X806D2D6B85E0B269"></a>

<h5>5.7-5 SubdigraphHomeomorphicToK23</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ SubdigraphHomeomorphicToK23</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ SubdigraphHomeomorphicToK33</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ SubdigraphHomeomorphicToK4</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
Returns: A list or <code class="keyw">fail</code>.

These attributes return the immutable list of lists of out-neighbours of a subdigraph of the digraph <var class="Arg">digraph</var> which is homeomorphic to one of the following: the complete bipartite graph with vertex sets of sizes <code class="code">2</code> and <code class="code">3</code>; the complete bipartite graph with vertex sets of sizes <code class="code">3</code> and <code class="code">3</code>; or the complete graph with <code class="code">4</code> vertices. If <var class="Arg">digraph</var> has no such subdigraphs, then <code class="keyw">fail</code> is returned.

See also <code class="func">IsPlanarDigraph</code> (<a href="chap6_mj.html#X8606D415858C40AA">6.7-1</a>) and <code class="func">IsOuterPlanarDigraph</code> (<a href="chap6_mj.html#X8251E8B187E7F059">6.7-2</a>) for more details.

This method uses the reference implementation in <a href="https://github.com/graph-algorithms/edge-addition-planarity-suite">edge-addition-planarity-suite</a> by John Boyer of the algorithms described in <a href="chapBib_mj.html#biBBM06">[BM06]</a>.

<div class="example"><pre>
gap> D := Digraph([[3, 5, 10], [8, 9, 10], [1, 4], [3, 6], [1, 7, 11], 
> [4, 7], [6, 8], [2, 7], [2, 11], [1, 2], [5, 9]]);
<immutable digraph with 11 vertices, 25 edges>
gap> SubdigraphHomeomorphicToK4(D);
[ [ 3, 5, 10 ], [ 9, 8, 10 ], [ 4, 1 ], [ 6, 3 ], [ 1, 7, 11 ],
 [ 7, 4 ], [ 8, 6 ], [ 2, 7 ], [ 11, 2 ], [ 2, 1 ], [ 5, 9 ] ]
gap> SubdigraphHomeomorphicToK23(D);
[ [ 3, 5, 10 ], [ 9, 8, 10 ], [ 4, 1 ], [ 6, 3 ], [ 1, 11 ],
 [ 7, 4 ], [ 8, 6 ], [ 2, 7 ], [ 11, 2 ], [ 2, 1 ], [ 5, 9 ] ]
gap> D := Digraph([[3, 5, 10], [8, 9, 10], [1, 4], [3, 6], [1, 11], 
> [4, 7], [6, 8], [2, 7], [2, 11], [1, 2], [5, 9]]);
<immutable digraph with 11 vertices, 24 edges>
gap> SubdigraphHomeomorphicToK4(D);
fail
gap> SubdigraphHomeomorphicToK23(D);
[ [ 3, 10, 5 ], [ 10, 8, 9 ], [ 4, 1 ], [ 6, 3 ], [ 11, 1 ],
 [ 7, 4 ], [ 8, 6 ], [ 2, 7 ], [ 2, 11 ], [ 1, 2 ], [ 9, 5 ] ]
gap> SubdigraphHomeomorphicToK33(D);
fail
gap> SubdigraphHomeomorphicToK23(NullDigraph(0));
fail
gap> SubdigraphHomeomorphicToK33(CompleteDigraph(5));
fail
gap> SubdigraphHomeomorphicToK33(CompleteBipartiteDigraph(3, 3));
[ [ 4, 6, 5 ], [ 4, 5, 6 ], [ 6, 5, 4 ], [ 1, 2, 3 ], [ 3, 2, 1 ],
 [ 2, 3, 1 ] ]
gap> SubdigraphHomeomorphicToK4(CompleteDigraph(3));
fail
gap> D := Digraph(IsMutableDigraph, [[3, 5, 10], [8, 9, 10], [1, 4],
> [3, 6], [1, 7, 11], [4, 7], [6, 8], [2, 7], [2, 11], [1, 2], [5, 9]]);
<mutable digraph with 11 vertices, 25 edges>
gap> SubdigraphHomeomorphicToK4(D);
[ [ 3, 5, 10 ], [ 9, 8, 10 ], [ 4, 1 ], [ 6, 3 ], [ 1, 7, 11 ],
 [ 7, 4 ], [ 8, 6 ], [ 2, 7 ], [ 11, 2 ], [ 2, 1 ], [ 5, 9 ] ]
gap> SubdigraphHomeomorphicToK23(D);
[ [ 3, 5, 10 ], [ 9, 8, 10 ], [ 4, 1 ], [ 6, 3 ], [ 1, 11 ],
 [ 7, 4 ], [ 8, 6 ], [ 2, 7 ], [ 11, 2 ], [ 2, 1 ], [ 5, 9 ] ]
gap> D := Digraph(IsMutableDigraph, [[3, 5, 10], [8, 9, 10], [1, 4],
> [3, 6], [1, 11], [4, 7], [6, 8], [2, 7], [2, 11], [1, 2], [5, 9]]);
<mutable digraph with 11 vertices, 24 edges>
gap> SubdigraphHomeomorphicToK4(D);
fail
gap> SubdigraphHomeomorphicToK23(D);
[ [ 3, 10, 5 ], [ 10, 8, 9 ], [ 4, 1 ], [ 6, 3 ], [ 11, 1 ],
 [ 7, 4 ], [ 8, 6 ], [ 2, 7 ], [ 2, 11 ], [ 1, 2 ], [ 9, 5 ] ]
gap> SubdigraphHomeomorphicToK33(D);
fail
gap> SubdigraphHomeomorphicToK23(NullDigraph(0));
fail
gap> SubdigraphHomeomorphicToK33(CompleteDigraph(5));
fail
gap> SubdigraphHomeomorphicToK33(CompleteBipartiteDigraph(3, 3));
[ [ 4, 6, 5 ], [ 4, 5, 6 ], [ 6, 5, 4 ], [ 1, 2, 3 ], [ 3, 2, 1 ],
 [ 2, 3, 1 ] ]
gap> SubdigraphHomeomorphicToK4(CompleteDigraph(3));
fail
</pre></div>

<a id="X876803517C34E1CD" name="X876803517C34E1CD"></a>

<h5>5.7-6 DualPlanarGraph</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DualPlanarGraph</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
Returns: A digraph or <code class="keyw">fail</code>.

If <var class="Arg">digraph</var> is a planar digraph, then <code class="func">DualPlanarGraph</code> returns the the dual graph of <var class="Arg">digraph</var>. If <var class="Arg">digraph</var> is not planar, then <code class="keyw">fail</code> is returned.

The dual graph of a planar digraph <var class="Arg">digraph</var> has a vertex for each face of <var class="Arg">digraph</var> and an edge for each pair of faces that are separated by an edge from each other. Vertex <var class="Arg">i</var> of the dual graph corresponds to the facial walk at the <var class="Arg">i</var>-th position calling <code class="func">FacialWalks</code> (<a href="chap5_mj.html#X805F15398735AD7D">5.4-35</a>) of <var class="Arg">digraph</var> with the rotation system returned by <code class="func">PlanarEmbedding</code> (<a href="chap5_mj.html#X84E3947E7D39BA64">5.7-3</a>).

Note that <code class="func">PlanarEmbedding</code> (<a href="chap5_mj.html#X84E3947E7D39BA64">5.7-3</a>), and therefore <code class="func">DualPlanarGraph</code>, uses the reference implementation in <a href="https://github.com/graph-algorithms/edge-addition-planarity-suite">edge-addition-planarity-suite</a> by John Boyer of the algorithms described in <a href="chapBib_mj.html#biBBM06">[BM06]</a>.

<div class="example"><pre>
gap> D := CompleteDigraph(4);;
gap> dualD := DualPlanarGraph(D);
<immutable digraph with 4 vertices, 12 edges>
gap> IsIsomorphicDigraph(D, dualD);
true
gap> cube := Digraph([[2, 4, 5], [1, 3, 6], [2, 4, 7], [1, 3, 8], 
> [1, 6, 8], [2, 5, 7], [3, 6, 8], [4, 5, 7]]);
<immutable digraph with 8 vertices, 24 edges>
gap> oct := DualPlanarGraph(cube);;
gap> IsIsomorphicDigraph(oct, CompleteMultipartiteDigraph([2, 2, 2]));
true
</pre></div>

<a id="X7FF5E2D07D48647E" name="X7FF5E2D07D48647E"></a>

<h4>5.8 Hashing</h4>

<a id="X7D97D990867B0149" name="X7D97D990867B0149"></a>

<h5>5.8-1 DigraphHash</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DigraphHash</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
Returns: The hash of a digraph.

This function returns a hash of <var class="Arg">digraph</var>.

Note that the underlying hashing function is system dependent, and so the value of this attribute is not guaranteed to be the same on different systems.

<div class="chlinkprevnextbot"> <a href="chap0_mj.html">[Top of Book]</a> <a href="chap0_mj.html#contents">[Contents]</a> <a href="chap4_mj.html">[Previous Chapter]</a> <a href="chap6_mj.html">[Next Chapter]</a> </div>

<div class="chlinkbot">Goto Chapter: <a href="chap0_mj.html">Top</a> <a href="chap1_mj.html">1</a> <a href="chap2_mj.html">2</a> <a href="chap3_mj.html">3</a> <a href="chap4_mj.html">4</a> <a href="chap5_mj.html">5</a> <a href="chap6_mj.html">6</a> <a href="chap7_mj.html">7</a> <a href="chap8_mj.html">8</a> <a href="chap9_mj.html">9</a> <a href="chapA_mj.html">A</a> <a href="chapB_mj.html">B</a> <a href="chapBib_mj.html">Bib</a> <a href="chapInd_mj.html">Ind</a> </div>

<hr />
generated by <a href="https://www.math.rwth-aachen.de/~Frank.Luebeck/GAPDoc">GAPDoc2HTML</a>
</body>
</html>

Messung V0.5 in Prozent

¤ Diese beiden folgenden Angebotsgruppen bietet das Unternehmen0.243Angebot (Wie Sie bei der Firma Beratungs- und Dienstleistungen beauftragen können 2026-04-26) ¤

*Eine klare Vorstellung vom Zielzustand

Wurzel

Suchen

Beweissystem der NASA

Beweissystem Isabelle

NIST Cobol Testsuite

Cephes Mathematical Library

Wiener Entwicklungsmethode

Haftungshinweis

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.