Quellcodebibliothek Statistik Leitseite products/Sources/formale Sprachen/GAP/pkg/digraphs/doc/   (GAP Algebra Version 4.15.1©)  Datei vom 27.8.2025 mit Größe 251 kB image not shown  

Quelle  chap5_mj.html   Sprache: HTML

 

 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"><span class="chlink1">Goto Chapter: </span><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>

<p id="mathjaxlink" class="pcenter"><a href="chap5.html">[MathJax off]</a></p>
<p><a id="X8739F6CD78C90B14" name="X8739F6CD78C90B14"></a></p>
<div class="ChapSects"><a href="chap5_mj.html#X8739F6CD78C90B14">5 <span class="Heading">Attributes and operations</span></a>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap5_mj.html#X7E814B6478F7D015">5.1 <span class="Heading">Vertices and edges</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X7C45F7D878D896AC">5.1-1 DigraphVertices</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X7C6F19B57CB2E882">5.1-2 DigraphNrVertices</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X7D1C6A4D7ECEC317">5.1-3 DigraphEdges</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X85E1CFDD7E164AD0">5.1-4 DigraphNrEdges</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X7BD5D255809C859E">5.1-5 DigraphNrAdjacencies</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X7E53E728795BB862">5.1-6 DigraphNrAdjacenciesWithoutLoops</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X7BDABAF07917462B">5.1-7 DigraphNrLoops</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X85D5E08280914EE4">5.1-8 DigraphSinks</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X7F5C6268839BE98C">5.1-9 DigraphSources</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X785C30378064CF47">5.1-10 DigraphTopologicalSort</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X7CA91E4B7904F793">5.1-11 DigraphVertexLabel</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X7E51F2FE87140B32">5.1-12 DigraphVertexLabels</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X79FAEACC7F438C2F">5.1-13 DigraphEdgeLabel</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X7C24851087D4A8FB">5.1-14 DigraphEdgeLabels</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X7EFAF01B7A155157">5.1-15 DigraphInEdges</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X7BECFE6687ECD028">5.1-16 DigraphOutEdges</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X7BB8ED88835F07B4">5.1-17 IsDigraphEdge</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X848FED0B7B4ACD1F">5.1-18 IsMatching</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X7B7A67277B1C9A02">5.1-19 DigraphMaximalMatching</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X78E9847A858788D1">5.1-20 DigraphMaximumMatching</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap5_mj.html#X7D7CE8328187D0DF">5.2 <span class="Heading">Neighbours and degree</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X7DC2CD70830BEE60">5.2-1 AdjacencyMatrix</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X87FA0A727CDB060B">5.2-2 CharacteristicPolynomial</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X8507DC4F794780C1">5.2-3 BooleanAdjacencyMatrix</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X7AFCE34A7A04D5C1">5.2-4 DigraphAdjacencyFunction</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X7FDEBF3279759961">5.2-5 DigraphRange</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X7E9880767AE68E00">5.2-6 OutNeighbours</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X85C7AA5A81DA6E11">5.2-7 InNeighbours</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X7F5ACE807D1BC2E2">5.2-8 OutDegrees</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X7ADDFBFD7A365775">5.2-9 InDegrees</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X7A09EB648070276D">5.2-10 OutDegreeOfVertex</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X83315B0186850806">5.2-11 OutNeighboursOfVertex</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X7C9CD0527CB9E6EF">5.2-12 InDegreeOfVertex</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X7C0DA18B8291F302">5.2-13 InNeighboursOfVertex</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X83271F607BD809CF">5.2-14 DigraphLoops</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X7BEAE1C78267F54D">5.2-15 DegreeMatrix</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X865390B08331936B">5.2-16 LaplacianMatrix</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap5_mj.html#X86424F167BD4F629">5.3 <span class="Heading">Orders</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X7DDB33B686B3A2C6">5.3-1 PartialOrderDigraphMeetOfVertices</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X824B9896798530F6">5.3-2 NonUpperSemimodularPair</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap5_mj.html#X8537F4088400DC48">5.4 <span class="Heading">Reachability and connectivity</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X7F16B9EB8398459C">5.4-1 DigraphDiameter</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X8104A9D37BCD8A05">5.4-2 DigraphShortestDistance</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X81F99BC67E9D050F">5.4-3 DigraphShortestDistances</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X8223718079D98A82">5.4-4 DigraphLongestDistanceFromVertex</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X7CB7DDCD84621D38">5.4-5 DigraphDistanceSet</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X79A3DA4078CF3C90">5.4-6 DigraphGirth</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X8374B7357EC189C1">5.4-7 DigraphOddGirth</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X84688B337BDDBB09">5.4-8 DigraphUndirectedGirth</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X842FAD6A7B835977">5.4-9 DigraphConnectedComponents</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X8484EC557810CD31">5.4-10 DigraphConnectedComponent</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X833ECD6B7A84944C">5.4-11 DigraphStronglyConnectedComponents</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X7EFCB5017D662254">5.4-12 DigraphStronglyConnectedComponent</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X7F1B5A2782F598B1">5.4-13 DigraphBicomponents</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X7DDE06E47E605DD7">5.4-14 ArticulationPoints</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X803459AB86AB9BE2">5.4-15 MinimalCyclicEdgeCut</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X84D5A125848BD800">5.4-16 Bridges</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X865590147BD1C507">5.4-17 StrongOrientation</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X853D0B0981A33433">5.4-18 DigraphPeriod</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X864A31A8809F61C2">5.4-19 DigraphFloydWarshall</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X7FBAB09E7C0BE5CF">5.4-20 IsReachable</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X7ECD22877AEA89CC">5.4-21 IsDigraphPath</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X7F255A2A84CB868C">5.4-22 VerticesReachableFrom</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X8039170B82A32257">5.4-23 DigraphPath</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X80E9D645843973A6">5.4-24 DigraphShortestPath</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X7C45396C808308C4">5.4-25 DigraphRandomWalk</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X787459247B2005E6">5.4-26 DigraphAbsorptionProbabilities</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X7B0A62CF7F6F23E9">5.4-27 DigraphAbsorptionExpectedSteps</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X7FE79CB278CE6991">5.4-28 Dominators</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X7D66A0FB7F6100FB">5.4-29 DominatorTree</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X7C0416FE7A69CA2C">5.4-30 IteratorOfPaths</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X7ECD16838704FAAA">5.4-31 DigraphAllSimpleCircuits</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X7C735C4E86BDD5F6">5.4-32 DigraphLongestSimpleCircuit</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X7F9EDAA8854FB538">5.4-33 DigraphAllUndirectedSimpleCircuits</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X7F0AC5617CE5E9DD">5.4-34 DigraphAllChordlessCycles</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X805F15398735AD7D">5.4-35 FacialWalks</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X870E04307C5F213F">5.4-36 DigraphLayers</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X7B2E42327DA118E0">5.4-37 DigraphDegeneracy</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X827C2BD17A4547E3">5.4-38 DigraphDegeneracyOrdering</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X863FDFC4839A3B82">5.4-39 HamiltonianPath</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X82F30D5681466BC6">5.4-40 NrSpanningTrees</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X79352A8286D1D8F6">5.4-41 DigraphDijkstra</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X794CD6037D4CF58C">5.4-42 DigraphCycleBasis</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X835AAF9085BC9D84">5.4-43 DigraphIsKing</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X7A17B9B67AC50561">5.4-44 DigraphKings</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap5_mj.html#X82F900777D677F55">5.5 <span class="Heading">Cayley graphs of groups</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X7A000B1D7CCF7093">5.5-1 GroupOfCayleyDigraph</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X8528455987D7D2BF">5.5-2 GeneratorsOfCayleyDigraph</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap5_mj.html#X790FD6647ECCAE3C">5.6 <span class="Heading">Associated semigroups</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X87D5C60D7B0C1309">5.6-1 AsSemigroup</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X7C6D5EC27C51066B">5.6-2 AsSemigroup</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap5_mj.html#X7E2305528492DDC0">5.7 <span class="Heading">Planarity</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X7DC478637E8C190D">5.7-1 KuratowskiPlanarSubdigraph</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X78E8F09A8286501B">5.7-2 KuratowskiOuterPlanarSubdigraph</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X84E3947E7D39BA64">5.7-3 PlanarEmbedding</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X85DFB8C18088711F">5.7-4 OuterPlanarEmbedding</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X806D2D6B85E0B269">5.7-5 SubdigraphHomeomorphicToK23</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X876803517C34E1CD">5.7-6 DualPlanarGraph</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap5_mj.html#X7FF5E2D07D48647E">5.8 <span class="Heading">Hashing</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X7D97D990867B0149">5.8-1 DigraphHash</a></span>
</div></div>
</div>

<h3>5 <span class="Heading">Attributes and operations</span></h3>

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

<h4>5.1 <span class="Heading">Vertices and edges</span></h4>

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

<h5>5.1-1 DigraphVertices</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; DigraphVertices</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>Returns: A list of positive integers.</p>

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

<p>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"><span class="RefLink">5.1-2</span></a>). Arbitrary <em>labels</em> can be assigned to the vertices of a digraph; see <code class="func">DigraphVertexLabels</code> (<a href="chap5_mj.html#X7E51F2FE87140B32"><span class="RefLink">5.1-12</span></a>) for more information about this.</p>


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

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

<h5>5.1-2 DigraphNrVertices</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; DigraphNrVertices</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>Returns: An non-negative integer.</p>

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


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

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

<h5>5.1-3 DigraphEdges</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; DigraphEdges</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>Returns: A list of lists of two positive integers.</p>

<p>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"><span class="RefLink">5.1-1</span></a>) of the form <code class="code">[source,range]</code>.</p>

<p>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.</p>

<p>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.</p>


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

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

<h5>5.1-4 DigraphNrEdges</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; DigraphNrEdges</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>Returns: An integer.</p>

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


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

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

<h5>5.1-5 DigraphNrAdjacencies</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; DigraphNrAdjacencies</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>Returns: An integer.</p>

<p>Returns the number of sets <span class="SimpleMath">\(\{u, v\}\)</span> of vertices of the digraph <var class="Arg">digraph</var>, such that either <span class="SimpleMath">\((u, v)\)</span> or <span class="SimpleMath">\((v, u)\)</span> 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>.</p>


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

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

<h5>5.1-6 DigraphNrAdjacenciesWithoutLoops</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; DigraphNrAdjacenciesWithoutLoops</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>Returns: An integer.</p>

<p>Returns the number of sets <span class="SimpleMath">\(\{u, v\}\)</span> of vertices of the digraph <var class="Arg">digraph</var>, such that <span class="SimpleMath">\(u \neq v\)</span> and either <span class="SimpleMath">\((u, v)\)</span> or <span class="SimpleMath">\((v, u)\)</span> 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>.</p>


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

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

<h5>5.1-7 DigraphNrLoops</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; DigraphNrLoops</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>Returns: An integer.</p>

<p>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"><span class="RefLink">6.2-1</span></a>).</p>


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

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

<h5>5.1-8 DigraphSinks</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; DigraphSinks</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>Returns: A list of vertices.</p>

<p>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"><span class="RefLink">5.2-10</span></a>).</p>


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

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

<h5>5.1-9 DigraphSources</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; DigraphSources</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>Returns: A list of vertices.</p>

<p>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"><span class="RefLink">5.2-12</span></a>).</p>


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

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

<h5>5.1-10 DigraphTopologicalSort</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; DigraphTopologicalSort</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>Returns: A list of positive integers, or <code class="keyw">fail</code>.</p>

<p>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 <span class="SimpleMath">\(1\)</span>, then this operation returns <code class="keyw">fail</code>.</p>

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

<p>The method used for this attribute has complexity <span class="SimpleMath">\(O(m+n)\)</span> where <span class="SimpleMath">\(m\)</span> is the number of edges (counting multiple edges as one) and <span class="SimpleMath">\(n\)</span> is the number of vertices in the digraph.</p>


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

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

<h5>5.1-11 DigraphVertexLabel</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; 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">&#an style='color: green'>8227; 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>
<p>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 <strong class="pkg">GAP</strong> object <var class="Arg">obj</var>.</p>

<p>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>.</p>

<p>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.</p>

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


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

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

<h5>5.1-12 DigraphVertexLabels</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; 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">&#an style='color: green'>8227; SetDigraphVertexLabels</code>( <var class="Arg">digraph</var>, <var class="Arg">list</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>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 <strong class="pkg">GAP</strong> objects <var class="Arg">list</var>, which must be of the same length as the number of vertices of <var class="Arg">digraph</var>.</p>

<p>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>.</p>

<p>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>.</p>

<p>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>.</p>

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


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

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

<h5>5.1-13 DigraphEdgeLabel</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; 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">&#an style='color: green'>8227; 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>
<p>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 <strong class="pkg">GAP</strong> object <var class="Arg">obj</var>.</p>

<p>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>.</p>

<p>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"><span class="RefLink">5.1-14</span></a>).</p>


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

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

<h5>5.1-14 DigraphEdgeLabels</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; 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">&#an style='color: green'>8227; 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">&#an style='color: green'>8227; SetDigraphEdgeLabels</code>( <var class="Arg">digraph</var>, <var class="Arg">func</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>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 <strong class="pkg">GAP</strong> 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>.</p>

<p>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>.</p>

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


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

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

<h5>5.1-15 DigraphInEdges</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; DigraphInEdges</code>( <var class="Arg">digraph</var>, <var class="Arg">vertex</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: A list of edges.</p>

<p><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.</p>


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

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

<h5>5.1-16 DigraphOutEdges</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; DigraphOutEdges</code>( <var class="Arg">digraph</var>, <var class="Arg">vertex</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: A list of edges.</p>

<p><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.</p>


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

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

<h5>5.1-17 IsDigraphEdge</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; 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">&#an style='color: green'>8227; 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>
<p>Returns: <code class="keyw">true</code> or <code class="keyw">false</code>.</p>

<p>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.</p>

<p>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.</p>


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

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

<h5>5.1-18 IsMatching</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; 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">&#an style='color: green'>8227; 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">&#an style='color: green'>8227; 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">&#an style='color: green'>8227; IsPerfectMatching</code>( <var class="Arg">digraph</var>, <var class="Arg">list</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: <code class="keyw">true</code> or <code class="keyw">false</code>.</p>

<p>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>.</p>

<p>A <em>matching</em> <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"><span class="RefLink">6.2-1</span></a>). The matching <code class="code">M</code> is <em>maximal</em> if it is contained in no larger matching of the digraph, is <em>maximum</em> if it has the greatest cardinality among all matchings and is <em>perfect</em> 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.</p>


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

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

<h5>5.1-19 DigraphMaximalMatching</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; DigraphMaximalMatching</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>Returns: A list of pairs of vertices.</p>

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

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


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

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

<h5>5.1-20 DigraphMaximumMatching</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; DigraphMaximumMatching</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>Returns: A list of pairs of vertices.</p>

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

<p>For the definition of a maximum matching, see <code class="func">IsMaximumMatching</code> (<a href="chap5_mj.html#X848FED0B7B4ACD1F"><span class="RefLink">5.1-18</span></a>). If <var class="Arg">digraph</var> is bipartite (see <code class="func">IsBipartiteDigraph</code> (<a href="chap6_mj.html#X860CFB0C8665F356"><span class="RefLink">6.2-3</span></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.</p>


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

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

<h4>5.2 <span class="Heading">Neighbours and degree</span></h4>

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

<h5>5.2-1 AdjacencyMatrix</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; 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">&#an style='color: green'>8227; AdjacencyMatrixMutableCopy</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: A square matrix of non-negative integers.</p>

<p>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.</p>

<p>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.</p>


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

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

<h5>5.2-2 CharacteristicPolynomial</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; CharacteristicPolynomial</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>Returns: A polynomial with integer coefficients.</p>

<p>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></p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">D := Digraph([</span>
<span class="GAPprompt">></span> <span class="GAPinput">[2, 2, 2], [1, 3, 6, 8, 9, 10], [4, 6, 8],</span>
<span class="GAPprompt">></span> <span class="GAPinput">[1, 2, 3, 9], [3, 3], [3, 5, 6, 10], [1, 2, 7],</span>
<span class="GAPprompt">></span> <span class="GAPinput">[1, 2, 3, 10, 5, 6, 10], [1, 3, 4, 5, 8, 10],</span>
<span class="GAPprompt">></span> <span class="GAPinput">[2, 3, 4, 6, 7, 10]]);</span>
<immutable multidigraph with 10 vertices, 44 edges>
<span class="GAPprompt">gap></span> <span class="GAPinput">CharacteristicPolynomial(D);</span>
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
<span class="GAPprompt">gap></span> <span class="GAPinput">D := CompleteDigraph(5);</span>
<immutable complete digraph with 5 vertices>
<span class="GAPprompt">gap></span> <span class="GAPinput">CharacteristicPolynomial(D);</span>
x_1^5-10*x_1^3-20*x_1^2-15*x_1-4
<span class="GAPprompt">gap></span> <span class="GAPinput">D := CycleDigraph(IsMutableDigraph, 3);</span>
<mutable digraph with 3 vertices, 3 edges>
<span class="GAPprompt">gap></span> <span class="GAPinput">CharacteristicPolynomial(D);</span>
x_1^3-1
</pre></div>

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

<h5>5.2-3 BooleanAdjacencyMatrix</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; 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">&#an style='color: green'>8227; BooleanAdjacencyMatrixMutableCopy</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: A square matrix of booleans.</p>

<p>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.</p>

<p>Note that the boolean adjacency matrix loses information about multiple edges.</p>

<p>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.</p>


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

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

<h5>5.2-4 DigraphAdjacencyFunction</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; DigraphAdjacencyFunction</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>Returns: A function.</p>

<p>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.</p>


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

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

<h5>5.2-5 DigraphRange</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; 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">&#an style='color: green'>8227; DigraphSource</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>Returns: A list of positive integers.</p>

<p><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>.</p>


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

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

<h5>5.2-6 OutNeighbours</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; 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">&#an style='color: green'>8227; 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">&#an style='color: green'>8227; 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">&#an style='color: green'>8227; OutNeighborsMutableCopy</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: The adjacencies of a digraph.</p>

<p><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>.</p>

<p>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.</p>

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


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

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

<h5>5.2-7 InNeighbours</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; 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">&#an style='color: green'>8227; 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">&#an style='color: green'>8227; 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">&#an style='color: green'>8227; InNeighborsMutableCopy</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: A list of lists of vertices.</p>

<p><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>.</p>

<p>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.</p>

<p>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"><span class="RefLink">3.1-11</span></a>).</p>


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

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

<h5>5.2-8 OutDegrees</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; 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">&#an style='color: green'>8227; 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">&#an style='color: green'>8227; OutDegreeSet</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>Returns: A list of non-negative integers.</p>

<p>Given a digraph <var class="Arg">digraph</var> with <span class="SimpleMath">\(n\)</span> vertices, the function <code class="code">OutDegrees</code> returns an immutable list <code class="code">out</code> of length <span class="SimpleMath">\(n\)</span>, 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"><span class="RefLink">5.2-10</span></a>).</p>

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

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


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

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

<h5>5.2-9 InDegrees</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; 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">&#an style='color: green'>8227; 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">&#an style='color: green'>8227; InDegreeSet</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>Returns: A list of non-negative integers.</p>

<p>Given a digraph <var class="Arg">digraph</var> with <span class="SimpleMath">\(n\)</span> vertices, the function <code class="code">InDegrees</code> returns an immutable list <code class="code">inn</code> of length <span class="SimpleMath">\(n\)</span>, 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"><span class="RefLink">5.2-12</span></a>).</p>

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

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


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

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

<h5>5.2-10 OutDegreeOfVertex</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; OutDegreeOfVertex</code>( <var class="Arg">digraph</var>, <var class="Arg">vertex</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: The non-negative integer.</p>

<p>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>.</p>


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

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

<h5>5.2-11 OutNeighboursOfVertex</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; 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">&#an style='color: green'>8227; OutNeighborsOfVertex</code>( <var class="Arg">digraph</var>, <var class="Arg">vertex</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: A list of vertices.</p>

<p>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.</p>


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

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

<h5>5.2-12 InDegreeOfVertex</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; InDegreeOfVertex</code>( <var class="Arg">digraph</var>, <var class="Arg">vertex</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: A non-negative integer.</p>

<p>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>.</p>


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

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

<h5>5.2-13 InNeighboursOfVertex</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; 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">&#an style='color: green'>8227; InNeighborsOfVertex</code>( <var class="Arg">digraph</var>, <var class="Arg">vertex</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: A list of positive vertices.</p>

<p>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.</p>


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

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

<h5>5.2-14 DigraphLoops</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; DigraphLoops</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>Returns: A list of vertices.</p>

<p>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"><span class="RefLink">5.1-1</span></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"><span class="RefLink">6.2-1</span></a>).</p>


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

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

<h5>5.2-15 DegreeMatrix</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; DegreeMatrix</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>Returns: A square matrix of non-negative integers.</p>

<p>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.</p>

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


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

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

<h5>5.2-16 LaplacianMatrix</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; LaplacianMatrix</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>Returns: A square matrix of integers.</p>

<p>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.</p>

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


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

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

<h4>5.3 <span class="Heading">Orders</span></h4>

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

<h5>5.3-1 PartialOrderDigraphMeetOfVertices</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; 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">&#an style='color: green'>8227; 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>
<p>Returns: A positive integer or <code class="keyw">fail</code></p>

<p>If the first argument is a partial order digraph <code class="func">IsPartialOrderDigraph</code> (<a href="chap6_mj.html#X82BAE6D37D49A145"><span class="RefLink">6.4-2</span></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"><span class="RefLink">6.4-3</span></a>) (or <code class="func">IsJoinSemilatticeDigraph</code> (<a href="chap6_mj.html#X78D3E17B7F737516"><span class="RefLink">6.4-3</span></a>)) - see the documentation for these properties for the definition of the meet (or the join).</p>


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

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

<h5>5.3-2 NonUpperSemimodularPair</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; 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">&#an style='color: green'>8227; NonLowerSemimodularPair</code>( <var class="Arg">D</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>Returns: A pair of vertices or <code class="keyw">fail</code>.</p>

<p><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.</p>

<p>If the digraph <var class="Arg">D</var> does not satisfy <code class="func">IsLatticeDigraph</code> (<a href="chap6_mj.html#X78D3E17B7F737516"><span class="RefLink">6.4-3</span></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"><span class="RefLink">6.4-3</span></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.</p>

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

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


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

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

<h4>5.4 <span class="Heading">Reachability and connectivity</span></h4>

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

<h5>5.4-1 DigraphDiameter</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; DigraphDiameter</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>Returns: An integer or <code class="code">fail</code>.</p>

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

<p>If a digraph <var class="Arg">digraph</var> is strongly connected and has at least 1 vertex, then the <em>diameter</em> 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>.</p>

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


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

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

<h5>5.4-2 DigraphShortestDistance</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; 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">&#an style='color: green'>8227; 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">&#an style='color: green'>8227; 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>
<p>Returns: An integer or <code class="keyw">fail</code></p>

<p>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"><span class="RefLink">1.1-1</span></a> for the definition of a directed path.</p>

<p>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>.</p>

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

<p>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>.</p>


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

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

<h5>5.4-3 DigraphShortestDistances</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; DigraphShortestDistances</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>Returns: A square matrix.</p>

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

<p>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>.</p>

<p>The method used in this function is a version of the Floyd-Warshall algorithm, and has complexity <span class="SimpleMath">\(O(n^3)\)</span>.</p>


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

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

<h5>5.4-4 DigraphLongestDistanceFromVertex</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; DigraphLongestDistanceFromVertex</code>( <var class="Arg">digraph</var>, <var class="Arg">v</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: An integer, or <code class="keyw">infinity</code>.</p>

<p>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"><span class="RefLink">1.1-1</span></a> for the definitions of directed walk, directed cycle, and loop.</p>


<ul>
<li><p>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"><span class="RefLink">3.3-25</span></a>):</p>

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

</li>
<li><p>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.</p>

</li>
</ul>
<p>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"><span class="RefLink">5.1-8</span></a>).</p>


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

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

<h5>5.4-5 DigraphDistanceSet</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; 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">&#an style='color: green'>8227; 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>
<p>Returns: A list of vertices</p>

<p>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>.</p>

<p><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.</p>


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

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

<h5>5.4-6 DigraphGirth</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; DigraphGirth</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>Returns: An integer, or <code class="keyw">infinity</code>.</p>

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

<p>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>.</p>

<p>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"><span class="RefLink">7.2-10</span></a>)], then the performance is likely to be better.</p>

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


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

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

<h5>5.4-7 DigraphOddGirth</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; DigraphOddGirth</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>Returns: An integer, or <code class="keyw">infinity</code>.</p>

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

<p>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>.</p>

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


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

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

<h5>5.4-8 DigraphUndirectedGirth</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; DigraphUndirectedGirth</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>Returns: An integer or <code class="keyw">infinity</code>.</p>

<p>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 <span class="SimpleMath">\([i, j]\)</span> and <span class="SimpleMath">\([j, i]\)</span> is treated as a single edge between <span class="SimpleMath">\(i\)</span> and <span class="SimpleMath">\(j\)</span>).</p>

<p>The <em>girth</em> 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.</p>

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


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

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

<h5>5.4-9 DigraphConnectedComponents</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; 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">&#an style='color: green'>8227; DigraphNrConnectedComponents</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>Returns: A record.</p>

<p>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"><span class="RefLink">5.4-11</span></a>)) of the <code class="func">DigraphSymmetricClosure</code> (<a href="chap3_mj.html#X874883DD7DD450C4"><span class="RefLink">3.3-12</span></a>) of <var class="Arg">digraph</var>.</p>

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

<p>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>.</p>

<p>The method used in this function has complexity <span class="SimpleMath">\(O(m+n)\)</span>, where <span class="SimpleMath">\(m\)</span> is the number of edges and <span class="SimpleMath">\(n\)</span> is the number of vertices in the digraph.</p>

<p><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.</p>


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

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

<h5>5.4-10 DigraphConnectedComponent</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; DigraphConnectedComponent</code>( <var class="Arg">digraph</var>, <var class="Arg">vertex</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: A list of vertices.</p>

<p>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"><span class="RefLink">5.4-9</span></a>) for more information.</p>


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

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

<h5>5.4-11 DigraphStronglyConnectedComponents</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; 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">&#an style='color: green'>8227; DigraphNrStronglyConnectedComponents</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>Returns: A record.</p>

<p>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>.</p>

<p>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>.</p>

<p>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 <span class="SimpleMath">\(O(m+n)\)</span> where <span class="SimpleMath">\(m\)</span> is the number of edges (counting multiple edges as one) and <span class="SimpleMath">\(n\)</span> is the number of vertices in the digraph.</p>

<p><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.</p>


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

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

<h5>5.4-12 DigraphStronglyConnectedComponent</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; DigraphStronglyConnectedComponent</code>( <var class="Arg">digraph</var>, <var class="Arg">vertex</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: A list of vertices.</p>

<p>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"><span class="RefLink">5.4-11</span></a>) for more information.</p>


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

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

<h5>5.4-13 DigraphBicomponents</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; DigraphBicomponents</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>Returns: A pair of lists of vertices, or <code class="keyw">fail</code>.</p>

<p>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"><span class="RefLink">6.2-3</span></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>.</p>

<p>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 <em>bicomponents</em> 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>.</p>

<p>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"><span class="RefLink">6.6-3</span></a>) for more information.</p>


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

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

<h5>5.4-14 ArticulationPoints</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; ArticulationPoints</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>Returns: A list of vertices.</p>

<p>A connected digraph is <em>biconnected</em> if it is still connected (in the sense of <code class="func">IsConnectedDigraph</code> (<a href="chap6_mj.html#X83C08C0B7EC1A91F"><span class="RefLink">6.6-3</span></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 <em>articulation point</em>.</p>

<p><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.</p>

<p>Multiple edges are ignored by this method.</p>

<p>The method used in this operation has complexity <span class="SimpleMath">\(O(m+n)\)</span> where <span class="SimpleMath">\(m\)</span> is the number of edges and <span class="SimpleMath">\(n\)</span> is the number of vertices in the digraph.</p>

<p>If <var class="Arg">D</var> has a bridge (see <code class="func">Bridges</code> (<a href="chap5_mj.html#X84D5A125848BD800"><span class="RefLink">5.4-16</span></a>)), then a node incident to the bridge is an articulation point if and only if it has degree at least <span class="SimpleMath">\(2\)</span>. It follows that if <var class="Arg">D</var> has a bridge and at least <span class="SimpleMath">\(3\)</span> 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.</p>

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


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

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

<h5>5.4-15 MinimalCyclicEdgeCut</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; MinimalCyclicEdgeCut</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>Returns: A list of edges or <code class="keyw">fail</code>.</p>

<p>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.</p>

<p>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.</p>

<p>The method used in this method has complexity <span class="SimpleMath">\(O(n^2*log^2(n)) \)</span> where <span class="SimpleMath">\(n\)</span> is the number of vertices in the digraph.</p>


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

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

<h5>5.4-16 Bridges</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; Bridges</code>( <var class="Arg">D</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>Returns: A (possibly empty) list of edges.</p>

<p>A connected digraph is <em>2-edge-connected</em> if it is still connected (in the sense of <code class="func">IsConnectedDigraph</code> (<a href="chap6_mj.html#X83C08C0B7EC1A91F"><span class="RefLink">6.6-3</span></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 <em>bridge</em>.</p>

<p><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.</p>

<p>Multiple edges are ignored by this method.</p>

<p>The method used in this operation has complexity <span class="SimpleMath">\(O(m+n)\)</span> where <span class="SimpleMath">\(m\)</span> is the number of edges and <span class="SimpleMath">\(n\)</span> is the number of vertices in the digraph.</p>

<p>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"><span class="RefLink">5.4-14</span></a>)) if and only if it has degree at least <span class="SimpleMath">\(2\)</span>. It follows that if <var class="Arg">D</var> has a bridge and at least <span class="SimpleMath">\(3\)</span> 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.</p>

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


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

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

<h5>5.4-17 StrongOrientation</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; 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">&#an style='color: green'>8227; StrongOrientationAttr</code>( <var class="Arg">D</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>Returns: A digraph or <code class="keyw">fail</code>.</p>

<p>A <em>strong orientation</em> 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"><span class="RefLink">6.6-5</span></a>)).</p>

<p>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.</p>

<p>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.</p>

<p>The method used in this operation has complexity <span class="SimpleMath">\(O(m+n)\)</span> where <span class="SimpleMath">\(m\)</span> is the number of edges and <span class="SimpleMath">\(n\)</span> is the number of vertices in the digraph.</p>


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

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

<h5>5.4-18 DigraphPeriod</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; DigraphPeriod</code>( <var class="Arg">digraph</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>Returns: An integer.</p>

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

<p>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 <span class="SimpleMath">\(0\)</span>. See Section <a href="chap1_mj.html#X84541F61810C741D"><span class="RefLink">1.1-1</span></a> for the definition of a directed cycle.</p>

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


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

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

<h5>5.4-19 DigraphFloydWarshall</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; 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>
<p>Returns: A matrix.</p>

<p>If <var class="Arg">digraph</var> is a digraph with <span class="SimpleMath">\(n\)</span> vertices, then this operation returns an <span class="SimpleMath">\(n \times n\)</span> 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>.</p>

<p>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 <strong class="pkg">GAP</strong> 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.</p>

<p>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>:</p>


<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>

<p>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:</p>


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

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

<h5>5.4-20 IsReachable</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&an style='color:turquoise'>#8227; 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>
<p>Returns: <code class="keyw">true</code> or <code class="keyw">false</code>.</p>

<p>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"><span class="RefLink">1.1-1</span></a> for the definition of a non-trivial directed walk.</p>

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


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

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

<h5>5.4-21 IsDigraphPath</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&an style='color:turquoise'>#8227; 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">&an style='color:turquoise'>#8227; IsDigraphPath</code>( <var class="Arg">D</var>, <var class="Arg">list</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: <code class="keyw">true</code> or <code class="keyw">false</code>.</p>

<p>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>, <span class="SimpleMath">\((v_1, e_1, v_2, e_2, ..., e_{n-1}, v_n)\)</span>, is represented by a pair of lists <code class="code">[<var class="Arg">v</var>, <var class="Arg">a</var>]</code> as follows:</p>


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

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

</li>
</ul>
<p>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>.</p>


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

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

<h5>5.4-22 VerticesReachableFrom</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&an style='color:turquoise'>#8227; 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">&an style='color:turquoise'>#8227; VerticesReachableFrom</code>( <var class="Arg">digraph</var>, <var class="Arg">list</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: A list.</p>

<p>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"><span class="RefLink">1.1-1</span></a> for the definition of a non-trivial directed walk.</p>

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

<p>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>.</p>


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

paid=X8039170B82A32257 ">/>/p>

<h5>5.4-23 DigraphPath</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&an style='color:turquoise'>#8227; DigraphPath</code>( <var class="Arg">digraph</var>,   to deal intheSoftwarewithout restriction without limitation
<p>Returns: A pair of lists, or <code class="keyw">fail</ *andorsell copiesof the Software,to permitpersons towhom the

<p>If there exists a non-trivial directed path (or a non-trivial cycle  allcopiesor   theSoftware

<p *IMPLIED,INCLUDINGBUT NOT LIMITED TO THE WARRANTIESOF ,


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

</li>
<><p<codeclass"code"></ode  thelist   <panclass=SimpleMath>\[, ,..,a_n1]\)/>where  each <spanclass"SimpleMath"">(i lt n)<span, spanclass="SimpleMath">(\)/span is  position  < class=SimpleMath"\v_+\<span  code=c"OutNeighboursOfVertex</><var class=Arg"digraph/ar> ="code><code< "">\v_i\<span< ="code")/> correspondingtothe  < class"impleMath>()/.Thiscanbeusefulif of vertexin    -neighoursissignificant  exampleinorbitdigraphs.<>

class
</ul>
<const  ;

pSeealsoc =""IsDigraphPath/>(ahref".#X7ECD22877AEA89CC>spanclass=R">5421<span><a>./>


< =example>pre>
">D :=Digraph([2,[],[2,3])/span>
;
<span java.lang.StringIndexOutOfBoundsException: Index 8 out of bounds for length 0
[
<span class="java.lang.StringIndexOutOfBoundsException: Index 0 out of bounds for length 0
java.lang.StringIndexOutOfBoundsException: Range [4, 5) out of bounds for length 4
<span
[ 3,3]    java.lang.StringIndexOutOfBoundsException: Index 19 out of bounds for length 19
<span

</pre>

<p><a idjava.lang.StringIndexOutOfBoundsException: Index 0 out of bounds for length 0

5424</5

">tableclass"func" width=100%><tr><td class"tdleft>code class"func">#8227; DigraphShortestPath</code>( <var class="Arg">digraph</var>, <var class="Arg">u</var>, <var class="Arg">v</var> )</td><td class="tdright static <char16_t,int32_t>SCRIPT_ARR;
  class""fail/./p>

<p>Returns a shortest directed path in the digraphjava.lang.StringIndexOutOfBoundsException: Index 0 out of bounds for length 0

<bool;


<  nsHtml5ElementName nonInternedTagName
   java.lang.StringIndexOutOfBoundsException: Range [29, 28) out of bounds for length 29
&i5   >
s =GAPpromptgap&;/ classjava.lang.StringIndexOutOfBoundsException: Range [61, 60) out of bounds for length 98
[ [ 5, 4, 1 ], [ 2, 1 ] ]
spanclass">>/pan><pan ""DigraphShortestPath(,3,3;/span>
[ [ 3, 2, 3 ], [ 1, 1 ] ]
 G"&;/>< java.lang.StringIndexOutOfBoundsException: Range [51, 50) out of bounds for length 98
fail
="java.lang.StringIndexOutOfBoundsException: Range [82, 81) out of bounds for length 98
 ,[1  java.lang.StringIndexOutOfBoundsException: Index 19 out of bounds for length 19
</pre></div>

<:

<h5

< (OZ_UNLIKELYs.ength<newLen)){
<}

 path correspondingto <>andom </>inthe <ar=Arg></ar>    var class><var   lengthnomore  <ar class=Arg>t</>./>

 begins at<ar ="Arg"v/>,     itfollows a   Itthein  until it < java.lang.StringIndexOutOfBoundsException: Range [234, 233) out of bounds for length 354

<p  java.lang.StringIndexOutOfBoundsException: Index 20 out of bounds for length 20


div=example>prejava.lang.StringIndexOutOfBoundsException: Index 26 out of bounds for length 26
<span class
<immutable digraph withreconsume,pos)
<span           continue
 , 2, 3, 2,3]  , 1 ,1]]
</pre></div>

           (; java.lang.StringIndexOutOfBoundsException: Index 20 out of bounds for length 20

<ties<>

<div class=containsHyphen ;
<p>Returns: A

   throughafinite  passthrough several strongly  SCCs.,with  1 it  java.lang.StringIndexOutOfBoundsException: Range [181, 180) out of bounds for length 440

<,;

<                      nsHtml5Tokenizer:PROCESSING_INSTRUCTION,reconsume pos;


<divNS_HTML5_CONTINUE)
<span  tokenHandler>n:LT_GT ,2)java.lang.StringIndexOutOfBoundsException: Index 72 out of bounds for length 72
<immutableNS_HTML5_CONTINUE)
<     tokenHandler->characters(nsHtml5Tokenizer::LT_GT, 0, 1);
[[2,  ] [4 ],[1 ] ]
          
[[ 23 /,0]  , 0, ,[1 ,0]  ,1,0]]
</pre></div>

<p><a id="X7B0A62CF7F6F23E9" nameNS_HTML5_BREAKstateloop

<h5>5.4-27 DigraphAbsorptionExpectedSteps</h5>

div =func>tableclass"" width"%>tr< "tdleft>code="unc"&/(<class="">digraph<var> )/d<tdclass="tdright"(nbspa&bsp;<td><tr<table</iv>
<p>Returns: A list of                stateloop;

();

<>codeclass=code>/>    c =code><code   equaltothenumberofvertices of < =Arg></var, where <ode class=code"Lv<code>      steps arandomwalkvertexcode">/>takebefore is– expected oftoreachanthatcannever<

<p          


java.lang.StringIndexOutOfBoundsException: Range [31, 30) out of bounds for length 42
<spancasef:java.lang.StringIndexOutOfBoundsException: Index 26 out of bounds for length 26
<immutable digraph with 4 verticesreconsume pos;
 class">&t;/> <span class=GAPinput"DigraphAbsorptionExpectedSteps;/
 ,3, 0,4]
</pre></div>

id"java.lang.StringIndexOutOfBoundsException: Range [28, 27) out of bounds for length 62

<h5>5.4-                )

<[[;
<p>Returns: Aif+pos= ){

<                                      :AFTER_ATTRIBUTE_NAME


<div class="case/: 
="gapgt;</pan><spanclass=GAPinput"D=Digraph([2,[,6,[,4,[] ] [3])<span
 ()
sclass">&;</> <spanclass=GAPinput">Dominators(D, 1);</span>
              
<span class="emitCurrentTagToken(alse ,
[ [ 4java.lang.StringIndexOutOfBoundsException: Range [34, 33) out of bounds for length 45
<span                \'
  4, ,[3], [ 3 , [2 3]]
<span class="java.lang.StringIndexOutOfBoundsException: Index 16 out of bounds for length 15
[ [ 4 ], [ 1, 4 ]                )
          ]
[  ]
 class="APinput">(,6)<span
[ [ 4, 3, 6                \:{
java.lang.StringIndexOutOfBoundsException: Range [14, 12) out of bounds for length 12

 name"7"<a<pjava.lang.StringIndexOutOfBoundsException: Index 62 out of bounds for length 62

<h5>5.4-29 DominatorTree</h5>

d =func>table=func"width"%"<>< class=tdleft"><ode classfunc>#;DominatorTree/> var class""digraph/var>,<ar =Arg">root</var>)/td>td =tdright"(nbspoperationnbsp)/>/>/<div
<p>Returns: A record.</p>

<perrAttributeValueMissing)


<dlcase'0: 
dt<class"><strong>/dt>
<dd><p>the immediate dominators of the vertices                   (c;

</dd>
<dt><strong class="Mark">preorder</strong></dt>
<dd}

<>
</dl>
<p                :(,buf ;


<div class="example"><pre>
<span class="GAPprompt">gap><                appendCharRefBuf(;
&;mmutable  with6vertices,12 edges&tjava.lang.StringIndexOutOfBoundsException: Index 51 out of bounds for length 51
 ="GAPprompt>&;/>< class=GAPinput"DominatorTree,1)</spanjava.lang.StringIndexOutOfBoundsException: Index 89 out of bounds for length 89
rec( idom := [ fail, 1, 1, 1, 1, 1 ], 
  preorder:  ,,4 3,5 6])
<default java.lang.StringIndexOutOfBoundsException: Index 24 out of bounds for length 24
rec( idom := [ 5, 5, 5,         :;
  preorder := [ 5, 1, 2, 4, 3, 6 {
<span class="GAPprompt">gap></case'\r': {
&; complete digraph with 5vertices&tjava.lang.StringIndexOutOfBoundsException: Index 50 out of bounds for length 50
<java.lang.StringIndexOutOfBoundsException: Range [14, 3) out of bounds for length 26
rec( idom  ':
<span                                        java.lang.StringIndexOutOfBoundsException: Index 54 out of bounds for length 54
rec( idom := [ 2, fail, 2,                                      SELF_CLOSING_START_TAG
</pre></div>

<<id""name""<a<pjava.lang.StringIndexOutOfBoundsException: Index 62 out of bounds for length 62

<                               nsHtml5Tokenizer:,

<           +== ){
<Returns  ./>

<p>If <varNS_HTML5_BREAKstateloop;

<}


d classe"<pre>
java.lang.StringIndexOutOfBoundsException: Range [26, 23) out of bounds for length 32
limmutablemultidigraphwith 5 vertices  g;
<spanP:(this
&;iteratorgt
              \' 
[ [ 1              ''
<                (;
[ [ 1, 4 ], [ 3 ] ]
<span            "harRefBufLennot  after  !)
[ [ 1, 2, 5, 4 ], [ 4, 2, 1 ] ]
<span class="GAPprompt">                                   ;
    case':{
<span class="reconsumejava.lang.StringIndexOutOfBoundsException: Index 54 out of bounds for length 54
<iterator>
<span class="GAPprompt">gap& case':
[ 1 ,1  
</pre></div>

<p><a id}

<h5>5.4-31 DigraphAllSimpleCircuits</h5>

<[[allthrough]];
<p>Returns''

<p>If                                       :java.lang.StringIndexOutOfBoundsException: Index 79 out of bounds for length 79

<p>See Section <a href="chap1_mj.html#reconsume )java.lang.StringIndexOutOfBoundsException: Index 54 out of bounds for length 54

<p>For a digraph                                       ;

<p>With this approach, a                   xfffd;


<                fjava.lang.StringIndexOutOfBoundsException: Range [31, 29) out of bounds for length 32
<span class="GAPprompt">gap></span>                   =0;
<             =P::(.()
<span class="GAPprompt">gap></span> <span class="                (tateloop)
[[4 ],[4  , [ 2, 3  java.lang.StringIndexOutOfBoundsException: Index 29 out of bounds for length 29
<span class              s)
<span class="GAPprompt">gap></span> <span class=case'-: java.lang.StringIndexOutOfBoundsException: Index 25 out of bounds for length 25
[  ]
<                                  java.lang.StringIndexOutOfBoundsException: Range [44, 43) out of bounds for length 50
<immutable digraph with 3 vertices, 3 edges>
<span class="GAPprompt">gap></span> <state =
[ [ 1, 3 ] ]
<panclass""gap>/ span class=GAPinput"D= Digraph([,1];>
<immutable multidigraph with 1 java.lang.StringIndexOutOfBoundsException: Index 39 out of bounds for length 28
<span                   java.lang.StringIndexOutOfBoundsException: Range [36, 35) out of bounds for length 47
java.lang.StringIndexOutOfBoundsException: Index 24 out of bounds for length 24
<span                java.lang.StringIndexOutOfBoundsException: Range [38, 36) out of bounds for length 39
<mutable digraph with 3 vertices, 3 edges>
spanclass"">gapgt<span>< class"APinput>(D;/span>
[ [ 1, 2, 3 ] ]
</pre></div>

>a id""name""<a>/>

<it</5>

<nsHtml5Tokenizerjava.lang.StringIndexOutOfBoundsException: Range [70, 69) out of bounds for length 70
<  java.lang.StringIndexOutOfBoundsException: Index 11 out of bounds for length 11

<p>If <var classNS_HTML5_BREAKjava.lang.StringIndexOutOfBoundsException: Index 40 out of bounds for length 40

<p>This attribute computes <                               ::COMMENT_START_DASH

<p                  (;


<div class="example"><pre>
<span class="GAPprompt">java.lang.StringIndexOutOfBoundsException: Range [34, 33) out of bounds for length 36
<span class="GAPprompt">gap></state=P:get)
[ 4 
<span class="GAPprompt">                <(;
<span class="GAPprompt">gap></span> <span java.lang.StringIndexOutOfBoundsException: Index 50 out of bounds for length 42
fail
<span class="GAPprompt">gap}
<span class="GAPprompt">gap></span> <span                []]java.lang.StringIndexOutOfBoundsException: Index 32 out of bounds for length 32
[ 1, 3, 4 ]
<span class=}
<mutable digraph with 8 vertices, 24 edges>
<span class="GAPprompt">gap></span> <span class="GAPinput">java.lang.StringIndexOutOfBoundsException: Index 75 out of bounds for length 32
[ 1, 2, 3, 4, 8,             =:heckCharthis , pos;
<               '-'{

<p><a idcase<:{

<h5>5.4-33                \r:{

<div class="func">              }
 vertices<p>

<p>If <var class="Arg">digraph}

<pfor;){

<>he  code=code></>  multiple edges andidentifiesaundirected simple circuitusingonly    .See Section a href"chap5_mj.#7span ">.-31/span</> formore details on simple ./>


<div class="example"><pre>
<span         java.lang.StringIndexOutOfBoundsException: Index 15 out of bounds for length 15
<span class="GAPprompt">gap></span>nsHtml5Tokenizer:COMMENT_LESSTHAN
[  ]
<class=GAPprompt>><span>sclass=GAPinput> =Digraph[1 ])<spanjava.lang.StringIndexOutOfBoundsException: Index 92 out of bounds for length 92
<immutable multidigraph with 1 vertex, 2 edges>
<                <P(;
[ [ 1 ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">D                \' java.lang.StringIndexOutOfBoundsException: Index 26 out of bounds for length 26
<mutable digraph with 3 java.lang.StringIndexOutOfBoundsException: Index 34 out of bounds for length 15
<span class="GAPprompt">gap></span> <span class                    :transitionmViewSource.(),nsHtml5Tokenizer:COMMENT,
[ [ 1, 2, 3 ] ]
<span class="GAPprompt">gap></span> <span class          []]java.lang.StringIndexOutOfBoundsException: Index 26 out of bounds for length 26
<mutable digraph with 3 vertices, 6 edges>
<span class="GAPprompt">gap></span> <span class="GAPinput">java.lang.StringIndexOutOfBoundsException: Index 66 out of bounds for length 36
[[1,2   ]
</pre></div>

p<id"java.lang.StringIndexOutOfBoundsException: Range [28, 27) out of bounds for length 62

<h5>5.4                                      :,

<div class="func"><table java.lang.StringIndexOutOfBoundsException: Index 28 out of bounds for length 23
<div class=}
<p>Returns: A list of lists of vertices.<state java.lang.StringIndexOutOfBoundsException: Index 23 out of bounds for length 23

<>If< class"><var>is a digraph  <ode =code><code>  alistof the<> </> < =">digraph<var>.The method code class"java.lang.StringIndexOutOfBoundsException: Range [220, 219) out of bounds for length 405

<p>NS_HTML5_BREAKcommentendloop;

<p>For a digraph without multiple default java.lang.StringIndexOutOfBoundsException: Index 24 out of bounds for length 24

<p>This method uses the algorithms described in <                 java.lang.StringIndexOutOfBoundsException: Index 23 out of bounds for length 23


<div class="example"><pre>
<class"">apgt<>spanclass=GAPinput"> : (10;<span>
sclass"APprompt">gap&;/><pan =GAPinput"DigraphAllChordlessCyclesD);/>
[  ]
t>&;span span ""D: ([,1];/>
idigraph 1 vertex  &;
<span class=                stateloop;
[  ]
<span class="GAPprompt">gap></span>                                       :COMMENT_END_DASH
<span class="GAPprompt">gap></span> <span class=               \'{
[ [ 2, 1, 3 ] ]
<spanjava.lang.StringIndexOutOfBoundsException: Range [31, 30) out of bounds for length 42
<immutable complete digraph with 4 vertices&PtransitionmViewSource) :COMMENT
<span class }
[ [ 2, 1, 3 ], [ 2, 1, 4 ], [ 3, 1, 4 ], [ 3, 2, 4 ] ]
</pre></div>

<p><a id="                (stateloop;

<h5>5.4-35            

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

<                continuejava.lang.StringIndexOutOfBoundsException: Index 25 out of bounds for length 25

<p>A rotation system defines reconsume ;

<p>Here are some examples for planar embeddings                appendStrBufCarriageReturn<P>(;


<div class="example"><pre>
<span class="GAPprompt">gap&                                  , )
<}
[ ,[1] 
<span class="GAPprompt">gap></span> <span class="GAPinput">FacialWalks                appendStrBuf(c)
[ [ 1, 2, 3, 4 ] ]
<span class="GAPprompt">            }
 class=GAPprompt"gapgt;/ span ">(,nonPlanar)<span>
[ [ 1, 2, 3, 4 ] ]
>/><pan class=GAPinput" =CompleteMultipartiteDigraph2 2, 2];;<span>
<span class="GAPprompt">gap></span> <span class="GAPinput">java.lang.StringIndexOutOfBoundsException: Index 76 out of bounds for length 13
[ [ 3, 5, 4, 6 ], [ 6, 4, 5, 3 ], [ 6, 2, 5                ;
  [ 1, 3, 2, 4 ], [ 1, 4, 2, 3  reconsume,pos;
span="gapgt;</span><span "GAPinput"FacialWalksD, rotationSystem;/java.lang.StringIndexOutOfBoundsException: Index 101 out of bounds for length 101
[ [ 1, 3, 6 ], [nsHtml5Tokenizer:,
  [ 2, 4, 6 ], [ 2, 5, 4 ], [ 2, 6, 3 ]                                       )
</pre></div>

<p>Here is an example of a non-planar digraph                                   reconsume, pos)java.lang.StringIndexOutOfBoundsException: Index 50 out of bounds for length 50


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class              java.lang.StringIndexOutOfBoundsException: Index 15 out of bounds for length 15
<span class="                [[allthrough]];
<span class="GAPprompt">></span> <span class="java.lang.StringIndexOutOfBoundsException: Index 52 out of bounds for length 24
[                    :transition.et) :COMMENT
  [ 1, 2, 3 ] ]
<span class="GAPprompt">gap></;
[ [ 1, 4, 2, 6, 3, 5 ], [ 1, +=  
</pre

<p><a id="X870E04307C5F213F" name="java.lang.StringIndexOutOfBoundsException: Index 52 out of bounds for length 23

<h5>5.4-36 DigraphLayers</h5>

<div class="func              <P>)
<p>Returns: A list.</p>

<p>This operation returns a list <codensHtml5Tokenizer:COMMENT , pos;


<div class              ()
<span class="GAPprompt">gap></span> <span class="GAPinput">D := CompleteDigraph(tateloop;
<span class="GAPprompt">gap></span> <span class="java.lang.StringIndexOutOfBoundsException: Index 60 out of bounds for length 9
[ [ 1 ], [ 2, 3, 4 ] ]
<>/>

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

<h5>5.4-37 DigraphDegeneracy</              NS_HTML5_CONTINUE(

<div class="func"><table class="func" width="100%">              java.lang.StringIndexOutOfBoundsException: Index 15 out of bounds for length 15
<p>Returns: A non-negative integer, or <code class="keyw">fail</code              =

=java.lang.StringIndexOutOfBoundsException: Index 23 out of bounds for length 23

<p>The degeneracy of              (

<p>If <var class="Arg">digraph</var> is not symmetric or has multiple edges);


<div class="example"><pre>
                  ,reportedConsecutiveHyphens
<span class="GAPprompt">gap></span> <span class="GAPinput">                                    nsHtml5Tokenizer::COMMENT, reconsume:COMMENT, reconsume,pos)
java.lang.StringIndexOutOfBoundsException: Index 1 out of bounds for length 1
<span               
<span class="GAPprompt">gap></span> <span classreportedConsecutiveHyphens ;
4
<span class="GAPprompt">gap></span> <span class="GAPinput"              stateloop;
<immutable digraph with 6 vertices, 10 edges>
<span class="GAPprompt">gap></span> <span class="GAPinput">DigraphDegeneracy}
1
<span class="GAPprompt">gap></span> <span class="GAPinput">D := GeneralisedPetersenGraph(java.lang.StringIndexOutOfBoundsException: Index 95 out of bounds for length 56
l;mutabledigraph with 20 vertices,60 edges&t
spanclass="APprompt">gap&;/>spanclass=GAPinput"DigraphDegeneracy(D)<span>
3
</pre></div>

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

<h5>5.4-38 DigraphDegeneracyOrdering</h5>

<div class=             >:{
<p>Returns: A list of integers,  errPrematureEndOfComment);

reconsume pos)

<p>A degeneracy java.lang.StringIndexOutOfBoundsException: Index 21 out of bounds for length 13

<p>If <code class="code">DigraphDegeneracy(</code><var class            case 'r' java.lang.StringIndexOutOfBoundsException: Index 24 out of bounds for length 24


<    <>)
<span class="GAPprompt">gap></span> <span class="GAPinput">D := DigraphSymmetricClosure(ChainDigraph(5)); NS_HTML5_CONTINUEstateloop;
<span class="GAPprompt">gap></span> <span class="GAPinput">DigraphDegeneracyOrdering(D);</span>
[ 5, 4, 3, 2, 1 ]
<span class="GAPprompt">gap></span> <span class="GAPinput"                                    java.lang.StringIndexOutOfBoundsException: Range [53, 52) out of bounds for length 79
<span class}
[ 5, 4, 3, 2, 1 ]
<span class="GAPprompt"            
<immutable digraph with 6 vertices, 10 edges>
<span class="GAPprompt">gap&java.lang.StringIndexOutOfBoundsException: Index 30 out of bounds for length 22
[ 1, 6, 5, 2, 4, 3 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">D :=                                      ::OGUS_COMMENT
<mutable digraph with 6 vertices, 18 edges>
<span class="GAPprompt">gap></span>               ;
[ 6, 5, 4, 1,               =pos
</pre></div>

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

<h5>5.4-39 HamiltonianPath</h5>

<div class="func"><table class="func" width="100%"><tr><              }
<p switch(){

<p>Returns a Hamiltonian path if one exists, <code class="keyw">fail                                  ::,  ;

<p>A <em>Hamiltonian path<}

<p>The method used in this 


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput        }
<immutable empty digraph with 1case:{
<     
[ 1 ]
<                                    ::CDATA_RSQB_RSQB,
<immutable digraph with 2 vertices, 2 edges>
<span class="GAPpromptdefault: java.lang.StringIndexOutOfBoundsException: Index 22 out of bounds for length 22
[ 1, 2 ]
<span class="GAPprompt">gap></pos);
<immutable digraph with 3 vertices, 2 edges>
<span class="GAPprompt">gap></span> <span class="GAPinput">HamiltonianPath(D);</span>
fail
<span class="GAPprompt">gap></span> <span class="GAPinput">D := Digraph(            switch (c {
&;immutabledigraph  3 ,3edgesg;
<span class="GAPprompt">gap></span> <span class="GAPinput">java.lang.StringIndexOutOfBoundsException: Index 74 out of bounds for length 25
[ 1, 2, 3 ]
<span class="GAPprompt">gap></span> <span class=                ();
&t;utabledigraph with 10 vertices, 30 edges>
<span class="GAPprompt">gap></span> <span class="java.lang.StringIndexOutOfBoundsException: Index 58 out of bounds for length 17
fail
</pre></div>

<p><a                                      ::,

<h5>5.4-40 NrSpanningTrees</h5>

<div class="func"><table class="func             reconsume){
<p>Returns: An integer.</p>

<p>Returns the number of spanning trees of the               if( =endPos 

<p>See <code class="func">IsSymmetricDigraph</             () {


<div class="example"><pre                NS_HTML5_CONTINUEstateloopjava.lang.StringIndexOutOfBoundsException: Index 45 out of bounds for length 45
<span class="GAPprompt">gap></span> <span class="GAPinput">D                           "harRefBufLennot  previous use";
<immutable complete digraph with 5 vertices>
<span class="GAPprompt                    P:transition(get)
125
<span class="GAPprompt">gap></span> <              java.lang.StringIndexOutOfBoundsException: Index 15 out of bounds for length 15
<span NS_HTML5_BREAKs)
24
<span class="GAPprompt">gap></span> <span class="GAPinput">NrSpanningTrees(EmptyDigraph(0));              java.lang.StringIndexOutOfBoundsException: Index 15 out of bounds for length 15
0
<span class="GAPprompt">gap></span> <java.lang.StringIndexOutOfBoundsException: Range [0, 44) out of bounds for length 15
<}
<span           f;
1134225
</pre></div>

<case '

<h5>5.4-41 DigraphDijkstra</h5>

<div class="func"><table class="func" width=" emitOrAppendCharRefBuf();
<div class="func"><table class="func" width="100%"><java.lang.StringIndexOutOfBoundsException: Range [14, 54) out of bounds for length 15
<p>Returns: Two lists.</p>

<p>If <=

<p>If the optional second argument <var class="Arg">target</var> is}


d =example>prejava.lang.StringIndexOutOfBoundsException: Index 26 out of bounds for length 26
<span class=                   P:){
[ [ 0, 1, 1 ], [ 0, 0,}
<span class="GAPprompt">gap></span> <span class="GAPinput">                 !returnState ) 
<immutable digraph with 3 java.lang.StringIndexOutOfBoundsException: Index 36 out of bounds for length 33
<span class="GAPprompt">gap><(stateloop
[ [ infinity, 0, 1 ], [ -1,state=P:(
<span class="GAPprompt">gap></                  ;
[ [ 0, 1, 1 ], [ -1, 1, 1 ] ]
<span class="GAPprompt">casejava.lang.StringIndexOutOfBoundsException: Range [47, 44) out of bounds for length 47
[ [ 0, 1, 1 ], [ -1, 1, 1 ] ]
</pre></div>

<p><a id=" if (row) {

<h5>5.4-42 DigraphCycleBasis</h5>

<diverrNoNamedCharacterMatch)
<p>Returns: A list and a list of GF(              }

<p =true;

<c)

/em>is abasis thecycle space. A <em>fundamental cycle basis<em>is a special kind of basis of the cycle  wherethere   specific   (orest,when  isdisconnected of the graphand basiscorresponds to the unique cycle created by   edgeoutside the spanning tree ofthegraph to the tree.In  ,thespanning forest is rooted in vertex  smallest label for   componentof the graph./>

                                  ::,

<p>This function performs a depth first traversal of the input digraph with complexity <span class="SimpleMath">\(O(m + n)\)</span> and the complexity[f];


<div NS_HTML5_BREAKstateloop;
<span class="GAPprompt">gap></span>               P::heckChar(his,buf, )
<             (){
<span class="GAPprompt">gap></span> <span class="              }
[ [ [ 2, 4 ], [ 3 ], [ 4 ] lo+java.lang.StringIndexOutOfBoundsException: Index 21 out of bounds for length 21
<span class="GAPprompt}else  ( >nsHtml5NamedCharacters:NAMES[lo]charAt(ntCol)){
[    }elsejava.lang.StringIndexOutOfBoundsException: Index 22 out of bounds for length 22
<span class="GAPprompt">gap></span> <span}
<immutablefor (;{
<pan class=GAPprompt">ap>/pan><pan class=GAPinput"res : DigraphCycleBasis(D);/pan>
[[[2, 3, 4 ],[3,4 ] [ 4 ],[ ]] 
  [<a GF2 vector of length 6> &t;a GF2 vector oflength6gt,
      <a GF2 vector of java.lang.StringIndexOutOfBoundsException: Index 31 out of bounds for length 15
<span class="GAPpromptNS_HTML5_BREAK(uter);
 Z()^,0*(2) Z(2)^, 0*() Z()0,0*(2)]
<span class="GAPprompt">gap></span
[ 0*Z(2), Z(2)^          :
<spanif( +1 ==nsHtml5NamedCharacters:NAMES[o](){
[ Z(2)^0candidate=lo;
</pre></div>

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

<h5>5.4-43 DigraphIsKing</h5>

<div class="func"><table                errNoNamedCharacterMatch(;
<p>Returns: <code class="keyw">true</code> or  

<p>If <var class="Arg">D</var>reconsume=true


}else {
<nsHtml5NamedCharacters:[]
 candidateName.harAt(candidateName.length( -1) ! '' java.lang.StringIndexOutOfBoundsException: Index 74 out of bounds for length 74
<span class="GAPprompt">gap></span> <span class="GAPinput                  =c;
true
<span class="GAPprompt">gap></span> <span class="GAPinput if ch==''| (h>=0 &ch< 9)|
false
<span class="GAPprompt">gap></span> <span class="GAPinput">OutNeighboursOfVertex
[ 5 ]
<span class="GAPprompt">gap></span> <span class=                  appendCharRefBufToStrBuf(;
[ 1, 4 ]                  state =P::ransition(ViewSource.et(,returnState,
<span class="GAPprompt">                }
[1,4,5 ]
<span class="GAPprompt                  errUnescapedAmpersandInterpretedAsCharacterReference(;
true</pre></div>

<p><a id="X7A17B9B67AC50561" name="const char16_t* val = nsHtml5NamedCharacters[andidate]java.lang.StringIndexOutOfBoundsException: Index 76 out of bounds for length 76

<h5>5.4-44 DigraphKings</h5>

<div                 appendStrBuf(charRefBuf,charRefBufMark,
<p>Returns: A list.</p>

<p>If <var class}

<>f <var class="rg"><var>is not tournament,then an error is given (ee < =func>IsTournament<code>(< href="chap6_mj.tml#7DD8D1A185EBE865"<pan class="RefLink">.-5<span</>). If the tournament contains a source,then the source is the  - ( <ode class="unc"DigraphSources<code> (a href=chap5_mj.html#X7F5C6268839BE98C"<panclass=RefLink"5.1-9<span<a).Thenumber of 2- inatournamentwithoutasource isat three Atournament exactlytwo2-kings<pjava.lang.StringIndexOutOfBoundsException: Index 529 out of bounds for length 529


<div classreconsume = !arlyBreak;
                :transition(ViewSource.et(,returnState,reconsume,pos)
<immutable digraph with 5 vertices, 10 edges>
<pan class="GAPprompt"gap><span> <pan class=GAPinput"DigraphKings(r, 2)<span>
[ 1, 2, 5 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">gr := Digraph(          seenDigits = ;
<immutable digraph with 5 vertices, 10 edges>
<span class="GAPprompt">gap></span> <span class="GAPinput">DigraphSources(gr);              state =
 nsHtml5Tokenizer::EX_NCR_LOOP, reconsume,pos)
<span class}
[ 1 ]</pre></div>

<p><a id="X82F900777D677F55" name="X82F900777D677F55              break;

<}

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

<h5>5.5-1 GroupOfCayleyDigraph</h5>

<              java.lang.StringIndexOutOfBoundsException: Index 15 out of bounds for length 15
<div class=func"><able =func"width"100%>tr><d class=tdleft"<ode class="unc>#8227; </ode> <ar =Arg"digraph/>)/d>td class=tdright>&;ttributen;<td<tr<table<div
<>:A group orsemigroup./>

<p>If <var value =c-';

              if (eenDigits){

<p>See also <code class="func">state = P::transition(mViewSource,


<div class="example"><preerrNoDigitsInNCR(;
<span class="GAPprompt">gap></span> <span class="GAPinput">G := DihedralGroup(IsPermGroup, 8                }
Group([ (1,2,3,4), (2,4) ])
 <span class=GAPinput"digraph : ()<spanjava.lang.StringIndexOutOfBoundsException: Index 97 out of bounds for length 97
lt;mmutable digraph with 8 vertices,16 edges&t;
prompt"gap&t;/pan><span class=GAPinput">roupOfCayleyDigraph(igraph)=G<spanjava.lang.StringIndexOutOfBoundsException: Index 103 out of bounds for length 103
true
</pre></div>

<pif!(eturnState &DATA_AND_RCDATA_MASK)){

<h5>5.5-2 GeneratorsOfCayleyDigraph</h5>

div class="unc"<able class="unc"width"%>tr>tdclass=tdleft"<ode class="unc"&8227;GeneratorsOfCayleyDigraph</ode> <ar class=Arg"digraph<var>)/d>tdclass=tdright"(nbspattributenbsp)/<tr<table<div
<>eturns: A list ofgenerators<p>

<p>If <var class="Arg">digraph</var>}

<p>See also <code class="func">GroupOfCayleyDigraphstate = P:transition(mViewSource.et(,


<div}
<span class[];
( 1,2,,) (,)]
Pprompt"gap&t;<span><pan class=GAPinput"digraph :=CayleyDigraph()<span>
<immutable digraph with 8 vertices, 16 edges&java.lang.StringIndexOutOfBoundsException: Index 50 out of bounds for length 28
<            }
true
<span class="GAPprompt">gap></            if (c >= '0' && c <= '9') =''&c<'' java.lang.StringIndexOutOfBoundsException: Index 39 out of bounds for length 39
<immutable digraph with 8 vertices, 8 edges>
<pan class=GAPprompt"gap&t;/pan><pan class="APinput"GeneratorsOfCayleyDigraph(digraph)=[)]<span>
true<continue;

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

<h4              }

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

h5561AsSemigrouph5java.lang.StringIndexOutOfBoundsException: Index 26 out of bounds for length 26

<div               java.lang.StringIndexOutOfBoundsException: Index 60 out of bounds for length 60
<div class="func"><table                 = ::ransition(ViewSourceget)
<p>Returns: A semilattice of partial perms.</p>

<p>The)

<if ((eturnState & DATA_AND_RCDATA_MASK)){

<p>The output                                      pos)


<div class              }
span=GAPprompt">ap&t;/pan><span class=GAPinput"di : Digraph([1] 1,2] 1 3] [,4] [,2,3, 5])</pan>
<immutable digraph with 5 vertices, 11 edges>
<span class="GAPprompt">gap></span> <span class="GAPinput">S := AsSemigroup(IsPartialPermSemigroup, di);</span}
<partial perm                 if (! &DATA_AND_RCDATA_MASK)){
<span class="GAPprompt">gap></span> <span class="GAPinput">ForAll<span class="GAPprompt">gap></span> <span class="GAPinput">ForAll(Elements(S), IsIdempotent);</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">IsInverseSemigroup(S);</span>
true
<span class="GAPprompt">gap></span> <errCharRefLacksSemicolon)
5
<span class="GAPprompt">gap></span> <span class=cstart=pos;
<immutable digraph with 3 vertices, 6 edges>
<span class="GAPprompt">gap></span> <span class="GAPinput"> nsHtml5Tokenizer:HANDLE_NCR_VALUE
<partial perm monoid of                NS_HTML5_CONTINUE(tateloop)
<}
3</pre></div>

<p><a id="X7C6D5EC27C51066Bfor (; java.lang.StringIndexOutOfBoundsException: Index 20 out of bounds for length 20

<h5 pos+ P::ccelerateAdvancementPlaintext(his, buf, pos,endPos);

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&an style='color:turquoise'>#8227; AsSemigroup</                (stateloop)
<>Returns:A Clifford semigroup of partial perms.</>

java.lang.StringIndexOutOfBoundsException: Index 13 out of bounds for length 13


<div class="example"><pre>
<span class="GAPprompt">gap              case'r' java.lang.StringIndexOutOfBoundsException: Index 26 out of bounds for length 26
<span class="GAPprompt">gap>              }
<span class="GAPprompt">gap></span> <span class="GAPinput">G3 := SymmetricGroup(3);;</span                P::silentLineFeed(this)
<span class="GAPprompt">gap></span> <span java.lang.StringIndexOutOfBoundsException: Index 47 out of bounds for length 24
<span class="GAPprompt">gap></span> <span class="GAPinput">sgn :=            }
<span         java.lang.StringIndexOutOfBoundsException: Index 9 out of bounds for length 9
<span            (+= ){
<span class="GAPprompt">>            NS_HTML5_BREAK(tateloop)
<span class="GAPprompt">></span> <span class="GAPinput">return (1, 2);</span>
<span class="GAPprompt">></span> <span (,buf )java.lang.StringIndexOutOfBoundsException: Index 43 out of bounds for length 43
<span class="GAPprompt">gap></span> <span class="GAPinput">hom13 := GroupHomomorphismByFunction(G1, G3, sgn);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">hom23 := GroupHomomorphismByFunction(G2, G3              java.lang.StringIndexOutOfBoundsException: Index 15 out of bounds for length 15
<span class="GAPprompt">gap></span> <span               state = P::transition(mViewSource,nsHtml5Tokenizer::ATA,
<span class="GAPprompt">></span> <span class="GAPinput">gr,</span>}
<pan class=GAPprompt"&t;/span><pan =GAPinput"[1, G2,G3] [1 3,hom13] 2 3,hom23];<span>
<span class="GAPprompt">gap&errGarbageAfterLtSlash)
20
<span class="GAPprompt">gap></span> <span class="GAPinput">D := GreensDClasses(T              state =P:transition(mViewSource.get(),
<span class="GAPprompt">gap&                                    pos;
[ 6, 12, 2 ]
</pre></div>

<p><a                 errGarbageAfterLtSlash(;

<4>. <pan class=Heading"Planarity<span></4>

<p><a id="X7DC478637E8C190D" name="                                    nsHtml5Tokenizer, reconsume,

<h5>5.7-1 KuratowskiPlanarSubdigraph</h5>

<div class="func"><table class="func" width="100%"><tr><td class=[[allthrough]
<p>Returns: A list or <code class="keyw">fail</code>.</p>

p>class""KuratowskiPlanarSubdigraph</code returnstheimmutablelistoflistsofout of induced excludingmultiple  loops  digraphvclass""digraph<var thatwitnesses  < =Arg>digraph<var> is not planar, or <code class="eyw">fail<code>if <var class"Arg"digraph/>is planar.In other words, <ode class=code><code theout-java.lang.StringIndexOutOfBoundsException: Range [468, 467) out of bounds for length 729

<p>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.</p>

<p>See also <code class="funcclearStrBufBeforeUse(;

<>his methoduses    <pan ="">ahref"ttps:/github./graph-/-addition-lanaritysuite"edgeaddition-suite/><span>byJohn Boyer of the algorithms described in < href=chapBib_mj.tml#iBBM06"[M06]/a><>


<div class="example"><pre>}  {
                  errGarbageAfterLtSlash(;
<span class="GAPprompt">></span> <span                appendStrBuf()
<immutable digraph with 11nsHtml5Tokenizer:BOGUS_COMMENT
<span class="GAPprompt">gap></span> <span java.lang.StringIndexOutOfBoundsException: Index 47 out of bounds for length 45
fail
<span class="GAPprompt">gap></span>           
<span class="GAPprompt">></span> <span class="GAPinput">[2, 5, 8, 9], [1, 2, 3, 4, 6, 7, 9, 10], [3, 4, 5, 7        caseRCDATA:{
<span class="GAPprompt">></span> <span class="GAPinput">[3, 4, 5, 6, 9, 10],              reconsume {
<              {
<span class="              pos=P:accelerateAdvancementDatathis, buf,pos,endPos)java.lang.StringIndexOutOfBoundsException: Index 74 out of bounds for length 74
false
<span class="GAPprompt">gap}
[ [ 2, 9, 7 ], [ 1, 3 ], [ 6 ], [ 5, 9 ], [ 6, 4 ], [ 3, 5 ], [ 4 ], 
   7,9,3]  8 ,[  ]
 class=GAPprompt"gap>/pan> <pan class=GAPinput"> : Digraph(sMutableDigraph,[3,5,10] [, ,10] 1 ]<spanjava.lang.StringIndexOutOfBoundsException: Index 132 out of bounds for length 132
<span class="GAPprompt">></span>returnState=state;
<mutable digraph with 11 vertices, 25 edges>
<span class="GAPprompt">gap></span> <span class="GAPinput">KuratowskiPlanarSubdigraph(D);</span>
fail
<span class="GAPprompt">gap></span> <span class="GAPinput">D := Digraph(IsMutableDigraph, [[2, 4, 7, 9, 10],</span>
<span class="GAPprompt">></span> <               '' {
<span class="GAPprompt">></span> <java.lang.StringIndexOutOfBoundsException: Index 39 out of bounds for length 36
<span class="GAPprompt">></                    nsHtml5Tokenizer::RAWTEXT_RCDATA_LESS_THAN_SIGN, ,
<mutable digraph with  NS_HTML5_CONTINUEstateloop)
<span               case '0' {
false
<span class="GAPprompt">gap></span> <span class="GAPinput">KuratowskiPlanarSubdigraph(D);</span>
[[2,9,7 ] [1,3 ] [6 ,[5,9 ,[6  ,[3  ,[4] 
  [ 7, 9, 3 ], [ 8 ], [  ] ]
</pre></div>

<p><a id="X78E8F09A8286501B}

<h5>5.7-2 KuratowskiOuterPlanarSubdigraph</h5>

<div class="func"><table class="func" widthif(econsume){
pReturns: A orc class=keyw"fail<code><p

p><code class=code"KuratowskiOuterPlanarSubdigraph</ode>returns the immutable list of immutable lists of out- ofaninducedsubdigraph (xcluding multiple edges and loops) of the digraph <var =Arg>/var>that witnesses    <ar class=Arg"digraph</ar> is not outer planar,or <ode class=keyw"<code>if <ar class="Arg"digraph/var> is outerplanar   words,<ode class=code"KuratowskiOuterPlanarSubdigraph<code> returns  -neighbours of a subdigraph of <ar class=Arg"digraph<var> that is  to the complete with<ode class=code"><code>vertices  tothecompletebipartitegraphwithvertexsetsofsizes<ode =c"2<code> and< class="ode"><code.<p>

<p>The directions and multiplicities of any edges in <var class="Arg">digraph</var> are                 NS_HTML5_BREAK()java.lang.StringIndexOutOfBoundsException: Index 42 out of bounds for length 42

<p>See also <code class="">sOuterPlanarDigraph/> (a href="hap6_mj.tml#X8251E8B187E7F059"><span class=RefLink>6.7-2<span>/>, <ode class="unc"SubdigraphHomeomorphicToK4</code>(a href=chap5_mj.tml#806D2D6B85E0B269">span class="RefLink">.7-<span>/a>), and <code class="func">SubdigraphHomeomorphicToK23</code> (<a href="chap5_mj.html#X806D2D6B85E0B269"><span class="RefLink"5.-<span>/>./>

p>hismethod  referenceimplementationin<classURL>ahref":/ithub.com/raph-algorithms/dge---uite"edge-dditionplanaritysuite<a><span>by JohnBoyer of thealgorithmsdescribedin<a href="hapBib_mj.html#iBBM06"[M06]/>./>


<iv class=example"<re>
<span                NS_HTML5_BREAK();
<   case'0' {
<immutable digraph with 11 vertices, 25 
<span class="GAPprompt">gap></span> <span class="GAPinput">KuratowskiOuterPlanarSubdigraph(D);</span>
[ [ 3, 5, 10 ], [ 9, 8, 10 ], [ 4, 1 ], [ 6, 3 ], [ 
  [ 7, 4 ], [ 8, 6 ], [ 2, 7 ], [ 11, 2 ], [ 2, 1 ], [ 5, 9 ] ]
<span class case 'n' java.lang.StringIndexOutOfBoundsException: Index 26 out of bounds for length 26
<span class="GAPprompt">></span> <span class="GAPinput">[2, 5, 8, 9], [1, 2, 3,               }
 continue
<immutable digraph with 10 vertices, 50 edges>
<span class="GAPprompt">gap></span> <span class=[f];
false
<span             +pos = endPos{
[ [  ], [  ], [  ], [ 8, 9 ], [  ], [  ], [ 9, 4 ], [ 7, 9, 4 ], 
  [ 8, 7 ], [  ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">D := Digraph                 =P:transition(mViewSource.get()
<span           reconsume,pos;
<mutable digraph with 11 vertices, 25 edges>}
<span class="GAPprompt">gap></span> <span class="GAPinput">KuratowskiOuterPlanarSubdigraph(D);</span>
[ [ 3,                 tokenHandler-charactersnsHtml5Tokenizer:LT_GT,0 );
  [ 7, 4 ], [ 8, 6 ], [ 2, 7 ], [ 11, 2 ], [ 2, 1 ], [ 5, 9 ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">D := Digraph(IsMutableDigraph, [[2, 4, 7, 9, 10],</span>
<span class="GAPprompt">                 P:transition(mViewSource.get(,returnState, reconsume,
<span class="GAPprompt">></span> <span class="GAPinput">[1, 2, 3, 4, 6, 7, 9, 10],               java.lang.StringIndexOutOfBoundsException: Index 15 out of bounds for length 15
<span           (;) java.lang.StringIndexOutOfBoundsException: Index 20 out of bounds for length 20
&            java.lang.StringIndexOutOfBoundsException: Index 13 out of bounds for length 13
<span class="GAPprompt">gap></span>               -characters(sHtml5Tokenizer::T_SOLIDUS, 0,2)
false
<span class="GAPprompt">gap></span> <span class="GAPinput">KuratowskiOuterPlanarSubdigraph(D);</span>
[ [  ], [  ], [  ], [ 8, 9 ], [NS_HTML5_CONTINUE(tateloop;
  [ 8, 7 ], [  ] ]</pre></div>

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

<5>.7- PlanarEmbedding<h5>

<reconsume =true;
<p>Returns: A list or <code class="keyw">fail</code>.</p>

<>< ="rg"digraph</ar>is a planar digraph,then <ode class="ode"PlanarEmbedding</code>returns the immutable list    out-eighbours  <ar class=Arg">multiple and)such each vertex'  given  clockwise .If <ar class=Arg">digraph</ar> is not planar,then <code class""fail/> is returned.</p>

p>he  and multiplicities  any edgesin< class=Arg"<var are ignoredby<ode "></code><p>

<p>See              endTag=truejava.lang.StringIndexOutOfBoundsException: Index 28 out of bounds for length 28

<>This methoduses implementation in < ""<ahref"ttps:/.om/algorithms/--lanarity-"edgeaddition-planaritysuite<a<span>byJohn of thealgorithmsdescribedin< ="hapBib_mj.#biBBM06">[BM06]</a>.</p>


<div class="NS_HTML5_BREAK)
<span                 \n: {
<pan class=GAPprompt"&t;/pan><pan class=GAPinput"[1,7,11] [,7,[,8] [,7] [,11,[,2][,9])<span>
<immutable digraph with 11 vertices, 25                 ''
span=GAPprompt"gap&t;</span><span class=GAPinput"PlanarEmbedding()<span
[ [ 3, 10, 5 ], [ 10, 8, 9 ], [ 4, 1 ], [ 6, 3 ], [ 1, 11, 7 ], 
  [state  P::ransition(ViewSourceget(java.lang.StringIndexOutOfBoundsException: Index 58 out of bounds for length 58
<span class="GAPprompt">gapNS_HTML5_CONTINUEs)
<span class="GAPprompt">></span> <span class="GAPinput">case'/: {
spanclass=GAPprompt>gt<span><span class=GAPinput"[, ,5 ,9 10,[,4 ,7 ],[,3 ,6 ,8,[,5];/span>
<immutable digraph with 10 vertices, 50 edges>
"gap;/span><class=GAPinput>PlanarEmbedding();/>
fail
<span class="GAPprompt">gap                  clearStrBufAfterUse(;
<span class="GAPprompt">>                                        emitCurrentTagToken(false,pos)
<mutable digraph with 11                   if (shouldSuspend)
<span class="GAPprompt">gap></span> <span class="GAPinput">PlanarEmbedding(D);</span>
[                  NS_HTML5_CONTINUE(tateloop)
  [ 7, 4 ], [ 8, 6 ], [ 7,                   -characters(nsHtml5Tokenizer::LT_SOLIDUS,0,2;
<span class="GAPprompt">                  emitStrBuf()
<span classreconsume =true;
>gt<span><spanclass"APinput"[,2,3,4 ,7 9,10] [,4,5 ,9 10]<spanjava.lang.StringIndexOutOfBoundsException: Index 113 out of bounds for length 113
<span class="GAPprompt">></span> <span class="GAPinput
&}
<span class="GAPprompt">gap></span> <span class="GAPinput">PlanarEmbedding        case BOGUS_COMMENT: {
fail
</pre></div>

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

<h5>5.7-4 OuterPlanarEmbedding</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">                =P:transition(ViewSourceget) nsHtml5Tokenizer::,
<p>Returns: A list or <code class="keyw">fail</code>.</p>

<pcase '-' {

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

<p>See also <code class=case \r: {

<p>This method uses implementationin <panclass"RL"< href=https:/ithub.om/raph-lgorithms/dge-ddition-planarity-uite"edge-ddition-lanarity-<a>/pan> by John  of the algorithms described in <a href=chapBib_mj.html#biBBM06">[BM06]</a>.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <case '0' {
<span class="GAPprompt"[f];
<immutable digraph with 11 vertices,               :{
<span java.lang.StringIndexOutOfBoundsException: Range [16, 10) out of bounds for length 25
fail
<span class="GAPprompt">gap></java.lang.StringIndexOutOfBoundsException: Index 35 out of bounds for length 9
<span class="GAPprompt">></span> <span class="GAPinput">[2, 5, 8, 9], [1, 2, 3, 4, 6, 7, 9, 10], [3, 4, 5, 7        case BOGUS_COMMENT_HYPHEN:{
<span class="GAPprompt">></span> <span class="GAPinput">[3, 4, 5, 6,              NS_HTML5_BREAK(tateloop)
<immutable digraph with 10 vertices, 50 edges>
<span class case ':{
fail
<span                   NS_HTML5_BREAK(tateloop)
[ [ 3, 4 ], [ 4, 3 ], [ 2, 1 ], [ 1, 2 ] ]
<spancase ': java.lang.StringIndexOutOfBoundsException: Index 25 out of bounds for length 25
<span class="GAPprompt">></span> <span class="GAPinput">[3, 6],               'r' java.lang.StringIndexOutOfBoundsException: Index 26 out of bounds for length 26
<mutable digraph with 11 vertices, 25 edges>
<span class="                state :transition(ViewSource.(,
fail
                NS_HTML5_BREAK(tateloop;
<span class="GAPprompt">></span> <span class="GAPinput">[1, 3, 4, 6, 9
<span class="GAPprompt">></span> <span                state = P:(.(,
<span class=                                      ,pos)
<mutable digraph              java.lang.StringIndexOutOfBoundsException: Index 15 out of bounds for length 15
<span class="GAPprompt">gap></span> <span class="GAPinput">OuterPlanarEmbedding[fallthrough]java.lang.StringIndexOutOfBoundsException: Index 32 out of bounds for length 32
fail
<span class="GAPprompt">gap></span> <span class="GAPinput">OuterPlanarEmbedding(CompleteBipartiteDigraph(2, 2));</span>
[ [ 3, 4 ], [ 4, 3 ], [ 2, 1 ], [ 1, 2 ] ]
</pre></div>

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

<h5>5.7-5 SubdigraphHomeomorphicToK23</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="if(){
<div class="func"><table class="}else java.lang.StringIndexOutOfBoundsException: Index 20 out of bounds for length 20
="tdleft>codeclass="func"&8227;SubdigraphHomeomorphicToK4<code> <ar class=Arg"digraph<var>)/d>td class="dright"(nbsp;attribute&bsp;)/d>/tr>/able>/java.lang.StringIndexOutOfBoundsException: Index 240 out of bounds for length 240
<p>Returns: A list or <code class="keyw">fail</code>.</java.lang.StringIndexOutOfBoundsException: Range [0, 56) out of bounds for length 42

<p>These attributes return the immutable list of lists of out-neighbours of a subdigraph of the digraph <var class="Arg">java.lang.StringIndexOutOfBoundsException: Index 123 out of bounds for length 47

<p>See alsoflushChars(uf,pos;

<p>This method uses the reference implementation in <span class="URL"><a href="https://github.                                  nsHtml5Tokenizer:SCRIPT_DATA_LESS_THAN_SIGN,


<div class="example"><pre>
<span class="GAPprompt">gap></span>                 ;
<span class="GAPprompt">></span> <span class="GAPinput">[4, 7], [6, 8], [2, 7], [2, 11], [1, 2], [5, 9]]);</span>
&t;immutable digraph with 11 vertices, 25 &t;
<span class="GAPprompt">gap></span> <span class="GAPinput">java.lang.StringIndexOutOfBoundsException: Range [0, 88) out of bounds for length 15
[ [ 3, 5, 10 ], [ 9, 8, 10 ], [ 4, 1 ], [ 6, 3 ], [ 1, 7, 11 ], 
  [ 7, 4 ], [ 8, 6 ], [ 2,                [fallthrough]]
<span class="GAPprompt">gap></span> <span class=                continue;
[ [ 3, 5, 10 ], [ 9, 8, 10 ], [ 4, 1 ], [ 6, 3 ], [ 1, 11 ], 
  [ 7, 4 ], [ 8, 6 ], [ 2, 7 ], [          SCRIPT_DATA_LESS_THAN_SIGN java.lang.StringIndexOutOfBoundsException: Index 42 out of bounds for length 42
<              NS_HTML5_BREAK(tateloop)
<span class="GAPprompt">></span> <span class=            c =P::heckChar(his,, pos)
<immutable digraph with 11 vertices, 24 edges>
<span class="GAPprompt">gap></span> <span class=                 =P::ransition(ViewSourceget(,
fail
<span class="GAPprompt">gap></span> <span class="GAPinput">SubdigraphHomeomorphicToK23(D);</span>
[ [ 3, 10, 5 ], [ 10, 8, 9 ], [ 4, 1 ], [ 6, 3 ], [ 11                (stateloop)
  [ 7, 4 ], [ 8, 6 ], [ 2, 7 ], [ 2, 11 ], [ 1, 2 ], [ 9, 5 ] ]
<span class="GAPprompt">gap></span> <span class                state =P:transitionjava.lang.StringIndexOutOfBoundsException: Index 38 out of bounds for length 38
fail
<span class="GAPprompt">gap></span> <span class tokenHandler>haracters(nsHtml5Tokenizer::,0, 1);
fail
<span class="GAPprompt">gap></span> <span class="GAPinput">SubdigraphHomeomorphicToK33(CompleteDigraph(5));</span>
fail
<span class="GAPprompt">gap></java.lang.StringIndexOutOfBoundsException: Range [0, 37) out of bounds for length 15
[ [ 4, 6, 5 ], [ 4, 5, 6 ], [ 6, 5, 4 ], [ 1, 2, 3 ], [ 3, 2, 1 ], 
  , ,1]]
<span class="GAPprompt">gap></span> <span class="GAPinput"> case : {
fail
<pan class=GAPprompt"gap&t;/>< class=GAPinput> =Digraph(sMutableDigraph [[,5 ], [,9,10] 1 ]</pan>
<span class="GAPprompt">></span> <span class="GAPinput">[3, 6            }
<mutable digraph with 11 vertices, 25 edges&               -' {
> <spanclass=GAPinput"SubdigraphHomeomorphicToK4);/>
[ [ 3, 5, 10 ], [ 9, 8, 10 ], [ 4, 1 ], [ 6
  [ 7, 4 ], [ 8, 6 ], [ 2, 7 ], [ 11, 2 ], [ 2, 1 ], [ 5, 9 ] ]
<span class##  option can take are in the (integer) range 0 to 4. 
##  option,  but the latter,  being 2 words,  is  not available via  the  GAP 
  [ 7, 4 ##  chance of still being functional if new options are added to the ACE bin-
<panclass=GAPprompt>ap>/> <spanclass=GAPinput">: DigraphIsMutableDigraph [,5 10,[,9 10,[                                      ;
              
&java.lang.StringIndexOutOfBoundsException: Index 11 out of bounds for length 11
<span class="GAPprompt  start =[, [f];
fail
"g&<>span ">D<
[[,,5, , ,  ,[,1][              sjava.lang.StringIndexOutOfBoundsException: Range [39, 38) out of bounds for length 40
   , ,6]  , , ,  ,  ,  ,     java.lang.StringIndexOutOfBoundsException: Index 63 out of bounds for length 63
<span                                       ) java.lang.StringIndexOutOfBoundsException: Range [57, 58) out of bounds for length 57
fail
<span class  mendelsohn: [,[,1]java.lang.StringIndexOutOfBoundsException: Index 27 out of bounds for length 27
fail
igraphHomeomorphicToK33()<
fail
<span class="recover := [4["] # "recover" and "contiguous"
 4 6  , ,5  ,[6 ,  ,[1,,  , ,, ,
  [java.lang.StringIndexOutOfBoundsException: Range [8, 7) out of bounds for length 21
span""g&;/><class>java.lang.StringIndexOutOfBoundsException: Range [89, 88) out of bounds for length 116
fail
</pre></div>

<p><##  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . binary options.

<h5>5 . . . . . . . .          java.lang.StringIndexOutOfBoundsException: Index 42 out of bounds for length 2

##
<>:or<classkeyw>/><p>

p v ""digraph/>isa  code""/>              

<p>purec:= ,  : ,= ,  java.lang.StringIndexOutOfBoundsException: Range [61, 60) out of bounds for length 66

p thatcodeclass""/>< =".#java.lang.StringIndexOutOfBoundsException: Index 462 out of bounds for length 462


<div####
sG>&< span=> =(;/
<span
ltimmutable    >
<span classjava.lang.StringIndexOutOfBoundsException: Index 0 out of bounds for length 0
true
<span class="java.lang.StringIndexOutOfBoundsException: Index 19 out of bounds for length 16
s class=>;/>< =>[,6 ] 2 ,]3 ,8,4 ,])/>
with8  &;
<span )
<span class="GAPprompt">gap> }
true
</pre></java.lang.StringIndexOutOfBoundsException: Index 10 out of bounds for length 0

<p><##  . . . . . . . . . . . . . . . . . .  KnownACEOptions, or false otherwise.

<h4##

<p><####

<h5>.- <h5>

<div ,
<p>#############################################################################

<p>This####

 hashingfunctionsystem   sotheof attribute   the java.lang.StringIndexOutOfBoundsException: Range [155, 154) out of bounds for length 159


div=chlinkprevnextbot"#


classchlink1Goto java.lang.StringIndexOutOfBoundsException: Range [66, 65) out of bounds for length 516

<hr />
p=foot> a"https/mathrwthaachen./java.lang.StringIndexOutOfBoundsException: Index 87 out of bounds for length 13

</html>

Messung
CHZG
849910094

¤ Dauer der Verarbeitung: 0.121 Sekunden  (vorverarbeitet am  2026-11-04) ¤

*© Formatika GbR, Deutschland






Wurzel

Suchen

PVS Prover

Isabelle Prover


Cephes Mathematical Library

Vienna Development Method

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.

Bemerkung:

Die farbliche Syntaxdarstellung und die Messung sind noch experimentell.