GAP (Digraphs) - Chapter 5: Attributes and operations

Note that the vertices of a digraph are always the range of positive integers from 1 to the number of vertices of the graph, DigraphNrVertices (5.1-2). Arbitrary labels can be assigned to the vertices of a digraph; see DigraphVertexLabels (5.1-12) for more information about this.

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

5.1-2 DigraphNrVertices

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

5.1-3 DigraphEdges

Returns a list of edges of the digraph digraph, where each edge is a pair of elements of DigraphVertices (5.1-1) of the form [source,range].

The entries of DigraphEdges(digraph) are in one-to-one correspondence with the edges of digraph. Hence DigraphEdges(digraph) is duplicate-free if and only if digraph contains no multiple edges.

The entries of DigraphEdges 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.

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

5.1-4 DigraphNrEdges

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

5.1-5 DigraphNrAdjacencies

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

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

5.1-6 DigraphNrAdjacenciesWithoutLoops

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

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

5.1-7 DigraphNrLoops

This function returns the number of loops of the digraph digraph. See DigraphHasLoops (6.2-1).

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

5.1-8 DigraphSinks

This function returns a list of the sinks of the digraph digraph. A sink of a digraph is a vertex with out-degree zero. See OutDegreeOfVertex (5.2-10).

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);
[  ]

5.1-9 DigraphSources

This function returns an immutable list of the sources of the digraph digraph. A source of a digraph is a vertex with in-degree zero. See InDegreeOfVertex (5.2-12).

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);
[  ]

5.1-10 DigraphTopologicalSort

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

See Section 1.1-1 for the definition of a directed cycle, and the definition of a loop.

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

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 ]

5.1-11 DigraphVertexLabel

If digraph is a digraph, then the first operation returns the label of the vertex i. The second operation can be used to set the label of the vertex i in digraph to the arbitrary GAP object obj.

The label of a vertex can be changed an arbitrary number of times. If no label has been set for the vertex i, then the default value is i.

If digraph is a digraph created from a record with a component DigraphVertices, then the labels of the vertices are set to the value of this component.

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

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

5.1-12 DigraphVertexLabels

If digraph is a digraph, then DigraphVertexLabels returns a copy of the labels of the vertices in digraph. SetDigraphVertexLabels can be used to set the labels of the vertices in digraph to the list of arbitrary GAP objects list, which must be of the same length as the number of vertices of digraph.

If the list list is immutable, then the vertex labels are set to a mutable copy of list. Otherwise, the labels are set to exactly list.

The label of a vertex can be changed an arbitrary number of times. If no label has been set for the vertex i, then the default value is i.

If digraph is a digraph created from a record with a component DigraphVertices, 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 DigraphVertices. Otherwise, they are set to exactly DigraphVertices.

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

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

5.1-13 DigraphEdgeLabel

If digraph is a digraph without multiple edges, then the first operation returns the label of the edge from vertex i to vertex j. The second operation can be used to set the label of the edge between vertex i and vertex j to the arbitrary GAP object obj.

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

Induced subdigraphs, and some other operations which create new digraphs from old ones, inherit their edge labels from their parents. See also DigraphEdgeLabels (5.1-14).

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

5.1-14 DigraphEdgeLabels

If digraph is a digraph without multiple edges, then DigraphEdgeLabels returns a copy of the labels of the edges in digraph as a list of lists labels such that labels[i][j] is the label on the edge from vertex i to vertex OutNeighbours(digraph)[i][j]. SetDigraphEdgeLabels can be used to set the labels of the edges in digraph without multiple edges to the list labels of lists of arbitrary GAP objects such that list[i][j] is the label on the edge from vertex i to the vertex OutNeighbours(digraph>[i][j]. Alternatively SetDigraphEdgeLabels can be called with binary function func that as its second argument that when passed two vertices i and j returns the label for the edge between vertex i and vertex j.

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

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

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

5.1-15 DigraphInEdges

DigraphInEdges returns the list of all edges of digraph which have vertex as their range.

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

5.1-16 DigraphOutEdges

DigraphOutEdges returns the list of all edges of digraph which have vertex as their source.

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

5.1-17 IsDigraphEdge

In the first form, this function returns true if and only if the list list specifies an edge in the digraph digraph. Specifically, this operation returns true if list is a pair of positive integers where list[1] is the source and list[2] is the range of an edge in digraph, and false otherwise.

The second form simply returns true if [u, v] is an edge in digraph, and false otherwise.

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

5.1-18 IsMatching

If digraph is a digraph and list is a list of pairs of vertices of digraph, then IsMatching returns true if list is a matching of digraph. The operation IsMaximalMatching returns true if list is a maximal matching, IsMaximumMatching returns true if list is a maximum matching and IsPerfectMatching returns true if list is a perfect, matching of digraph, respectively. Otherwise, each of these operations return false.

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

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

5.1-19 DigraphMaximalMatching

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

5.1-20 DigraphMaximumMatching

For the definition of a maximum matching, see IsMaximumMatching (5.1-18). If digraph is bipartite (see IsBipartiteDigraph (6.2-3)), then the algorithm used has complexity O(m*sqrt(n)). Otherwise for general graphs the complexity is O(m*n*log(n)). Here n is the number of vertices and m is the number of edges.

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

5.2 Neighbours and degree

5.2-1 AdjacencyMatrix

This function returns the adjacency matrix mat of the digraph digraph. The value of the matrix entry mat[i][j] is the number of edges in digraph with source i and range j. If digraph has no vertices, then the empty list is returned.

The function AdjacencyMatrix returns an immutable list of lists, whereas the function AdjacencyMatrixMutableCopy returns a copy of AdjacencyMatrix that is a mutable list of mutable lists.

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

5.2-2 CharacteristicPolynomial

This function returns the characteristic polynomial of the digraph digraph. That is it returns the characteristic polynomial of the adjacency matrix of the digraph digraph

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

5.2-3 BooleanAdjacencyMatrix

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

The attribute BooleanAdjacencyMatrix returns an immutable list of immutable lists, whereas the function BooleanAdjacencyMatrixMutableCopy returns a copy of the BooleanAdjacencyMatrix that is a mutable list of mutable lists.

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

5.2-4 DigraphAdjacencyFunction

If digraph is a digraph, then DigraphAdjacencyFunction returns a function which takes two integer parameters x, y and returns true if there exists an edge from vertex x to vertex y in digraph and false if not.

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

5.2-5 DigraphRange

DigraphRange and DigraphSource return the range and source of the digraph digraph. More precisely, position i in DigraphSource(digraph) and DigraphRange(digraph) give, respectively, the source and range of the ith edge of digraph.

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

5.2-6 OutNeighbours

OutNeighbours returns the list out of out-neighbours of each vertex of the digraph digraph. More specifically, a vertex j appears in out[i] each time there exists the edge [i, j] in digraph.

The function OutNeighbours returns an immutable list of lists, whereas the function OutNeighboursMutableCopy returns a copy of OutNeighbours which is a mutable list of mutable lists.

Note that the entries of out are not guaranteed to be sorted in any particular order.

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

5.2-7 InNeighbours

InNeighbours returns the list inn of in-neighbours of each vertex of the digraph digraph. More specifically, a vertex j appears in inn[i] each time there exists an edge [j,i] in digraph.

The function InNeighbours returns an immutable list of lists, whereas the function InNeighboursMutableCopy returns a copy of InNeighbours which is a mutable list of mutable lists.

Note that the entries of inn are not necessarily sorted into ascending order, particularly if digraph was constructed via DigraphByInNeighbours (3.1-11).

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

5.2-8 OutDegrees

Given a digraph digraph with \(n\) vertices, the function OutDegrees returns an immutable list out of length \(n\), such that for a vertex i in digraph, the value of out[i] is the out-degree of vertex i. See OutDegreeOfVertex (5.2-10).

The function OutDegreeSequence returns the same list, after it has been sorted into non-increasing order.

The function OutDegreeSet returns the same list, sorted into increasing order with duplicate entries removed.

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

5.2-9 InDegrees

Given a digraph digraph with \(n\) vertices, the function InDegrees returns an immutable list inn of length \(n\), such that for a vertex i in digraph, the value of inn[i] is the in-degree of vertex i. See InDegreeOfVertex (5.2-12).

The function InDegreeSequence returns the same list, after it has been sorted into non-increasing order.

The function InDegreeSet returns the same list, sorted into increasing order with duplicate entries removed.

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

5.2-10 OutDegreeOfVertex

This operation returns the out-degree of the vertex vertex in the digraph digraph. The out-degree of vertex is the number of edges in digraph whose source is vertex.

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

5.2-11 OutNeighboursOfVertex

This operation returns the list out of vertices of the digraph digraph. A vertex i appears in the list out each time there exists an edge with source vertex and range i in digraph; in particular, this means that out may contain duplicates.

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

5.2-12 InDegreeOfVertex

This operation returns the in-degree of the vertex vertex in the digraph digraph. The in-degree of vertex is the number of edges in digraph whose range is vertex.

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

5.2-13 InNeighboursOfVertex

This operation returns the list inn of vertices of the digraph digraph. A vertex i appears in the list inn each time there exists an edge with source i and range vertex in digraph; in particular, this means that inn may contain duplicates.

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

5.2-14 DigraphLoops

If digraph is a digraph, then DigraphLoops returns the list consisting of the DigraphVertices (5.1-1) of digraph at which there is a loop. See DigraphHasLoops (6.2-1).

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

5.2-15 DegreeMatrix

Returns the out-degree matrix mat of the digraph digraph. The value of the ith diagonal matrix entry is the out-degree of the vertex i in digraph. All off-diagonal entries are 0. If digraph has no vertices, then the empty list is returned.

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

5.2-16 LaplacianMatrix

Returns the out-degree Laplacian matrix mat of the digraph digraph. The out-degree Laplacian matrix is defined as DegreeMatrix(digraph) - AdjacencyMatrix(digraph). If digraph has no vertices, then the empty list is returned.

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

5.3 Orders

5.3-1 PartialOrderDigraphMeetOfVertices

If the first argument is a partial order digraph IsPartialOrderDigraph (6.4-2) then these operations return the meet, or the join, of the two input vertices. If the meet (or join) is does not exist then fail is returned. The meet (or join) is guaranteed to exist when the first argument satisfies IsMeetSemilatticeDigraph (6.4-3) (or IsJoinSemilatticeDigraph (6.4-3)) - see the documentation for these properties for the definition of the meet (or the join).

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

5.3-2 NonUpperSemimodularPair

NonUpperSemimodularPair returns a pair of vertices in the digraph D that witnesses the fact that D does not represent an upper semimodular lattice, if such a pair exists.

If the digraph D does not satisfy IsLatticeDigraph (6.4-3), then an error is given. Otherwise if the digraph D does satisfy IsLatticeDigraph (6.4-3), then either a non-upper semimodular pair of vertices is returned, or fail is returned if no such pair exists (meaning that D is an upper semimodular lattice.

NonLowerSemimodularPair behaves in the analogous way to NonUpperSemimodularPair with respect to lower semimodularity.

See IsUpperSemimodularDigraph (6.4-5) and IsLowerSemimodularDigraph (6.4-5) for the definition of upper semimodularity of a lattice.

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

5.4 Reachability and connectivity

5.4-1 DigraphDiameter

If a digraph digraph is strongly connected and has at least 1 vertex, then the diameter is the maximum shortest distance between any pair of distinct vertices. Otherwise then the diameter of digraph is undefined, and this function returns the value fail.

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

5.4-2 DigraphShortestDistance

If there is a directed path in the digraph digraph between vertex u and vertex v, then this operation returns the length of the shortest such directed path. If no such directed path exists, then this operation returns fail. See Section 1.1-1 for the definition of a directed path.

If the second form is used, then list should be a list of length two, containing two positive integers which correspond to the vertices u and v.

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

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

5.4-3 DigraphShortestDistances

If digraph is a digraph with \(n\) vertices, then this function returns an \(n \times n\) matrix mat, where each entry is either a non-negative integer, or fail. If \(n = 0\), then an empty list is returned.

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

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

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

5.4-4 DigraphLongestDistanceFromVertex

If digraph is a digraph and v is a vertex in digraph, then this operation returns the length of the longest directed walk in digraph which begins at vertex v. See Section 1.1-1 for the definitions of directed walk, directed cycle, and loop.

Note that the result is 0 if and only if v is a sink of digraph. See DigraphSinks (5.1-8).

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

5.4-5 DigraphDistanceSet

This operation returns the list of all vertices in digraph digraph such that the shortest distance to a vertex vertex is distance or is in the list distances.

digraph should be a digraph, vertex should be a positive integer, distance should be a non-negative integer, and distances should be a list of non-negative integers.

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

5.4-6 DigraphGirth

This attribute returns the girth of the digraph digraph. The girth of a digraph is the length of its shortest simple circuit. See Section 1.1-1 for the definitions of simple circuit, directed cycle, and loop.

If digraph has no directed cycles, then this function will return infinity. If digraph contains a loop, then this function will return 1.

In the worst case, the method used in this function is a version of the Floyd-Warshall algorithm, and has complexity O(n ^ 3), where n is the number of vertices in digraph. If the digraph has known automorphisms [see DigraphGroup (7.2-10)], then the performance is likely to be better.

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

5.4-7 DigraphOddGirth

This attribute returns the odd girth of the digraph digraph. The odd girth of a digraph is the length of its shortest simple circuit of odd length. See Section 1.1-1 for the definitions of simple circuit, directed cycle, and loop.

If digraph has no directed cycles of odd length, then this function will return infinity, even if digraph has a directed cycle of even length. If digraph contains a loop, then this function will return 1.

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

5.4-8 DigraphUndirectedGirth

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

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

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

5.4-9 DigraphConnectedComponents

This function returns the record wcc corresponding to the weakly connected components of the digraph digraph. Two vertices of digraph 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 digraph if and only if they are in the same strongly connected component (see DigraphStronglyConnectedComponents (5.4-11)) of the DigraphSymmetricClosure (3.3-12) of digraph.

The set of weakly connected components is a partition of the vertex set of digraph.

The record wcc has 2 components: comps and id. The component comps is a list of the weakly connected components of digraph (each of which is a list of vertices). The component id is a list such that the vertex i is an element of the weakly connected component comps[id[i]].

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

DigraphNrConnectedComponents(digraph) is simply a shortcut for Length(DigraphConnectedComponents(digraph).comps), and is no more efficient.

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

5.4-10 DigraphConnectedComponent

If vertex is a vertex in the digraph digraph, then this operation returns the connected component of vertex in digraph. See DigraphConnectedComponents (5.4-9) for more information.

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

5.4-11 DigraphStronglyConnectedComponents

This function returns the record scc corresponding to the strongly connected components of the digraph digraph. Two vertices of digraph 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 digraph.

The record scc has 2 components: comps and id. The component comps is a list of the strongly connected components of digraph (each of which is a list of vertices). The component id is a list such that the vertex i is an element of the strongly connected component comps[id[i]].

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

DigraphNrStronglyConnectedComponents(digraph) is simply a shortcut for Length(DigraphStronglyConnectedComponents(digraph).comps), and is no more efficient.

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

5.4-12 DigraphStronglyConnectedComponent

If vertex is a vertex in the digraph digraph, then this operation returns the strongly connected component of vertex in digraph. See DigraphStronglyConnectedComponents (5.4-11) for more information.

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

5.4-13 DigraphBicomponents

If digraph is a bipartite digraph, i.e. if it satisfies IsBipartiteDigraph (6.2-3), then DigraphBicomponents returns a pair of bicomponents of digraph. Otherwise, DigraphBicomponents returns fail.

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

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 IsConnectedDigraph (6.6-3) for more information.

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

5.4-14 ArticulationPoints

A connected digraph is biconnected if it is still connected (in the sense of IsConnectedDigraph (6.6-3)) when any vertex is removed. If the digraph digraph is not biconnected but is connected, then any vertex v of digraph whose removal makes the resulting digraph disconnected is called an articulation point.

ArticulationPoints returns a list of the articulation points of digraph, if any, and, in particular, returns the empty list if digraph is not connected.

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

If D has a bridge (see Bridges (5.4-15)), then a node incident to the bridge is an articulation point if and only if it has degree at least \(2\). It follows that if D has a bridge and at least \(3\) nodes, then at least one of the nodes incident to the bridge is an articulation point. The converse does not hold, there are digraphs with articulation points, but no bridges.

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

5.4-15 Bridges

A connected digraph is 2-edge-connected if it is still connected (in the sense of IsConnectedDigraph (6.6-3)) when any edge is removed. If the digraph D is not 2-edge-connected but is connected, then any edge [u, v] of D whose removal makes the resulting digraph disconnected is called a bridge.

Bridges returns a list of the bridges of D, if any, and, in particular, returns the empty list if D is not connected.

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

If D has a bridge, then a node incident to the bridge is an articulation point (see ArticulationPoints (5.4-14)) if and only if it has degree at least \(2\). It follows that if D has a bridge and at least \(3\) nodes, then at least one of the nodes incident to the bridge is an articulation point. The converse does not hold, there are digraphs with articulation points, but no bridges.

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

5.4-16 StrongOrientation

A strong orientation of a connected symmetric digraph D (if it exists) is a strongly connected subdigraph C of D such that for every edge [u, v] of D either [u, v] or [v, u] is an edge of C but not both. Robbin's Theorem states that a digraph admits a strong orientation if and only if it is bridgeless (see IsBridgelessDigraph (6.6-5)).

This operation returns a strong orientation of the digraph D if D is symmetric and D admits a strong orientation. If D is symmetric but does not admit a strong orientation, then fail is returned. If D is not symmetric, then an error is given.

If D is immutable, StrongOrientation(D) returns an immutable digraph, and if D is mutable, then StrongOrientation(D) returns a mutable digraph.

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

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

5.4-17 DigraphPeriod

If a digraph digraph has at least one directed cycle, then the period is the greatest positive integer which divides the lengths of all directed cycles of digraph. If digraph has no directed cycles, then this function returns \(0\). See Section 1.1-1 for the definition of a directed cycle.

A digraph with a period of \(1\) is said to be aperiodic. See IsAperiodicDigraph (6.6-7).

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

5.4-18 DigraphFloydWarshall

If digraph is a digraph with \(n\) vertices, then this operation returns an \(n \times n\) matrix mat containing the output of a generalised version of the Floyd-Warshall algorithm, applied to digraph.

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

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

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;

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

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

5.4-19 IsReachable

This operation returns true if there exists a non-trivial directed walk from vertex u to vertex v in the digraph digraph, and false if there does not exist such a directed walk. See Section 1.1-1 for the definition of a non-trivial directed walk.

The method for IsReachable has worst case complexity of \(O(m + n)\) where \(m\) is the number of edges and \(n\) the number of vertices in digraph.

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

5.4-20 IsDigraphPath

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

If the arguments to IsDigraphPath are a digraph D and list list, then this is equivalent to calling IsDigraphPath(D, list[1], list[2]).

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

5.4-21 VerticesReachableFrom

This operation returns a list of the vertices v, for which there exists a non-trivial directed walk from the vertex root, or any of the list of vertices list, to vertex v in the digraph digraph. See Section 1.1-1 for the definition of a non-trivial directed walk.

The method for VerticesReachableFrom has worst case complexity of \(O(m + n)\) where \(m\) is the number of edges and \(n\) the number of vertices in digraph.

This function returns an error if root, or any vertex in list, is not a vertices of digraph.

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

5.4-22 DigraphPath

If there exists a non-trivial directed path (or a non-trivial cycle, in the case that u = v) from vertex u to vertex v in the digraph digraph, then this operation returns such a directed path (or directed cycle). Otherwise, this operation returns fail. See Section Definitions for the definition of a directed path and a directed cycle.

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

The method for DigraphPath has worst case complexity of \(O(m + n)\) where \(m\) is the number of edges and \(n\) the number of vertices in digraph.

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

5.4-23 DigraphShortestPath

Returns a shortest directed path in the digraph digraph from vertex u to vertex v, if such a path exists. If u = v, then the shortest non-trivial cycle is returned, again, if it exists. Otherwise, this operation returns fail. See Section Definitions for the definition of a directed path and a directed cycle.

See DigraphPath (5.4-22) for details on the output. The method for DigraphShortestPath has worst case complexity of \(O(m + n)\) where \(m\) is the number of edges and \(n\) the number of vertices in digraph.

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

5.4-24 DigraphRandomWalk

Returns a directed path corresponding to a random walk in the digraph digraph, starting at vertex v and having length no more than t.

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

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

5.4-25 DigraphAbsorptionProbabilities

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

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

Strongly connected components are indexed in the order given by DigraphStronglyConnectedComponents (5.4-11). See also DigraphRandomWalk (5.4-24) and DigraphAbsorptionExpectedSteps (5.4-26).

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

5.4-26 DigraphAbsorptionExpectedSteps

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

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

See also DigraphRandomWalk (5.4-24) and DigraphAbsorptionProbabilities (5.4-25).

gap> gr := Digraph([[2], [3, 4], [], [2]]);
<immutable digraph with 4 vertices, 4 edges>
gap> DigraphAbsorptionExpectedSteps(gr);
[ 4, 3, 0, 4 ]

5.4-27 Dominators

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

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

5.4-28 DominatorTree

DominatorTree takes a digraph and a root vertex and returns a record with the following components:

The immediate dominator of a vertex \(u\) is the unique dominator of \(u\) that is dominated by all other dominators of \(u\). The algorithm is an implementation of the fast algorithm written by Thomas Lengauer and Robert Endre Tarjan [LT79]. The complexity of this algorithm is \(O(mlog n)\) where \(m\) is the number of edges and \(n\) is the number of nodes in the subdigraph induced by the nodes in digraph reachable from root.

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

5.4-29 IteratorOfPaths

If digraph is a digraph or a list of adjacencies which defines a digraph - see OutNeighbours (5.2-6) - then this operation returns an iterator of the non-trivial directed paths (or directed cycles, in the case that u = v) in digraph from the vertex u to the vertex v.

See DigraphPath (5.4-22) for more information about the representation of a directed path or directed cycle which is used, and see Reference: Iterators for more information about iterators. See Section Definitions for the definition of a directed path and a directed cycle.

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

5.4-30 DigraphAllSimpleCircuits

If digraph is a digraph, then DigraphAllSimpleCircuits returns a list of the simple circuits in digraph.

See Section 1.1-1 for the definition of a simple circuit, and related notions. Note that a loop is a simple circuit.

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

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

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

5.4-31 DigraphLongestSimpleCircuit

If digraph is a digraph, then DigraphLongestSimpleCircuit returns the longest simple circuit in digraph. See Section 1.1-1 for the definition of simple circuit, and the definition of length for a simple circuit.

This attribute computes DigraphAllSimpleCircuits(digraph) to find all the simple circuits of digraph, and returns one of maximal length. A simple circuit is represented as a list of vertices, in the same way as described in DigraphAllSimpleCircuits (5.4-30).

If digraph has no simple circuits, then this attribute returns fail. If digraph has multiple simple circuits of maximal length, then this attribute returns one of them.

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

5.4-32 DigraphAllUndirectedSimpleCircuits

If digraph is a digraph, then DigraphAllUndirectedSimpleCircuits returns a list of the undirected simple circuits in digraph.

See Section 1.1-1 for the definition of a simple circuit, and related notions. Note that a loop is a simple circuit. A simple circuit is undirected if the orientation of the edges in the circuit does not matter.

The attribute DigraphAllUndirectedSimpleCircuitss ignores multiple edges, and identifies a undirected simple circuit using only its subsequence of vertices. See Section 5.4-30 for more details on simple circuits.

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

5.4-33 DigraphAllChordlessCycles

If digraph is a digraph, then DigraphAllChordlessCycles returns a list of the chordless cycles in digraph.

A chordless cycle \(C\) is a undirected simple circuit (see Section 1.1-1 ) where each pair of vertices in \(C\) are not connected by an edge not in \(C\). Here, cycles of length two are ignored.

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

5.4-34 DigraphLayers

This operation returns a list list such that list[i] is the list of vertices whose minimum distance from the vertex vertex in digraph is i - 1. Vertex vertex is assumed to be at distance 0 from itself.

gap> D := CompleteDigraph(4);;
gap> DigraphLayers(D, 1);
[ [ 1 ], [ 2, 3, 4 ] ]

5.4-35 DigraphDegeneracy

If digraph is a symmetric digraph without multiple edges - see IsSymmetricDigraph (6.2-14) and IsMultiDigraph (6.2-11) - then this attribute returns the degeneracy of digraph.

The degeneracy of a digraph is the least integer k such that every induced of digraph contains a vertex whose number of neighbours (excluding itself) is at most k. Note that this means that loops are ignored.

If digraph is not symmetric or has multiple edges then this attribute returns fail.

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

5.4-36 DigraphDegeneracyOrdering

If digraph is a digraph for which DigraphDegeneracy(digraph) is a non-negative integer k - see DigraphDegeneracy (5.4-35) - then this attribute returns a degeneracy ordering of the vertices of the vertices of digraph.

A degeneracy ordering of digraph is a list ordering of the vertices of digraph ordered such that for any position i of the list, the vertex ordering[i] has at most k neighbours in later position of the list.

If DigraphDegeneracy(digraph) returns fail, then this attribute returns fail.

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

5.4-37 HamiltonianPath

A Hamiltonian path of a digraph with n vertices is directed cycle of length n. If digraph is a digraph that contains a Hamiltonian path, then this function returns one, described in the form used by DigraphAllSimpleCircuits (5.4-30). Note if digraph has 0 or 1 vertices, then HamiltonianPath returns [] or [1], respectively.

The method used in this attribute has the same worst case complexity as DigraphMonomorphism (7.3-4).

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

5.4-38 NrSpanningTrees

Returns the number of spanning trees of the symmetric digraph digraph. NrSpanningTrees will return an error if digraph is not a symmetric digraph.

See IsSymmetricDigraph (6.2-14) and IsUndirectedSpanningTree (4.1-2) for more information.

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

5.4-39 DigraphDijkstra

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

If the optional second argument target is not present, then DigraphDijkstra returns the shortest path from source to every vertex that is reachable from source.

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

5.4-40 DigraphCycleBasis

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

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

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

The fundamental cycle basis is unique up to reordering of the basis vectors. The number of basis vectors in the fundamental cycle basis is \(m - n + c\), where \(m\) is the number of edges, \(n\) is the number of vertices, and \(c\) is the number of connected components. See DigraphConnectedComponents (5.4-9).

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

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

5.5 Cayley graphs of groups

5.5-1 GroupOfCayleyDigraph

If digraph is an immutable Cayley graph of a group G and digraph belongs to the category IsCayleyDigraph (3.1-4), then GroupOfCayleyDigraph returns G.

If digraph is a Cayley graph of a semigroup S and digraph belongs to the category IsCayleyDigraph (3.1-4), then SemigroupOfCayleyDigraph returns S.

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

5.5-2 GeneratorsOfCayleyDigraph

If digraph is an immutable Cayley graph of a group or semigroup with respect to a set of generators gens and digraph belongs to the category IsCayleyDigraph (3.1-4), then GeneratorsOfCayleyDigraph return the list of generators gens over which digraph is defined.

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

5.6 Associated semigroups

5.6-1 AsSemigroup

The operation AsSemigroup requires that filt be equal to IsPartialPermSemigroup (Reference: IsPartialPermSemigroup). If digraph is a IsJoinSemilatticeDigraph (6.4-3) or IsLatticeDigraph (6.4-3) then AsSemigroup returns a semigroup of partial perms which is isomorphic to the semigroup whose elements are the vertices of digraph with the binary operation PartialOrderDigraphJoinOfVertices (5.3-1). If digraph satisfies IsMeetSemilatticeDigraph (6.4-3) but not IsJoinSemilatticeDigraph (6.4-3) then AsSemigroup returns a semigroup of partial perms which is isomorphic to the semigroup whose elements are the vertices of digraph with the binary operation PartialOrderDigraphMeetOfVertices (5.3-1).

The operation AsMonoid behaves similarly to AsSemigroup except that filt may also be equal to IsPartialPermMonoid (Reference: IsPartialPermMonoid), digraph must satisfy IsLatticeDigraph (6.4-3), and the output satisfies IsMonoid (Reference: IsMonoid).

The output of both of these operations is guaranteed to be of minimal degree (see DegreeOfPartialPermSemigroup (Reference: DegreeOfPartialPermSemigroup)). Furthermore the GeneratorsOfSemigroup (Reference: GeneratorsOfSemigroup) of the output is guaranteed to be the unique generating set of minimal size.

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

5.6-2 AsSemigroup

The operation AsSemigroup requires that filt be equal to IsPartialPermSemigroup (Reference: IsPartialPermSemigroup). If Y is a IsJoinSemilatticeDigraph (6.4-3) or IsMeetSemilatticeDigraph (6.4-3), gps is a list of groups corresponding to each vertex, and homs is a list containing for each edge (i, j) in the transitive reduction of digraph a triple [i, j, hom] where hom is a group homomorphism from gps[i] to gps[j], and the diagram of homomorphisms commutes, then AsSemigroup returns a semigroup of partial perms which is isomorphic to the strong semilattice of groups \(S[Y; gps; homs]\).

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

5.7 Planarity

5.7-1 KuratowskiPlanarSubdigraph

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

The directions and multiplicities of any edges in digraph are ignored when considering whether or not digraph is planar.

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

5.7-2 KuratowskiOuterPlanarSubdigraph

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

The directions and multiplicities of any edges in digraph are ignored when considering whether or not digraph is outer planar.

See also IsOuterPlanarDigraph (6.7-2), SubdigraphHomeomorphicToK4 (5.7-5), and SubdigraphHomeomorphicToK23 (5.7-5).

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

5.7-3 PlanarEmbedding

If digraph is a planar digraph, then PlanarEmbedding returns the immutable list of lists of out-neighbours of digraph (excluding multiple edges and loops) such that each vertex's neighbours are given in clockwise order. If digraph is not planar, then fail is returned.

The directions and multiplicities of any edges in digraph are ignored by PlanarEmbedding.

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

5.7-4 OuterPlanarEmbedding

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

The directions and multiplicities of any edges in digraph are ignored by OuterPlanarEmbedding.

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

5.7-5 SubdigraphHomeomorphicToK23

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

See also IsPlanarDigraph (6.7-1) and IsOuterPlanarDigraph (6.7-2) for more details.

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

5.8 Hashing

5.8-1 DigraphHash

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

5 Attributes and operations

5.1 Vertices and edges

5.1-1 DigraphVertices

5.1-2 DigraphNrVertices

5.1-3 DigraphEdges

5.1-4 DigraphNrEdges

5.1-5 DigraphNrAdjacencies

5.1-6 DigraphNrAdjacenciesWithoutLoops

5.1-7 DigraphNrLoops

5.1-8 DigraphSinks

5.1-9 DigraphSources

5.1-10 DigraphTopologicalSort

5.1-11 DigraphVertexLabel

5.1-12 DigraphVertexLabels

5.1-13 DigraphEdgeLabel

5.1-14 DigraphEdgeLabels

5.1-15 DigraphInEdges

5.1-16 DigraphOutEdges

5.1-17 IsDigraphEdge

5.1-18 IsMatching

5.1-19 DigraphMaximalMatching

5.1-20 DigraphMaximumMatching

5.2 Neighbours and degree

5.2-1 AdjacencyMatrix

5.2-2 CharacteristicPolynomial

5.2-3 BooleanAdjacencyMatrix

5.2-4 DigraphAdjacencyFunction

5.2-5 DigraphRange

5.2-6 OutNeighbours

5.2-7 InNeighbours

5.2-8 OutDegrees

5.2-9 InDegrees

5.2-10 OutDegreeOfVertex

5.2-11 OutNeighboursOfVertex

5.2-12 InDegreeOfVertex

5.2-13 InNeighboursOfVertex

5.2-14 DigraphLoops

5.2-15 DegreeMatrix

5.2-16 LaplacianMatrix

5.3 Orders

5.3-1 PartialOrderDigraphMeetOfVertices

5.3-2 NonUpperSemimodularPair

5.4 Reachability and connectivity

5.4-1 DigraphDiameter

5.4-2 DigraphShortestDistance

5.4-3 DigraphShortestDistances

5.4-4 DigraphLongestDistanceFromVertex

5.4-5 DigraphDistanceSet

5.4-6 DigraphGirth

5.4-7 DigraphOddGirth

5.4-8 DigraphUndirectedGirth

5.4-9 DigraphConnectedComponents

5.4-10 DigraphConnectedComponent

5.4-11 DigraphStronglyConnectedComponents

5.4-12 DigraphStronglyConnectedComponent

5.4-13 DigraphBicomponents

5.4-14 ArticulationPoints

5.4-15 Bridges

5.4-16 StrongOrientation

5.4-17 DigraphPeriod

5.4-18 DigraphFloydWarshall

5.4-19 IsReachable

5.4-20 IsDigraphPath

5.4-21 VerticesReachableFrom

5.4-22 DigraphPath

5.4-23 DigraphShortestPath

5.4-24 DigraphRandomWalk

5.4-25 DigraphAbsorptionProbabilities

5.4-26 DigraphAbsorptionExpectedSteps

5.4-27 Dominators

5.4-28 DominatorTree

5.4-29 IteratorOfPaths

5.4-30 DigraphAllSimpleCircuits

5.4-31 DigraphLongestSimpleCircuit

5.4-32 DigraphAllUndirectedSimpleCircuits

5.4-33 DigraphAllChordlessCycles

5.4-34 DigraphLayers

5.4-35 DigraphDegeneracy

5.4-36 DigraphDegeneracyOrdering

5.4-37 HamiltonianPath