#############################################################################
##
#W attr.xml
#Y Copyright (C) 2014-19 James D. Mitchell
##
## Licensing information can be found in the README file of this package.
##
#############################################################################
##
<#GAPDoc Label="DigraphVertices">
<ManSection>
<Attr Name="DigraphVertices" Arg="digraph"/>
<Returns>A list of positive integers.</Returns>
<Description>
Returns the vertices of the digraph <A>digraph</A>. <P/>
Note that the vertices of a digraph are always the range of
positive integers from <C>1</C> to the number of vertices of the
graph, <Ref Attr="DigraphNrVertices"/>.
Arbitrary <E>labels</E> can be assigned to the vertices of a digraph;
see <Ref Oper="DigraphVertexLabels"/> for more information about this.
<#GAPDoc Label="DigraphNrVertices">
<ManSection>
<Attr Name="DigraphNrVertices" Arg="digraph"/>
<Returns>An non-negative integer.</Returns>
<Description>
Returns the number of vertices of the digraph <A>digraph</A>. <P/>
<#GAPDoc Label="DigraphEdges">
<ManSection>
<Attr Name="DigraphEdges" Arg="digraph"/>
<Returns>A list of lists of two positive integers.</Returns>
<Description>
Returns a list of edges of the digraph <A>digraph</A>,
where each edge is a pair of elements of <Ref Attr="DigraphVertices"/> of
the form <C>[source,range]</C>.
<P/>
<!-- TODO remove this paragraph when multidigraphs are removed -->
The entries of <C>DigraphEdges(</C><A>digraph</A><C>)</C> are in one-to-one
correspondence with the edges of <A>digraph</A>. Hence
<C>DigraphEdges(</C><A>digraph</A><C>)</C> is duplicate-free if and only if
<A>digraph</A> contains no multiple edges. <P/>
The entries of <C>DigraphEdges</C> 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.
<Example><![CDATA[
gap> gr := DigraphFromDiSparse6String(".DaXbOe?EAM@G~");
<immutable multidigraph with 5 vertices, 16 edges>
gap> edges := ShallowCopy(DigraphEdges(gr));; Sort(edges);
gap> edges;
[ [ 1, 1 ], [ 1, 3 ], [ 1, 3 ], [ 1, 4 ], [ 1, 5 ], [ 2, 1 ],
[ 2, 2 ], [ 2, 3 ], [ 2, 5 ], [ 3, 2 ], [ 3, 4 ], [ 3, 5 ],
[ 4, 2 ], [ 4, 4 ], [ 4, 5 ], [ 5, 1 ] ]
gap> D := CycleDigraph(IsMutableDigraph, 3);
<mutable digraph with 3 vertices, 3 edges>
gap> DigraphEdges(D);
[ [ 1, 2 ], [ 2, 3 ], [ 3, 1 ] ]
]]></Example>
</Description>
</ManSection>
<#/GAPDoc>
<#GAPDoc Label="DigraphNrEdges">
<ManSection>
<Attr Name="DigraphNrEdges" Arg="digraph"/>
<Returns>An integer.</Returns>
<Description>
Returns the number of edges of the digraph <A>digraph</A>.
<Example><![CDATA[
gap> gr := Digraph([
> [1, 3, 4, 5], [1, 2, 3, 5], [2, 4, 5], [2, 4, 5], [1]]);;
gap> DigraphNrEdges(gr);
15
gap> gr := Digraph(["a", "b", "c"],
> ["a", "b", "b"],
> ["b", "a", "a"]);
<immutable multidigraph with 3 vertices, 3 edges>
gap> DigraphNrEdges(gr);
3
gap> D := CycleDigraph(IsMutableDigraph, 3);
<mutable digraph with 3 vertices, 3 edges>
gap> DigraphNrEdges(D);
3
]]></Example>
</Description>
</ManSection>
<#/GAPDoc>
<#GAPDoc Label="DigraphNrAdjacencies">
<ManSection>
<Attr Name="DigraphNrAdjacencies" Arg="digraph" />
<Returns>An integer.</Returns>
<Description> Returns the number of sets <M>\{u, v\}</M> of vertices of the digraph <A>digraph</A>, such that
either <M>(u, v)</M> or <M>(v, u)</M> is an edge. The following equality holds for
any digraph <C>D</C> with no multiple edges: <C>DigraphNrAdjacencies(D) * 2 - DigraphNrLoops(D)
= DigraphNrEdges(DigraphSymmetricClosure(D))</C>.
<Example><![CDATA[
gap> gr := Digraph([
> [1, 3, 4, 5], [1, 2, 3, 5], [2, 4, 5], [2, 4, 5], [1]]);;
gap> DigraphNrAdjacencies(gr);
13
gap> DigraphNrAdjacencies(gr) * 2 - DigraphNrLoops(gr) =
> DigraphNrEdges(DigraphSymmetricClosure(gr));
true
]]></Example>
</Description>
</ManSection>
<#/GAPDoc>
<#GAPDoc Label="DigraphNrAdjacenciesWithoutLoops">
<ManSection>
<Attr Name="DigraphNrAdjacenciesWithoutLoops" Arg="digraph" />
<Returns>An integer.</Returns>
<Description> Returns the number of sets <M>\{u, v\}</M> of vertices of the digraph <A>digraph</A>, such that
<M>u \neq v</M> and either <M>(u, v)</M> or <M>(v, u)</M> is an edge. The following equality holds for
any digraph <C>D</C> with no multiple edges: <C>DigraphNrAdjacenciesWithoutLoops(D) * 2 + DigraphNrLoops(D)
= DigraphNrEdges(DigraphSymmetricClosure(D))</C>.
<Example><![CDATA[
gap> gr := Digraph([
> [1, 3, 4, 5], [1, 2, 3, 5], [2, 4, 5], [2, 4, 5], [1]]);;
gap> DigraphNrAdjacenciesWithoutLoops(gr);
10
gap> DigraphNrAdjacenciesWithoutLoops(gr) * 2 + DigraphNrLoops(gr) =
> DigraphNrEdges(DigraphSymmetricClosure(gr));
true
]]></Example>
</Description>
</ManSection>
<#/GAPDoc>
<#GAPDoc Label="DigraphNrLoops">
<ManSection>
<Attr Name="DigraphNrLoops" Arg="digraph"/>
<Returns>An integer.</Returns>
<Description>
This function returns the number of loops of the digraph <A>digraph</A>. See <Ref Prop="DigraphHasLoops"/>. <P/>
<Example><![CDATA[
gap> D := Digraph([[2, 3], [1, 4], [3, 3, 5], [], [2, 5]]);
<immutable multidigraph with 5 vertices, 9 edges>
gap> DigraphNrLoops(D);
3
gap> D := EmptyDigraph(5);
<immutable empty digraph with 5 vertices>
gap> DigraphNrLoops(D);
0
gap> D := CompleteDigraph(5);
<immutable complete digraph with 5 vertices>
gap> DigraphNrLoops(D);
0
]]></Example>
</Description>
</ManSection>
<#/GAPDoc>
<#GAPDoc Label="RangeSourceDigraph">
<ManSection>
<Attr Name="DigraphRange" Arg="digraph"/>
<Attr Name="DigraphSource" Arg="digraph"/>
<Returns>A list of positive integers.</Returns>
<Description>
<C>DigraphRange</C> and <C>DigraphSource</C> return the range and source of
the digraph <A>digraph</A>. More precisely, position <C>i</C> in
<C>DigraphSource(<A>digraph</A>)</C> and
<C>DigraphRange(<A>digraph</A>)</C> give, respectively, the source and
range of the <C>i</C>th edge of <A>digraph</A>.
<#GAPDoc Label="OutNeighbours">
<ManSection>
<Attr Name="OutNeighbours" Arg="digraph"/>
<Attr Name="OutNeighbors" Arg="digraph"/>
<Oper Name="OutNeighboursMutableCopy" Arg="digraph"/>
<Oper Name="OutNeighborsMutableCopy" Arg="digraph"/>
<Returns>The adjacencies of a digraph.</Returns>
<Description>
<C>OutNeighbours</C> returns the list <C>out</C> of out-neighbours of
each vertex of the digraph <A>digraph</A>. <!-- TODO update the following sentence once multidigraphs are gone -->
More specifically, a vertex <C>j</C> appears in <C>out[i]</C> each time
there exists the edge <C>[i, j]</C> in <A>digraph</A>. <P/>
The function <C>OutNeighbours</C> returns an immutable list of
lists, whereas the function <C>OutNeighboursMutableCopy</C> returns a copy
of <C>OutNeighbours</C> which is a mutable list of mutable lists. <P/>
Note that the entries of <C>out</C> are not guaranteed to be sorted in any
particular order.
<#GAPDoc Label="InNeighbours">
<ManSection>
<Attr Name="InNeighbours" Arg="digraph"/>
<Attr Name="InNeighbors" Arg="digraph"/>
<Oper Name="InNeighboursMutableCopy" Arg="digraph"/>
<Oper Name="InNeighborsMutableCopy" Arg="digraph"/>
<Returns>A list of lists of vertices.</Returns>
<Description>
<C>InNeighbours</C> returns the list <C>inn</C> of in-neighbours of each
vertex of the digraph <A>digraph</A>. <!-- TODO update the following sentence once multidigraphs are gone -->
More specifically, a vertex <C>j</C> appears in <C>inn[i]</C> each time
there exists an edge <C>[j,i]</C> in <A>digraph</A>. <P/>
The function <C>InNeighbours</C> returns an immutable list of
lists, whereas the function <C>InNeighboursMutableCopy</C> returns a copy
of <C>InNeighbours</C> which is a mutable list of mutable lists. <P/>
Note that the entries of <C>inn</C> are not necessarily sorted into
ascending order, particularly if <A>digraph</A> was constructed via
<Ref Oper="DigraphByInNeighbours"/>.
<#GAPDoc Label="DigraphAdjacencyFunction">
<ManSection>
<Attr Name="DigraphAdjacencyFunction" Arg="digraph"/>
<Returns>A function.</Returns>
<Description>
If <A>digraph</A> is a digraph, then <C>DigraphAdjacencyFunction</C> returns
a function which takes two integer parameters <C>x, y</C> and returns
<K>true</K> if there exists an edge from vertex <C>x</C> to vertex <C>y</C>
in <A>digraph</A> and <K>false</K> if not.
<Example><![CDATA[
gap> digraph := Digraph([[1, 2], [3], []]);
<immutable digraph with 3 vertices, 3 edges>
gap> foo := DigraphAdjacencyFunction(digraph);
function( u, v ) ... end
gap> foo(1, 1);
true
gap> foo(1, 2);
true
gap> foo(1, 3);
false
gap> foo(3, 1);
false
gap> gr := Digraph(["a", "b", "c"],
> ["a", "b", "b"],
> ["b", "a", "a"]);
<immutable multidigraph with 3 vertices, 3 edges>
gap> foo := DigraphAdjacencyFunction(gr);
function( u, v ) ... end
gap> foo(1, 2);
true
gap> foo(3, 2);
false
gap> foo(3, 1);
false
gap> D := CycleDigraph(IsMutableDigraph, 3);
<mutable digraph with 3 vertices, 3 edges>
gap> foo := DigraphAdjacencyFunction(D);
function( u, v ) ... end
gap> foo(1, 2);
true
gap> foo(2, 1);
false
]]></Example>
</Description>
</ManSection>
<#/GAPDoc>
<#GAPDoc Label="AdjacencyMatrix">
<ManSection>
<Attr Name="AdjacencyMatrix" Arg="digraph"/>
<Oper Name="AdjacencyMatrixMutableCopy" Arg="digraph"/>
<Returns>A square matrix of non-negative integers.</Returns>
<Description>
This function returns the adjacency matrix <C>mat</C> of the digraph
<A>digraph</A>. <!-- Update the following sentence when multidigraphs are gone -->
The value of the matrix entry <C>mat[i][j]</C> is the number of edges
in <A>digraph</A> with source <C>i</C> and range <C>j</C>. If <A>digraph</A>
has no vertices, then the empty list is returned. <P/>
The function <C>AdjacencyMatrix</C> returns an immutable list of
lists, whereas the function <C>AdjacencyMatrixMutableCopy</C> returns a copy
of <C>AdjacencyMatrix</C> that is a mutable list of mutable lists. <P/>
<#GAPDoc Label="BooleanAdjacencyMatrix">
<ManSection>
<Attr Name="BooleanAdjacencyMatrix" Arg="digraph"/>
<Oper Name="BooleanAdjacencyMatrixMutableCopy" Arg="digraph"/>
<Returns>A square matrix of booleans.</Returns>
<Description>
If <A>digraph</A> is a digraph with a positive number of vertices
<C>n</C>, then <C>BooleanAdjacencyMatrix(</C><A>digraph</A><C>)</C>
returns the boolean adjacency matrix <C>mat</C> of <A>digraph</A>. <!-- TODO Update the following sentence when multidigraphs are gone -->
The
value of the matrix entry <C>mat[j][i]</C> is <K>true</K> if and only if
there exists an edge in <A>digraph</A> with source <C>j</C> and range
<C>i</C>. If <A>digraph</A> has no vertices, then the empty list is
returned. <P/>
<!-- TODO Remove this sentence when multidigraphs are gone -->
Note that the boolean adjacency matrix loses information about multiple
edges. <P/>
The attribute <C>BooleanAdjacencyMatrix</C> returns an immutable list of
immutable lists, whereas the function
<C>BooleanAdjacencyMatrixMutableCopy</C> returns a copy of the
<C>BooleanAdjacencyMatrix</C> that is a mutable list of mutable lists. <P/>
<Example><![CDATA[
gap> gr := Digraph([[3, 4], [2, 3], [1, 2, 4], [4]]);
<immutable digraph with 4 vertices, 8 edges>
gap> PrintArray(BooleanAdjacencyMatrix(gr));
[ [ false, false, true, true ],
[ false, true, true, false ],
[ true, true, false, true ],
[ false, false, false, true ] ]
gap> gr := CycleDigraph(4);;
gap> PrintArray(BooleanAdjacencyMatrix(gr));
[ [ false, true, false, false ],
[ false, false, true, false ],
[ false, false, false, true ],
[ true, false, false, false ] ]
gap> BooleanAdjacencyMatrix(EmptyDigraph(0));
[ ]
gap> D := CycleDigraph(IsMutableDigraph, 3);
<mutable digraph with 3 vertices, 3 edges>
gap> PrintArray(BooleanAdjacencyMatrix(D));
[ [ false, true, false ],
[ false, false, true ],
[ true, false, false ] ]
]]></Example>
</Description>
</ManSection>
<#/GAPDoc>
<#GAPDoc Label="DegreeMatrix">
<ManSection>
<Attr Name="DegreeMatrix" Arg="digraph"/>
<Returns>A square matrix of non-negative integers.</Returns>
<Description>
Returns the out-degree matrix <C>mat</C> of the digraph
<A>digraph</A>. The value of the <C>i</C>th diagonal matrix entry is the
out-degree of the vertex <C>i</C> in <A>digraph</A>. All off-diagonal
entries are <C>0</C>.
If <A>digraph</A> has no vertices, then the empty list is returned. <P/>
<#GAPDoc Label="LaplacianMatrix">
<ManSection>
<Attr Name="LaplacianMatrix" Arg="digraph"/>
<Returns>A square matrix of integers.</Returns>
<Description>
Returns the out-degree Laplacian matrix <C>mat</C> of the
digraph <A>digraph</A>. The out-degree Laplacian matrix is defined as
<C>DegreeMatrix(digraph) - AdjacencyMatrix(digraph)</C>. If
<A>digraph</A> has no vertices, then the empty list is returned. <P/>
<#GAPDoc Label="OutDegrees">
<ManSection>
<Attr Name="OutDegrees" Arg="digraph"/>
<Attr Name="OutDegreeSequence" Arg="digraph"/>
<Attr Name="OutDegreeSet" Arg="digraph"/>
<Returns>A list of non-negative integers.</Returns>
<Description>
Given a digraph <A>digraph</A> with <M>n</M> vertices, the function
<C>OutDegrees</C> returns an immutable list <C>out</C> of length <M>n</M>, such that
for a vertex <C>i</C> in <A>digraph</A>, the value of <C>out[i]</C> is the
out-degree of vertex <C>i</C>.
See <Ref Oper="OutDegreeOfVertex"/>. <P/>
The function <C>OutDegreeSequence</C> returns the same list,
after it has been sorted into non-increasing order. <P/>
The function <C>OutDegreeSet</C> returns the same list, sorted into
increasing order with duplicate entries removed. <P/>
<#GAPDoc Label="InDegrees">
<ManSection>
<Attr Name="InDegrees" Arg="digraph"/>
<Attr Name="InDegreeSequence" Arg="digraph"/>
<Attr Name="InDegreeSet" Arg="digraph"/>
<Returns>A list of non-negative integers.</Returns>
<Description>
Given a digraph <A>digraph</A> with <M>n</M> vertices, the function
<C>InDegrees</C> returns an immutable list <C>inn</C> of length <M>n</M>, such that
for a vertex <C>i</C> in <A>digraph</A>, the value of <C>inn[i]</C> is
the in-degree of vertex <C>i</C>.
See <Ref Oper="InDegreeOfVertex"/>. <P/>
The function <C>InDegreeSequence</C> returns the same list,
after it has been sorted into non-increasing order. <P/>
The function <C>InDegreeSet</C> returns the same list, sorted into
increasing order with duplicate entries removed. <P/>
<#GAPDoc Label="DigraphSources">
<ManSection>
<Attr Name="DigraphSources" Arg="digraph"/>
<Returns>A list of vertices.</Returns>
<Description>
This function returns an immutable list of the sources of the digraph
<A>digraph</A>.
A source of a digraph is a vertex with in-degree zero.
See <Ref Oper="InDegreeOfVertex"/>.
<Example><![CDATA[
gap> gr := Digraph([[3, 5, 2, 2], [3], [], [5, 2, 5, 3], []]);
<immutable multidigraph with 5 vertices, 9 edges>
gap> DigraphSources(gr);
[ 1, 4 ]
gap> D := CycleDigraph(IsMutableDigraph, 3);
<mutable digraph with 3 vertices, 3 edges>
gap> DigraphSources(D);
[ ]
]]></Example>
</Description>
</ManSection>
<#/GAPDoc>
<#GAPDoc Label="DigraphSinks">
<ManSection>
<Attr Name="DigraphSinks" Arg="digraph"/>
<Returns>A list of vertices.</Returns>
<Description>
This function returns a list of the sinks of the digraph
<A>digraph</A>.
A sink of a digraph is a vertex with out-degree zero.
See <Ref Oper="OutDegreeOfVertex"/>.
<Example><![CDATA[
gap> gr := Digraph([[3, 5, 2, 2], [3], [], [5, 2, 5, 3], []]);
<immutable multidigraph with 5 vertices, 9 edges>
gap> DigraphSinks(gr);
[ 3, 5 ]
gap> D := CycleDigraph(IsMutableDigraph, 3);
<mutable digraph with 3 vertices, 3 edges>
gap> DigraphSinks(D);
[ ]
]]></Example>
</Description>
</ManSection>
<#/GAPDoc>
<#GAPDoc Label="DigraphStronglyConnectedComponents">
<ManSection>
<Attr Name="DigraphStronglyConnectedComponents" Arg="digraph"/>
<Attr Name="DigraphNrStronglyConnectedComponents" Arg="digraph"/>
<Returns>A record.</Returns>
<Description>
This function returns the record <C>scc</C> corresponding to the strongly
connected components of the digraph <A>digraph</A>. Two vertices of
<A>digraph</A> 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
<A>digraph</A>.
<P/>
The record <C>scc</C> has 2 components: <C>comps</C> and <C>id</C>.
The component <C>comps</C> is a list of the strongly connected components
of <A>digraph</A> (each of which is a list of vertices).
The component <C>id</C> is a list such that the vertex <C>i</C> is an element of the strongly connected component <C>comps[id[i]]</C>. <P/>
The method used in this function is a non-recursive version of Gabow's
Algorithm <Cite Key="Gab00"/> and has complexity <M>O(m+n)</M> where
<M>m</M> is the number of edges (counting multiple edges as one) and
<M>n</M> is the number of vertices in the digraph. <P/>
<C>DigraphNrStronglyConnectedComponents(<A>digraph</A>)</C> is simply a
shortcut for
<C>Length(DigraphStronglyConnectedComponents(<A>digraph</A>).comps)</C>,
and is no more efficient.
<#GAPDoc Label="DigraphConnectedComponents">
<ManSection>
<Attr Name="DigraphConnectedComponents" Arg="digraph"/>
<Attr Name="DigraphNrConnectedComponents" Arg="digraph"/>
<Returns>A record.</Returns>
<Description>
This function returns the record <C>wcc</C> corresponding to the weakly
connected components of the digraph <A>digraph</A>. Two vertices of
<A>digraph</A> 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 <A>digraph</A> if and only if they are in the same strongly
connected component (see <Ref Attr="DigraphStronglyConnectedComponents"/>)
of the <Ref Oper="DigraphSymmetricClosure"/> of <A>digraph</A>. <P/>
The set of weakly connected components is a partition of
the vertex set of <A>digraph</A>. <P/>
The record <C>wcc</C> has 2 components: <C>comps</C> and <C>id</C>.
The component <C>comps</C> is a list of the weakly connected components
of <A>digraph</A> (each of which is a list of vertices).
The component <C>id</C> is a list such that the vertex <C>i</C> is an element of the weakly connected component <C>comps[id[i]]</C>. <P/>
The method used in this function has complexity <M>O(m+n)</M>, where
<M>m</M> is the number of edges and
<M>n</M> is the number of vertices in the digraph. <P/>
<C>DigraphNrConnectedComponents(<A>digraph</A>)</C> is simply a shortcut
for <C>Length(DigraphConnectedComponents(<A>digraph</A>).comps)</C>,
and is no more efficient.
<#GAPDoc Label="DigraphTopologicalSort">
<ManSection>
<Attr Name="DigraphTopologicalSort" Arg="digraph"/>
<Returns>A list of positive integers, or <K>fail</K>.</Returns>
<Description>
If <A>digraph</A> is a digraph whose only directed cycles are loops, then
<C>DigraphTopologicalSort</C> returns the vertices of <A>digraph</A> ordered
so that every edge's source appears no earlier in the list than its range.
If the digraph <A>digraph</A> contains directed cycles of length greater
than <M>1</M>, then this operation returns <K>fail</K>.
<P/>
See Section <Ref Subsect="Definitions" Style="Number" /> for the definition
of a directed cycle, and the definition of a loop.
<P/>
The method used for this attribute has complexity <M>O(m+n)</M> where
<M>m</M> is the number of edges (counting multiple edges as one) and
<M>n</M> is the number of vertices in the digraph. <P/>
<Example><![CDATA[
gap> D := Digraph([
> [2, 3], [], [4, 6], [5], [], [7, 8, 9], [], [], []]);
<immutable digraph with 9 vertices, 8 edges>
gap> DigraphTopologicalSort(D);
[ 2, 5, 4, 7, 8, 9, 6, 3, 1 ]
gap> D := Digraph(IsMutableDigraph, [[2, 3], [3], [4], []]);
<mutable digraph with 4 vertices, 4 edges>
gap> DigraphTopologicalSort(D);
[ 4, 3, 2, 1 ]
]]></Example>
</Description>
</ManSection>
<#/GAPDoc>
<#GAPDoc Label="DigraphDegeneracy">
<ManSection>
<Attr Name="DigraphDegeneracy" Arg="digraph"/>
<Returns>A non-negative integer, or <K>fail</K>.</Returns>
<Description>
If <A>digraph</A> is a symmetric digraph without multiple edges - see
<Ref Prop="IsSymmetricDigraph"/> and <Ref Prop="IsMultiDigraph"/> - then
this attribute returns the degeneracy of <A>digraph</A>. <P/>
The degeneracy of a digraph is the least integer <C>k</C> such
that every induced of <A>digraph</A> contains a vertex whose number of
neighbours (excluding itself) is at most <C>k</C>. Note that this means
that loops are ignored.<P/>
If <A>digraph</A> is not symmetric or has multiple edges then this
attribute returns <K>fail</K>.
<Example><![CDATA[
gap> D := DigraphSymmetricClosure(ChainDigraph(5));;
gap> DigraphDegeneracy(D);
1
gap> D := CompleteDigraph(5);;
gap> DigraphDegeneracy(D);
4
gap> D := Digraph([[1], [2, 4, 5], [3, 4], [2, 3, 4], [2], []]);
<immutable digraph with 6 vertices, 10 edges>
gap> DigraphDegeneracy(D);
1
gap> D := GeneralisedPetersenGraph(IsMutableDigraph, 10, 3);
<mutable digraph with 20 vertices, 60 edges>
gap> DigraphDegeneracy(D);
3
]]></Example>
</Description>
</ManSection>
<#/GAPDoc>
<#GAPDoc Label="DigraphDegeneracyOrdering">
<ManSection>
<Attr Name="DigraphDegeneracyOrdering" Arg="digraph"/>
<Returns>A list of integers, or <K>fail</K>.</Returns>
<Description>
If <A>digraph</A> is a digraph for which
<C>DigraphDegeneracy(</C><A>digraph</A><C>)</C> is a non-negative integer
<C>k</C> - see <Ref Attr="DigraphDegeneracy"/> - then this attribute
returns a degeneracy ordering of the vertices of the vertices of
<A>digraph</A>.<P/>
A degeneracy ordering of <A>digraph</A> is a list <C>ordering</C> of the
vertices of <A>digraph</A> ordered such that for any
position <C>i</C> of the list, the vertex <C>ordering[i]</C> has at most
<C>k</C> neighbours in later position of the list.<P/>
<#GAPDoc Label="DigraphShortestDistances">
<ManSection>
<Attr Name="DigraphShortestDistances" Arg="digraph"/>
<Returns>A square matrix.</Returns>
<Description>
If <A>digraph</A> is a digraph with <M>n</M> vertices, then this
function returns an <M>n \times n</M> matrix <C>mat</C>, where each entry is
either a non-negative integer, or <K>fail</K>. If <M>n = 0</M>, then an
empty list is returned. <P/>
If there is a directed path from vertex <C>i</C> to vertex <C>j</C>, then
the value of <C>mat[i][j]</C> is the length of the shortest such directed
path. If no such directed path exists, then the value of <C>mat[i][j]</C> is
<C>fail</C>. We use the convention that the distance from every vertex to
itself is <C>0</C>, i.e. <C>mat[i][i] = 0</C> for all vertices <C>i</C>.
<P/>
The method used in this function is a version of the Floyd-Warshall
algorithm, and has complexity <M>O(n^3)</M>.
<#GAPDoc Label="DigraphDiameter">
<ManSection>
<Attr Name="DigraphDiameter" Arg="digraph"/>
<Returns>An integer or <C>fail</C>.</Returns>
<Description>
This function returns the diameter of the digraph <A>digraph</A>.
<P/>
If a digraph <A>digraph</A> is strongly connected and has at least 1
vertex, then the <E>diameter</E> is the maximum shortest distance between
any pair of distinct vertices. Otherwise then the diameter of
<A>digraph</A> is undefined, and this function returns the value
<C>fail</C>. <P/>
See <Ref Attr="DigraphShortestDistances"/>. <P/>
<Example><![CDATA[
gap> D := Digraph([[2], [3], [4, 5], [5], [1, 2, 3, 4, 5]]);
<immutable digraph with 5 vertices, 10 edges>
gap> DigraphDiameter(D);
3
gap> D := ChainDigraph(2);
<immutable chain digraph with 2 vertices>
gap> DigraphDiameter(D);
fail
gap> IsStronglyConnectedDigraph(D);
false
gap> D := GeneralisedPetersenGraph(IsMutableDigraph, 6, 2);
<mutable digraph with 12 vertices, 36 edges>
gap> DigraphDiameter(D);
4
]]></Example>
</Description>
</ManSection>
<#/GAPDoc>
<#GAPDoc Label="DigraphGirth">
<ManSection>
<Attr Name="DigraphGirth" Arg="digraph"/>
<Returns>An integer, or <K>infinity</K>.</Returns>
<Description>
This attribute returns the <E>girth</E> of the digraph <A>digraph</A>.
The <E>girth</E> of a digraph is the length of its shortest simple circuit.
See Section <Ref Subsect="Definitions" Style="Number" /> for the definitions
of simple circuit, directed cycle, and loop.
<P/>
If <A>digraph</A> has no directed cycles, then this function will return
<K>infinity</K>. If <A>digraph</A> contains a loop, then this function will
return <C>1</C>.
<P/>
In the worst case, the method used in this function is a version of the
Floyd-Warshall algorithm, and has complexity <C>O(<A>n</A> ^ 3)</C>, where
<A>n</A> is the number of vertices in <A>digraph</A>. If the digraph has
known automorphisms [see <Ref Attr="DigraphGroup"/>], then the performance
is likely to be better.
<P/>
For symmetric digraphs, see also <Ref Attr="DigraphUndirectedGirth"/>. <P/>
<Example><![CDATA[
gap> D := Digraph([[1], [1]]);
<immutable digraph with 2 vertices, 2 edges>
gap> DigraphGirth(D);
1
gap> D := Digraph([[2, 3], [3], [4], []]);
<immutable digraph with 4 vertices, 4 edges>
gap> DigraphGirth(D);
infinity
gap> D := Digraph([[2, 3], [3], [4], [1]]);
<immutable digraph with 4 vertices, 5 edges>
gap> DigraphGirth(D);
3
gap> D := GeneralisedPetersenGraph(IsMutableDigraph, 6, 2);
<mutable digraph with 12 vertices, 36 edges>
gap> DigraphGirth(D);
2
]]></Example>
</Description>
</ManSection>
<#/GAPDoc>
<#GAPDoc Label="DigraphOddGirth">
<ManSection>
<Attr Name="DigraphOddGirth" Arg="digraph"/>
<Returns>An integer, or <K>infinity</K>.</Returns>
<Description>
This attribute returns the <E>odd girth</E> of the digraph <A>digraph</A>.
The <E>odd girth</E> of a digraph is the length of its shortest simple
circuit of odd length. See Section <Ref Subsect="Definitions"
Style="Number" /> for the definitions of simple circuit, directed
cycle, and loop.
<P/>
If <A>digraph</A> has no directed cycles of odd length, then this function
will return <K>infinity</K>, even if <A>digraph</A> has a directed cycle
of even length. If <A>digraph</A> contains a loop, then this function
will return <C>1</C>.
<P/>
See also <Ref Attr="DigraphGirth"/>. <P/>
<Example><![CDATA[
gap> D := Digraph([[2], [3, 1], [1]]);
<immutable digraph with 3 vertices, 4 edges>
gap> DigraphOddGirth(D);
3
gap> D := CycleDigraph(4);
<immutable cycle digraph with 4 vertices>
gap> DigraphOddGirth(D);
infinity
gap> D := Digraph([[2], [3], [], [3], [4]]);
<immutable digraph with 5 vertices, 4 edges>
gap> DigraphOddGirth(D);
infinity
gap> D := CycleDigraph(IsMutableDigraph, 4);
<mutable digraph with 4 vertices, 4 edges>
gap> DigraphDisjointUnion(D, CycleDigraph(5));
<mutable digraph with 9 vertices, 9 edges>
gap> DigraphOddGirth(D);
5
]]></Example>
</Description>
</ManSection>
<#/GAPDoc>
<#GAPDoc Label="DigraphUndirectedGirth">
<ManSection>
<Attr Name="DigraphUndirectedGirth" Arg="digraph"/>
<Returns>An integer or <K>infinity</K>.</Returns>
<Description>
If <A>digraph</A> is a symmetric digraph, then this function returns the
girth of <A>digraph</A> when treated as an undirected graph (i.e. each pair
of edges <M>[i, j]</M> and <M>[j, i]</M> is treated as a single edge between
<M>i</M> and <M>j</M>). <P/>
The <E>girth</E> 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/>
If <A>digraph</A> has no cycles, then this function will return
<K>infinity</K>. <P/>
<Example><![CDATA[
gap> D := Digraph([[2, 4], [1, 3], [2, 4], [1, 3]]);
<immutable digraph with 4 vertices, 8 edges>
gap> DigraphUndirectedGirth(D);
4
gap> D := Digraph([[2], [1, 3], [2]]);
<immutable digraph with 3 vertices, 4 edges>
gap> DigraphUndirectedGirth(D);
infinity
gap> D := Digraph([[1], [], [4], [3]]);
<immutable digraph with 4 vertices, 3 edges>
gap> DigraphUndirectedGirth(D);
1
gap> D := GeneralisedPetersenGraph(IsMutableDigraph, 9, 2);
<mutable digraph with 18 vertices, 54 edges>
gap> DigraphUndirectedGirth(D);
5
]]></Example>
</Description>
</ManSection>
<#/GAPDoc>
<#GAPDoc Label="ArticulationPoints">
<ManSection>
<Attr Name="ArticulationPoints" Arg="digraph"/>
<Returns>A list of vertices.</Returns>
<Description>
A connected digraph is <E>biconnected</E> if it is still connected (in the
sense of <Ref Prop="IsConnectedDigraph"/>) when any vertex is removed.
If the digraph <A>digraph</A> is not biconnected but is connected, then any
vertex <C>v</C> of <A>digraph</A> whose removal makes the resulting digraph
disconnected is called an <E>articulation point</E>.<P/>
<C>ArticulationPoints</C> returns a list of the articulation points of
<A>digraph</A>, if any, and, in particular, returns the empty list if
<A>digraph</A> is not connected. <P/>
Multiple edges are ignored by this method. <P/>
The method used in this operation has complexity <M>O(m+n)</M> where
<M>m</M> is the number of edges and <M>n</M> is the number of vertices in
the digraph.<P/>
If <A>D</A> has a bridge (see <Ref Attr="Bridges"/>), then a node incident
to the bridge is an articulation point if and only if it has degree at
least <M>2</M>. It follows that if <A>D</A> has a bridge and at least
<M>3</M> 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/>
<#GAPDoc Label="MinimalCyclicEdgeCut">
<ManSection>
<Attr Name="MinimalCyclicEdgeCut" Arg="digraph"/>
<Returns>A list of edges or <K>fail</K>.</Returns>
<Description>
A cyclic edge cut of <A>digraph</A> 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/>
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 <K>fail</K>.
Multiple edges of <A>digraph</A> are ignored by this method and note
that <A>digraph</A> is identified as an undirected graph. <P/>
The method used in this method has complexity <M>O(n^2*log^2(n)) </M> where
<M>n</M> is the number of vertices in the digraph.<P/>
<#GAPDoc Label="DigraphAbsorptionProbabilities">
<ManSection>
<Attr Name="DigraphAbsorptionProbabilities" Arg="digraph"/>
<Returns>A matrix of rational numbers.</Returns>
<Description>
A random walk of infinite length through a finite digraph may pass through several
different strongly connected components (SCCs). However, with probability 1
it must eventually reach an SCC which it can never leave, because the SCC
has no out-edges leading to other SCCs. We may say that such an SCC has
<E>absorbed</E> the random walk, and we can calculate the probability of
each SCC absorbing a walk starting at a given vertex.
<P/>
<C>DigraphAbsorptionProbabilities</C> returns an <M>m \times n</M> matrix
<C>mat</C>, where <M>m</M> is the number of vertices in <C>digraph</C> and
<M>n</M> is the number of strongly connected components. Each entry
<C>mat[i][j]</C> is a rational number representing the probability that an
unbounded random walk starting at vertex <C>i</C> will be absorbed by
strongly connected component <C>j</C> – that is, the probability that it
will reach the component and never leave.
<P/>
Strongly connected components are indexed in the order given by
<Ref Attr="DigraphStronglyConnectedComponents"/>. See also
<Ref Oper="DigraphRandomWalk"/> and
<Ref Attr="DigraphAbsorptionExpectedSteps"/>.
<P/>
<Example><![CDATA[
gap> gr := Digraph([[2, 3, 4], [3], [2], []]);
<immutable digraph with 4 vertices, 5 edges>
gap> DigraphStronglyConnectedComponents(gr).comps;
[ [ 2, 3 ], [ 4 ], [ 1 ] ]
gap> DigraphAbsorptionProbabilities(gr);
[ [ 2/3, 1/3, 0 ], [ 1, 0, 0 ], [ 1, 0, 0 ], [ 0, 1, 0 ] ]
]]></Example>
</Description>
</ManSection>
<#/GAPDoc>
<#GAPDoc Label="DigraphAbsorptionExpectedSteps">
<ManSection>
<Attr Name="DigraphAbsorptionExpectedSteps" Arg="digraph"/>
<Returns>A list of rational numbers.</Returns>
<Description>
A random walk of unbounded length through a finite digraph may pass through
several different strongly connected components (SCCs). However, with
probability 1 it must eventually reach an SCC which it can never leave,
because the SCC has no out-edges leading to other SCCs. When this happens,
we say the walk has been <E>absorbed</E>.
<P/>
<C>DigraphAbsorptionExpectedSteps</C> returns a list <C>L</C> with length
equal to the number of vertices of <A>digraph</A>, where <C>L[v]</C>
is the expected number of steps a random walk starting at vertex <C>v</C>
should take before it is absorbed – that is, the expected number of steps to
reach an SCC that it can never leave.
<P/>
See also <Ref Oper="DigraphRandomWalk"/> and
<Ref Attr="DigraphAbsorptionProbabilities"/>.
<P/>
<Example><![CDATA[
gap> gr := Digraph([[2], [3, 4], [], [2]]);
<immutable digraph with 4 vertices, 4 edges>
gap> DigraphAbsorptionExpectedSteps(gr);
[ 4, 3, 0, 4 ]
]]></Example>
</Description>
</ManSection>
<#/GAPDoc>
<#GAPDoc Label="StrongOrientation">
<ManSection>
<Oper Name="StrongOrientation" Arg="D"/>
<Attr Name="StrongOrientationAttr" Arg="D"/>
<Returns>A digraph or <K>fail</K>.</Returns>
<Description>
A <E>strong orientation</E> of a connected symmetric digraph <A>D</A> (if
it exists) is a strongly connected subdigraph <C>C</C> of <A>D</A> such
that for every edge <C>[u, v]</C> of <A>D</A> either <C>[u, v]</C> or
<C>[v, u]</C> is an edge of <C>C</C> but not both. Robbin's Theorem states
that a digraph admits a strong orientation if and only if it is
bridgeless (see <Ref Prop="IsBridgelessDigraph"/>).
<P/>
This operation returns a strong orientation of the digraph <A>D</A> if
<A>D</A> is symmetric and <A>D</A> admits a strong orientation. If <A>D</A>
is symmetric but does not admit a strong orientation, then <K>fail</K> is
returned. If <A>D</A> is not symmetric, then an error is given.
<P/>
If <A>D</A> is immutable, <C>StrongOrientation(<A>D</A>)</C> returns an
immutable digraph, and if <A>D</A> is mutable, then
<C>StrongOrientation(<A>D</A>)</C> returns a mutable digraph. <P/>
The method used in this operation has complexity <M>O(m+n)</M> where
<M>m</M> is the number of edges and <M>n</M> is the number of vertices in
the digraph.
<Example><![CDATA[
gap> StrongOrientation(DigraphSymmetricClosure(CycleDigraph(5)))
> = CycleDigraph(5);
true
gap> D := DigraphSymmetricClosure(Digraph(
> [[2, 7], [3, 5], [4], [2], [6], [1], []]));;
gap> IsBridgelessDigraph(D);
false
gap> StrongOrientation(D);
fail
gap> StrongOrientation(NullDigraph(0));
<immutable empty digraph with 0 vertices>
gap> StrongOrientation(DigraphDisjointUnion(CompleteDigraph(3),
> CompleteDigraph(3)));
fail
]]></Example>
</Description>
</ManSection>
<#/GAPDoc>
<#GAPDoc Label="Bridges">
<ManSection>
<Attr Name="Bridges" Arg="D"/>
<Returns>A (possibly empty) list of edges.</Returns>
<Description>
A connected digraph is <E>2-edge-connected</E> if it is still connected (in
the sense of <Ref Prop="IsConnectedDigraph"/>) when any edge is
removed. If the digraph <A>D</A> is not 2-edge-connected but is
connected, then any edge <C>[u, v]</C> of <A>D</A> whose removal
makes the resulting digraph disconnected is called a <E>bridge</E>.<P/>
<C>Bridges</C> returns a list of the bridges of <A>D</A>, if any, and, in
particular, returns the empty list if <A>D</A> is not connected. <P/>
Multiple edges are ignored by this method. <P/>
The method used in this operation has complexity <M>O(m+n)</M> where
<M>m</M> is the number of edges and <M>n</M> is the number of vertices in
the digraph.
<P/>
If <A>D</A> has a bridge, then a node incident to the bridge is an
articulation point (see <Ref Attr="ArticulationPoints"/>) if and only if
it has degree at least <M>2</M>. It follows that if <A>D</A> has a
bridge and at least <M>3</M> 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/>
<#GAPDoc Label="DigraphAllSimpleCircuits">
<ManSection>
<Attr Name="DigraphAllSimpleCircuits" Arg="digraph"/>
<Returns>A list of lists of vertices.</Returns>
<Description>
If <A>digraph</A> is a digraph, then <C>DigraphAllSimpleCircuits</C>
returns a list of the <E>simple circuits</E> in <A>digraph</A>. <P/>
See Section <Ref Subsect="Definitions" Style="Number" /> for the definition
of a simple circuit, and related notions. Note that a loop is a simple
circuit. <P/>
For a digraph without multiple edges, a simple circuit is uniquely
determined by its subsequence of vertices. However this is not the case for
a multidigraph. The attribute <C>DigraphAllSimpleCircuits</C> ignores
multiple edges, and identifies a simple circuit using only its subsequence
of vertices. For example, although the simple circuits <M>(v, e, v)</M> and
<M>(v, e', v) (for distinct edges e and e'</M>) are
mathematically distinct, <C>DigraphAllSimpleCircuits</C> considers them to
be the same. <P/>
With this approach, a directed circuit of length <C>n</C> can be determined
by a list of its first <C>n</C> vertices. Thus a simple circuit <M>(v_1,
e_1, v_2, e_2, ..., e_{n-1}, v_n, e_{n+1}, v_1)</M> can be represented as
the list <M>[v_1, \ldots, v_n]</M>, or any cyclic permutation thereof. For
each simple circuit of <A>digraph</A>,
<C>DigraphAllSimpleCircuits(<A>digraph</A>)</C> includes precisely one such
list to represent the circuit. <P/>
<#GAPDoc Label="DigraphLongestSimpleCircuit">
<ManSection>
<Attr Name="DigraphLongestSimpleCircuit" Arg="digraph"/>
<Returns>A list of vertices, or <K>fail</K>.</Returns>
<Description>
If <A>digraph</A> is a digraph, then <C>DigraphLongestSimpleCircuit</C>
returns the longest <E>simple circuit</E> in <A>digraph</A>. See Section
<Ref Subsect="Definitions" Style="Number" /> for the definition of simple
circuit, and the definition of length for a simple circuit.<P/>
This attribute computes
<C>DigraphAllSimpleCircuits(</C><A>digraph</A><C>)</C> to find all the
simple circuits of <A>digraph</A>, and returns one of maximal length. A
simple circuit is represented as a list of vertices, in the same way as
described in <Ref Attr="DigraphAllSimpleCircuits"/>.<P/>
If <A>digraph</A> has no simple circuits, then this attribute returns
<K>fail</K>. If <A>digraph</A> has multiple simple circuits of maximal
length, then this attribute returns one of them.<P/>
<#GAPDoc Label="DigraphAllUndirectedSimpleCircuits">
<ManSection>
<Attr Name="DigraphAllUndirectedSimpleCircuits" Arg="digraph"/>
<Returns>A list of lists of vertices.</Returns>
<Description>
If <A>digraph</A> is a digraph, then <C>DigraphAllUndirectedSimpleCircuits</C>
returns a list of the <E> undirected simple circuits</E> in <A>digraph</A>. <P/>
See Section <Ref Subsect="Definitions" Style="Number" /> for the definition
of a simple circuit, and related notions. Note that a loop is a simple
circuit. A simple circuit is undirected if the orientation of the edges
in the circuit does not matter.<P/>
The attribute <C>DigraphAllUndirectedSimpleCircuitss</C> ignores
multiple edges, and identifies a undirected simple circuit using only its subsequence
of vertices.
See Section <Ref Subsect="DigraphAllSimpleCircuits" Style="Number" /> for more details
on simple circuits.<P/>
<#GAPDoc Label="DigraphAllChordlessCycles">
<ManSection>
<Attr Name="DigraphAllChordlessCycles" Arg="digraph"/>
<Attr Name="DigraphAllChordlessCyclesOfMaximalLength" Arg="digraph, maxLength"/>
<Returns>A list of lists of vertices.</Returns>
<Description>
If <A>digraph</A> is a digraph, then <C>DigraphAllChordlessCycles</C>
returns a list of the <E>chordless cycles</E> in <A>digraph</A>.
The method <C>DigraphAllChordlessCyclesOfMaximalLength</C> returns
a list of all <E>chordless cycles</E> in <A>digraph</A> of length at
most <A>maxLength</A><P/>
A chordless cycle <M>C</M> is a undirected simple circuit (see Section <Ref Subsect="Definitions"Style="Number" /> )
where each pair of vertices in <M>C</M> are not connected by an edge not in <M>C</M>.
Here, cycles of length two are ignored.<P/>
For a digraph without multiple edges, a simple circuit is uniquely
determined by its subsequence of vertices. However this is not the case for
a multidigraph. The attribute <C>DigraphAllChordlessCycles</C> ignores
multiple edges, and identifies a simple circuit using only its subsequence
of vertices. See Section <Ref Subsect="DigraphAllSimpleCircuits" Style="Number" /> for more details.<P/>
This method uses the algorithms described in <Cite Key="US14"/>.<P/>
<Example><![CDATA[
gap> D := ChainDigraph(10);;
gap> DigraphAllChordlessCycles(D);
[ ]
gap> D := Digraph([[1, 1]]);
<immutable multidigraph with 1 vertex, 2 edges>
gap> DigraphAllChordlessCycles(D);
[ ]
gap> D := CycleDigraph(3);;
gap> DigraphAllChordlessCycles(D);
[ [ 2, 1, 3 ] ]
gap> D := CompleteDigraph(4);
<immutable complete digraph with 4 vertices>
gap> DigraphAllChordlessCycles(D);
[ [ 2, 1, 3 ], [ 2, 1, 4 ], [ 3, 1, 4 ], [ 3, 2, 4 ] ]
]]></Example>
</Description>
</ManSection>
<#/GAPDoc>
<#GAPDoc Label="FacialWalks">
<ManSection>
<Oper Name="FacialWalks" Arg="digraph, list"/>
<Returns>A list of lists of vertices.</Returns>
<Description>
If <A>digraph</A> is an Eulerian digraph and <A>list</A> is a rotation system of <A>digraph</A>,
then <C>FacialWalks</C> returns a list of the <E>facial walks</E> in <A>digraph</A>. <P/>
A rotation system defines for each vertex the ordering of the out-neighbours.
For example, the method <Ref Subsect="PlanarEmbedding" Style="Number" /> computes for a
planar digraph <A>D</A> the rotation system of a planar embedding of <A>D</A>.
The facial walks of <A>digraph</A> are closed walks and they are defined by the rotation system <A>list</A>.
They describe the boundaries of the faces of the embedding of <A>digraph</A> given
by the rotation system <A>list</A>.
<#GAPDoc Label="HamiltonianPath">
<ManSection>
<Attr Name="HamiltonianPath" Arg="digraph"/>
<Returns>A list or <K>fail</K>.</Returns>
<Description>
Returns a Hamiltonian path if one exists, <K>fail</K> if not.<P/>
A <E>Hamiltonian path</E> of a digraph with <C>n</C> vertices is directed
cycle of length <C>n</C>. If <A>digraph</A> is a digraph that contains a
Hamiltonian path, then this function returns one, described in the form
used by <Ref Attr="DigraphAllSimpleCircuits"/>. Note if <A>digraph</A> has
0 or 1 vertices, then <C>HamiltonianPath</C> returns <C>[]</C> or
<C>[1]</C>, respectively.<P/>
The method used in this attribute has the same worst case complexity as
<Ref Oper="DigraphMonomorphism"/>.
<Example><![CDATA[
gap> D := Digraph([[]]);
<immutable empty digraph with 1 vertex>
gap> HamiltonianPath(D);
[ 1 ]
gap> D := Digraph([[2], [1]]);
<immutable digraph with 2 vertices, 2 edges>
gap> HamiltonianPath(D);
[ 1, 2 ]
gap> D := Digraph([[3], [], [2]]);
<immutable digraph with 3 vertices, 2 edges>
gap> HamiltonianPath(D);
fail
gap> D := Digraph([[2], [3], [1]]);
<immutable digraph with 3 vertices, 3 edges>
gap> HamiltonianPath(D);
[ 1, 2, 3 ]
gap> D := GeneralisedPetersenGraph(IsMutableDigraph, 5, 2);
<mutable digraph with 10 vertices, 30 edges>
gap> HamiltonianPath(D);
fail
]]></Example>
</Description>
</ManSection>
<#/GAPDoc>
<#GAPDoc Label="DigraphPeriod">
<ManSection>
<Attr Name="DigraphPeriod" Arg="digraph"/>
<Returns>An integer.</Returns>
<Description>
This function returns the period of the digraph <A>digraph</A>.<P/>
If a digraph <A>digraph</A> has at least one directed cycle, then the period
is the greatest positive integer which divides the lengths of all directed
cycles of <A>digraph</A>. If <A>digraph</A> has no directed cycles, then
this function returns <M>0</M>. See Section <Ref Subsect="Definitions"
Style="Number" /> for the definition of a directed cycle. <P/>
A digraph with a period of <M>1</M> is said to be <E>aperiodic</E>. See
<Ref Prop="IsAperiodicDigraph"/>. <P/>
<Example><![CDATA[
gap> D := Digraph([[6], [1], [2], [3], [4, 4], [5]]);
<immutable multidigraph with 6 vertices, 7 edges>
gap> DigraphPeriod(D);
6
gap> D := Digraph([[2], [3, 5], [4], [5], [1, 2]]);
<immutable digraph with 5 vertices, 7 edges>
gap> DigraphPeriod(D);
1
gap> D := ChainDigraph(2);
<immutable chain digraph with 2 vertices>
gap> DigraphPeriod(D);
0
gap> IsAcyclicDigraph(D);
true
gap> D := GeneralisedPetersenGraph(IsMutableDigraph, 5, 2);
<mutable digraph with 10 vertices, 30 edges>
gap> DigraphPeriod(D);
1
]]></Example>
</Description>
</ManSection>
<#/GAPDoc>
<#GAPDoc Label="DigraphLoops">
<ManSection>
<Attr Name="DigraphLoops" Arg="digraph"/>
<Returns>A list of vertices.</Returns>
<Description>
If <A>digraph</A> is a digraph, then <C>DigraphLoops</C> returns the list
consisting of the <Ref Attr="DigraphVertices"/> of <A>digraph</A>
at which there is a loop. See <Ref Prop="DigraphHasLoops"/>. <P/>
<#GAPDoc Label="ChromaticNumber">
<ManSection>
<Attr Name="ChromaticNumber" Arg="digraph"/>
<Returns> A non-negative integer.</Returns>
<Description>
A <E>proper colouring</E> of a digraph is a labelling of its
vertices in such a way that adjacent vertices have different labels.
Equivalently, a proper digraph colouring can be defined to be a <Ref
Oper="DigraphEpimorphism"/> from a digraph onto a complete digraph. <P/>
If <A>digraph</A> is a digraph without loops (see <Ref
Prop="DigraphHasLoops"/>, then <C>ChromaticNumber</C> returns the least
non-negative integer <C>n</C> such that there is a proper colouring of
<A>digraph</A> with <C>n</C> colours. In other words, for a digraph with at
least one vertex, <C>ChromaticNumber</C> returns the least number <C>n</C>
such that <C>DigraphColouring(<A>digraph</A>, n)</C> does not return
<K>fail</K>. See <Ref Oper="DigraphColouring"
Label="for a digraph and a number of colours"/>. <P/>
It is possible to select the algorithm to compute the chromatic number via
the use of value options. The permitted algorithms and values to
pass as options are:
<List>
<Item><C>lawler</C> - Lawler's Algorithm
<Cite Key="Law1976"/></Item>
<Item><C>byskov</C> - Byskov's Algorithm
<Cite Key="Bys2002"/></Item>
<Item><C>zykov</C> - Zykov's Algorithm
<Cite Key="Corneil1973"/></Item>
<Item><C>christofides</C> - Christofides's Algorithm
<Cite Key="Wang1974"/></Item>
</List>
<#GAPDoc Label="DigraphBicomponents">
<ManSection>
<Attr Name="DigraphBicomponents" Arg="digraph"/>
<Returns>A pair of lists of vertices, or <K>fail</K>.</Returns>
<Description>
If <A>digraph</A> is a bipartite digraph, i.e. if it satisfies <Ref
Prop="IsBipartiteDigraph"/>, then <C>DigraphBicomponents</C> returns a
pair of bicomponents of <A>digraph</A>. Otherwise,
<C>DigraphBicomponents</C> returns <K>fail</K>.<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 <E>bicomponents</E> of <A>digraph</A>.
Equivalently, a pair of bicomponents of <A>digraph</A> consists of the
color-classes of a 2-coloring of <A>digraph</A>. <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 <Ref
Prop="IsConnectedDigraph"/> for more information.
<Example><![CDATA[
gap> D := CycleDigraph(3);
<immutable cycle digraph with 3 vertices>
gap> DigraphBicomponents(D);
fail
gap> D := ChainDigraph(5);
<immutable chain digraph with 5 vertices>
gap> DigraphBicomponents(D);
[ [ 1, 3, 5 ], [ 2, 4 ] ]
gap> D := Digraph([[5], [1, 4], [5], [5], []]);
<immutable digraph with 5 vertices, 5 edges>
gap> DigraphBicomponents(D);
[ [ 1, 3, 4 ], [ 2, 5 ] ]
gap> D := CompleteBipartiteDigraph(IsMutableDigraph, 2, 3);
<mutable digraph with 5 vertices, 12 edges>
gap> DigraphBicomponents(D);
[ [ 1, 2 ], [ 3, 4, 5 ] ]
]]></Example>
</Description>
--> --------------------
--> maximum size reached
--> --------------------
[ zur Elbe Produktseite wechseln0.72Quellennavigators
Analyse erneut starten
]
