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 DigraphSinks

5.1-6 DigraphSources

5.1-7 DigraphTopologicalSort

5.1-8 DigraphVertexLabel

5.1-9 DigraphVertexLabels

5.1-10 DigraphEdgeLabel

5.1-11 DigraphEdgeLabels

5.1-12 DigraphInEdges

5.1-13 DigraphOutEdges

5.1-14 IsDigraphEdge

5.1-15 IsMatching

5.1-1 DigraphVertices

5.1-2 DigraphNrVertices

5.1-3 DigraphEdges

5.1-4 DigraphNrEdges

5.1-5 DigraphSinks

5.1-6 DigraphSources

5.1-7 DigraphTopologicalSort

5.1-8 DigraphVertexLabel

5.1-9 DigraphVertexLabels

5.1-10 DigraphEdgeLabel

5.1-11 DigraphEdgeLabels

5.1-12 DigraphInEdges

5.1-13 DigraphOutEdges

5.1-14 IsDigraphEdge

5.1-15 IsMatching

5.2 Neighbours and degree

5.2-1 AdjacencyMatrix

5.2-2 BooleanAdjacencyMatrix

5.2-3 DigraphAdjacencyFunction

5.2-4 DigraphRange

5.2-5 OutNeighbours

5.2-6 InNeighbours

5.2-7 OutDegrees

5.2-8 InDegrees

5.2-9 OutDegreeOfVertex

5.2-10 OutNeighboursOfVertex

5.2-11 InDegreeOfVertex

5.2-12 InNeighboursOfVertex

5.2-13 DigraphLoops

5.2-14 PartialOrderDigraphMeetOfVertices

5.2-1 AdjacencyMatrix

5.2-2 BooleanAdjacencyMatrix

5.2-3 DigraphAdjacencyFunction

5.2-4 DigraphRange

5.2-5 OutNeighbours

5.2-6 InNeighbours

5.2-7 OutDegrees

5.2-8 InDegrees

5.2-9 OutDegreeOfVertex

5.2-10 OutNeighboursOfVertex

5.2-11 InDegreeOfVertex

5.2-12 InNeighboursOfVertex

5.2-13 DigraphLoops

5.2-14 PartialOrderDigraphMeetOfVertices

5.3 Reachability and connectivity

5.3-1 DigraphDiameter

5.3-2 DigraphShortestDistance

5.3-3 DigraphShortestDistances

5.3-4 DigraphLongestDistanceFromVertex

5.3-5 DigraphDistanceSet

5.3-6 DigraphGirth

5.3-7 DigraphUndirectedGirth

5.3-8 DigraphConnectedComponents

5.3-9 DigraphConnectedComponent

5.3-10 DigraphStronglyConnectedComponents

5.3-11 DigraphStronglyConnectedComponent

5.3-12 DigraphBicomponents

5.3-13 ArticulationPoints

5.3-14 DigraphPeriod

5.3-15 DigraphFloydWarshall

5.3-16 IsReachable

5.3-17 DigraphPath

5.3-18 IteratorOfPaths

5.3-19 DigraphAllSimpleCircuits

5.3-20 DigraphLongestSimpleCircuit

5.3-21 DigraphLayers

5.3-22 DigraphDegeneracy

5.3-23 DigraphDegeneracyOrdering

5.3-24 HamiltonianPath

5.3-1 DigraphDiameter

5.3-2 DigraphShortestDistance

5.3-3 DigraphShortestDistances

5.3-4 DigraphLongestDistanceFromVertex

5.3-5 DigraphDistanceSet

5.3-6 DigraphGirth

5.3-7 DigraphUndirectedGirth

5.3-8 DigraphConnectedComponents

5.3-9 DigraphConnectedComponent

5.3-10 DigraphStronglyConnectedComponents

5.3-11 DigraphStronglyConnectedComponent

5.3-12 DigraphBicomponents

5.3-13 ArticulationPoints

5.3-14 DigraphPeriod

5.3-15 DigraphFloydWarshall

5.3-16 IsReachable

5.3-17 DigraphPath

5.3-18 IteratorOfPaths

5.3-19 DigraphAllSimpleCircuits

5.3-20 DigraphLongestSimpleCircuit

5.3-21 DigraphLayers

5.3-22 DigraphDegeneracy

5.3-23 DigraphDegeneracyOrdering

5.3-24 HamiltonianPath

`‣ DigraphVertices` ( digraph ) | ( attribute ) |

Returns: A list of integers.

Returns the vertices of the digraph `digraph`.

Note that the vertices of a digraph are always a range of positive integers from `1`

to the number of vertices of the graph.

gap> gr := Digraph(["a", "b", "c"], > ["a", "b", "b"], > ["b", "c", "a"]); <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]); <digraph with 6 vertices, 5 edges> gap> DigraphVertices(gr); [ 1 .. 6 ] gap> DigraphVertices(RandomDigraph(100)); [ 1 .. 100 ]

`‣ DigraphNrVertices` ( digraph ) | ( attribute ) |

Returns: An integer.

Returns the number of vertices of the digraph `digraph`.

gap> gr := Digraph(["a", "b", "c"], > ["a", "b", "b"], > ["b", "c", "a"]); <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]); <digraph with 6 vertices, 5 edges> gap> DigraphNrVertices(gr); 6 gap> DigraphNrVertices(RandomDigraph(100)); 100

`‣ DigraphEdges` ( digraph ) | ( attribute ) |

Returns: A list of lists.

`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 corresponence 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~"); <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 ] ]

`‣ DigraphNrEdges` ( digraph ) | ( attribute ) |

Returns: An integer.

This function returns the number of edges of the digraph `digraph`.

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"]); <multidigraph with 3 vertices, 3 edges> gap> DigraphNrEdges(gr); 3

`‣ DigraphSinks` ( digraph ) | ( attribute ) |

Returns: A list of vertices.

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-9).

gap> gr := Digraph([[3, 5, 2, 2], [3], [], [5, 2, 5, 3], []]); <multidigraph with 5 vertices, 9 edges> gap> DigraphSinks(gr); [ 3, 5 ]

`‣ DigraphSources` ( digraph ) | ( attribute ) |

Returns: A list of vertices.

This function returns a list of the sources of the digraph `digraph`. A source of a digraph is a vertex with in-degree zero. See `InDegreeOfVertex`

(5.2-11).

gap> gr := Digraph([[3, 5, 2, 2], [3], [], [5, 2, 5, 3], []]); <multidigraph with 5 vertices, 9 edges> gap> DigraphSources(gr); [ 1, 4 ]

`‣ DigraphTopologicalSort` ( digraph ) | ( attribute ) |

Returns: A list of positive integers, or `fail`

.

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> gr := Digraph([ > [2, 3], [], [4, 6], [5], [], [7, 8, 9], [], [], []]); <digraph with 9 vertices, 8 edges> gap> DigraphTopologicalSort(gr); [ 2, 5, 4, 7, 8, 9, 6, 3, 1 ]

`‣ DigraphVertexLabel` ( digraph, i ) | ( operation ) |

`‣ SetDigraphVertexLabel` ( digraph, i, obj ) | ( operation ) |

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

, then the labels of the vertices are set to the value of this component.

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

gap> gr := DigraphFromDigraph6String("+D[NGc_"); <digraph with 5 vertices, 11 edges> gap> DigraphVertexLabel(gr, 3); 3 gap> gr := Digraph(["a", "b", "c"], [], []); <digraph with 3 vertices, 0 edges> gap> DigraphVertexLabel(gr, 2); "b" gap> SetDigraphVertexLabel(gr, 2, "d"); gap> DigraphVertexLabel(gr, 2); "d" gap> gr := InducedSubdigraph(gr, [1, 2]); <digraph with 2 vertices, 0 edges> gap> DigraphVertexLabel(gr, 2); "d"

`‣ DigraphVertexLabels` ( digraph ) | ( operation ) |

`‣ SetDigraphVertexLabels` ( digraph, list ) | ( operation ) |

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

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

, then the labels of the vertices are set to the value of this component.

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

gap> gr := DigraphFromDigraph6String("+D[NGc_"); <digraph with 5 vertices, 11 edges> gap> DigraphVertexLabels(gr); [ 1 .. 5 ] gap> gr := Digraph(["a", "b", "c"], [], []); <digraph with 3 vertices, 0 edges> gap> DigraphVertexLabels(gr); [ "a", "b", "c" ] gap> SetDigraphVertexLabel(gr, 2, "d"); gap> DigraphVertexLabels(gr); [ "a", "d", "c" ] gap> gr := InducedSubdigraph(gr, [1, 3]); <digraph with 2 vertices, 0 edges> gap> DigraphVertexLabels(gr); [ "a", "c" ]

`‣ DigraphEdgeLabel` ( digraph, i, j ) | ( operation ) |

`‣ SetDigraphEdgeLabel` ( digraph, i, j, obj ) | ( operation ) |

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-11).

gap> gr := DigraphFromDigraph6String("+D[NGc_"); <digraph with 5 vertices, 11 edges> gap> DigraphEdgeLabel(gr, 3, 1); 1 gap> SetDigraphEdgeLabel(gr, 2, 5, [42]); gap> DigraphEdgeLabel(gr, 2, 5); [ 42 ] gap> gr := InducedSubdigraph(gr, [2, 5]); <digraph with 2 vertices, 3 edges> gap> DigraphEdgeLabel(gr, 1, 2); [ 42 ]

`‣ DigraphEdgeLabels` ( digraph ) | ( operation ) |

`‣ SetDigraphEdgeLabels` ( digraph, labels ) | ( operation ) |

`‣ SetDigraphEdgeLabels` ( digraph, func ) | ( operation ) |

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> gr := DigraphFromDigraph6String("+D[NGc_"); <digraph with 5 vertices, 11 edges> gap> DigraphEdgeLabels(gr); [ [ 1 ], [ 1, 1, 1 ], [ 1 ], [ 1, 1, 1 ], [ 1, 1, 1 ] ] gap> SetDigraphEdgeLabel(gr, 2, 1, "d"); gap> DigraphEdgeLabels(gr); [ [ 1 ], [ "d", 1, 1 ], [ 1 ], [ 1, 1, 1 ], [ 1, 1, 1 ] ] gap> gr := InducedSubdigraph(gr, [1, 2, 3]); <digraph with 3 vertices, 4 edges> gap> DigraphEdgeLabels(gr); [ [ 1 ], [ "d", 1 ], [ 1 ] ] gap> OutNeighbours(gr); [ [ 3 ], [ 1, 3 ], [ 1 ] ]

`‣ DigraphInEdges` ( digraph, vertex ) | ( operation ) |

Returns: A list of edges.

`DigraphInEdges`

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

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

`‣ DigraphOutEdges` ( digraph, vertex ) | ( operation ) |

Returns: A list of edges.

`DigraphOutEdges`

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

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

`‣ IsDigraphEdge` ( digraph, list ) | ( operation ) |

`‣ IsDigraphEdge` ( digraph, u, v ) | ( operation ) |

Returns: `true`

or `false`

.

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

is an edge in `u`, `v`]`digraph`, and `false`

otherwise.

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

`‣ IsMatching` ( digraph, list ) | ( operation ) |

`‣ IsMaximalMatching` ( digraph, list ) | ( operation ) |

`‣ IsPerfectMatching` ( digraph, list ) | ( operation ) |

Returns: `true`

or `false`

.

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 operations `IsMaximalMatching`

and `IsPerfectMatching`

return `true`

if `list` is a maximal, or perfect, matching of `digraph`, respectively. Otherwise, these operations return `false`

.

A *matching* `M`

of a digraph `digraph` is a subset of the edges of `digraph`, i.e. `DigraphEdges(`

, such that no pair of distinct edges in `digraph`)`M`

are incident to the same vertex of `digraph`. Note that this definition allows a matching to contain loops. See `DigraphHasLoops`

(6.1-1). The matching `M`

is *maximal* if it is contained in no larger matching of the digraph, and is *perfect* if every vertex of the digraph is incident to an edge in the matching. Every perfect matching is maximal.

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

`‣ AdjacencyMatrix` ( digraph ) | ( attribute ) |

`‣ AdjacencyMatrixMutableCopy` ( digraph ) | ( operation ) |

Returns: A square matrix of non-negative integers.

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

`‣ BooleanAdjacencyMatrix` ( digraph ) | ( attribute ) |

`‣ BooleanAdjacencyMatrixMutableCopy` ( digraph ) | ( operation ) |

Returns: A square matrix of booleans.

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.

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

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

`‣ DigraphAdjacencyFunction` ( digraph ) | ( attribute ) |

Returns: A function.

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

`‣ DigraphRange` ( digraph ) | ( attribute ) |

`‣ DigraphSource` ( digraph ) | ( attribute ) |

Returns: A list of positive integers.

`DigraphRange`

and `DigraphSource`

return the range and source of the digraph `digraph`. More precisely, position `i`

in `DigraphRange(`

is the range of the `digraph`)`i`

th edge of `digraph`.

gap> gr := Digraph([ > [2, 1, 3, 5], [1, 3, 4], [2, 3], [2], [1, 2, 3, 4]]); <digraph with 5 vertices, 14 edges> gap> DigraphRange(gr); [ 2, 1, 3, 5, 1, 3, 4, 2, 3, 2, 1, 2, 3, 4 ] gap> DigraphSource(gr); [ 1, 1, 1, 1, 2, 2, 2, 3, 3, 4, 5, 5, 5, 5 ] 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 ] ]

`‣ OutNeighbours` ( digraph ) | ( attribute ) |

`‣ OutNeighbors` ( digraph ) | ( attribute ) |

`‣ OutNeighboursMutableCopy` ( digraph ) | ( operation ) |

`‣ OutNeighborsMutableCopy` ( digraph ) | ( operation ) |

Returns: The adjacencies of a digraph.

This function 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 an edge with source `i`

and range `j`

in `digraph`.

The function `OutNeighbours`

returns an immutable list of immutable lists, whereas the function `OutNeighboursMutableCopy`

returns a copy of `OutNeighbours`

which is a mutable list of mutable lists.

gap> gr := Digraph(["a", "b", "c"], > ["a", "b", "b"], > ["b", "a", "c"]); <digraph with 3 vertices, 3 edges> gap> OutNeighbours(gr); [ [ 2 ], [ 1, 3 ], [ ] ] gap> gr := Digraph([[1, 2, 3], [2, 1], [3]]); <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]]); <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 ] ]

`‣ InNeighbours` ( digraph ) | ( attribute ) |

`‣ InNeighbors` ( digraph ) | ( attribute ) |

`‣ InNeighboursMutableCopy` ( digraph ) | ( operation ) |

`‣ InNeighborsMutableCopy` ( digraph ) | ( operation ) |

Returns: A list of lists of vertices.

This function 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 with source `j`

and range `i`

in `digraph`.

The function `InNeighbours`

returns an immutable list of immutable lists, whereas the function `InNeighboursMutableCopy`

returns a copy of `InNeighbours`

which is a mutable list of mutable lists.

Note that each entry of `inn`

is sorted into ascending order.

gap> gr := Digraph(["a", "b", "c"], > ["a", "b", "b"], > ["b", "a", "c"]); <digraph with 3 vertices, 3 edges> gap> InNeighbours(gr); [ [ 2 ], [ 1 ], [ 2 ] ] gap> gr := Digraph([[1, 2, 3], [2, 1], [3]]); <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]]); <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 ] ]

`‣ OutDegrees` ( digraph ) | ( attribute ) |

`‣ OutDegreeSequence` ( digraph ) | ( attribute ) |

`‣ OutDegreeSet` ( digraph ) | ( attribute ) |

Returns: A list of non-negative integers.

Given a digraph `digraph` with n vertices, the function `OutDegrees`

returns a 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-9).

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> gr := Digraph([[1, 3, 2, 2], [], [2, 1], []]); <multidigraph with 4 vertices, 6 edges> gap> OutDegrees(gr); [ 4, 0, 2, 0 ] gap> OutDegreeSequence(gr); [ 4, 2, 0, 0 ] gap> OutDegreeSet(gr); [ 0, 2, 4 ]

`‣ InDegrees` ( digraph ) | ( attribute ) |

`‣ InDegreeSequence` ( digraph ) | ( attribute ) |

`‣ InDegreeSet` ( digraph ) | ( attribute ) |

Returns: A list of non-negative integers.

Given a digraph `digraph` with n vertices, the function `InDegrees`

returns a 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-11).

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> gr := Digraph([[1, 3, 2, 2, 4], [], [2, 1, 4], []]); <multidigraph with 4 vertices, 8 edges> gap> InDegrees(gr); [ 2, 3, 1, 2 ] gap> InDegreeSequence(gr); [ 3, 2, 2, 1 ] gap> InDegreeSet(gr); [ 1, 2, 3 ]

`‣ OutDegreeOfVertex` ( digraph, vertex ) | ( operation ) |

Returns: The non-negative integer.

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> gr := Digraph([ > [2, 2, 1], [1, 4], [2, 2, 4, 2], [1, 1, 2, 2, 1, 2, 2]]); <multidigraph with 4 vertices, 16 edges> gap> OutDegreeOfVertex(gr, 1); 3 gap> OutDegreeOfVertex(gr, 2); 2 gap> OutDegreeOfVertex(gr, 3); 4 gap> OutDegreeOfVertex(gr, 4); 7

`‣ OutNeighboursOfVertex` ( digraph, vertex ) | ( operation ) |

`‣ OutNeighborsOfVertex` ( digraph, vertex ) | ( operation ) |

Returns: A list of vertices.

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> gr := Digraph([ > [2, 2, 3], [1, 3, 4], [2, 2, 3], [1, 1, 2, 2, 1, 2, 2]]); <multidigraph with 4 vertices, 16 edges> gap> OutNeighboursOfVertex(gr, 1); [ 2, 2, 3 ] gap> OutNeighboursOfVertex(gr, 3); [ 2, 2, 3 ]

`‣ InDegreeOfVertex` ( digraph, vertex ) | ( operation ) |

Returns: A non-negative integer.

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> gr := Digraph([ > [2, 2, 1], [1, 4], [2, 2, 4, 2], [1, 1, 2, 2, 1, 2, 2]]); <multidigraph with 4 vertices, 16 edges> gap> InDegreeOfVertex(gr, 1); 5 gap> InDegreeOfVertex(gr, 2); 9 gap> InDegreeOfVertex(gr, 3); 0 gap> InDegreeOfVertex(gr, 4); 2

`‣ InNeighboursOfVertex` ( digraph, vertex ) | ( operation ) |

`‣ InNeighborsOfVertex` ( digraph, vertex ) | ( operation ) |

Returns: A list of postitive vertices.

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> gr := Digraph([ > [2, 2, 3], [1, 3, 4], [2, 2, 3], [1, 1, 2, 2, 1, 2, 2]]); <multidigraph with 4 vertices, 16 edges> gap> InNeighboursOfVertex(gr, 1); [ 2, 4, 4, 4 ] gap> InNeighboursOfVertex(gr, 2); [ 1, 1, 3, 3, 4, 4, 4, 4 ]

`‣ DigraphLoops` ( digraph ) | ( attribute ) |

Returns: A list of vertices.

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

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

`‣ PartialOrderDigraphMeetOfVertices` ( digraph, u, v ) | ( operation ) |

`‣ PartialOrderDigraphJoinOfVertices` ( digraph, u, v ) | ( operation ) |

Returns: A positive integer or `fail`

If the first argument is a partial order digraph `IsPartialOrderDigraph`

(6.1-14) 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.1-15) (or `IsJoinSemilatticeDigraph`

(6.1-15)) - see the documentation for these properties for the definition of the meet (or the join).

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

`‣ DigraphDiameter` ( digraph ) | ( attribute ) |

Returns: An integer or `fail`

.

This function returns the diameter of the digraph `digraph`.

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`

.

See `DigraphShortestDistances`

(5.3-3).

gap> gr := Digraph([[2], [3], [4, 5], [5], [1, 2, 3, 4, 5]]); <digraph with 5 vertices, 10 edges> gap> DigraphDiameter(gr); 3 gap> gr := ChainDigraph(2); <digraph with 2 vertices, 1 edge> gap> DigraphDiameter(gr); fail gap> IsStronglyConnectedDigraph(gr); false

`‣ DigraphShortestDistance` ( digraph, u, v ) | ( operation ) |

`‣ DigraphShortestDistance` ( digraph, list ) | ( operation ) |

`‣ DigraphShortestDistance` ( digraph, list1, list2 ) | ( operation ) |

Returns: An integer or `fail`

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

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

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> gr := Digraph([[2], [3], [1, 4], [1, 3], [5]]); <digraph with 5 vertices, 7 edges> gap> DigraphShortestDistance(gr, 1, 3); 2 gap> DigraphShortestDistance(gr, [3, 3]); 0 gap> DigraphShortestDistance(gr, 5, 2); fail gap> DigraphShortestDistance(gr, [1, 2], [4, 5]); 2 gap> DigraphShortestDistance(gr, [1, 3], [3, 5]); 0

`‣ DigraphShortestDistances` ( digraph ) | ( attribute ) |

Returns: A square matrix.

If `digraph` is a digraph with n vertices, then this function returns an n × 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> gr := Digraph([[1, 2], [3], [1, 2], [4]]); <digraph with 4 vertices, 6 edges> gap> mat := DigraphShortestDistances(gr);; gap> PrintArray(mat); [ [ 0, 1, 2, fail ], [ 2, 0, 1, fail ], [ 1, 1, 0, fail ], [ fail, fail, fail, 0 ] ]

`‣ DigraphLongestDistanceFromVertex` ( digraph, v ) | ( operation ) |

Returns: An integer, or `infinity`

.

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.

If there exists a directed walk starting at vertex

`v`which traverses a loop or a directed cycle, then we consider there to be a walk of infinite length from`v`(realised by repeatedly traversing the loop/directed cycle), and so the result is`infinity`

. To disallow walks using loops, try using`DigraphRemoveLoops`

(3.3-22):`DigraphLongestDistanceFromVertex(DigraphRemoveLoops(`

.`digraph`,`v`))Otherwise, if all directed walks starting at vertex

`v`have finite length, then the length of the longest such walk is returned.

Note that the result is `0`

if and only if `v` is a sink of `digraph`. See `DigraphSinks`

(5.1-5).

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

`‣ DigraphDistanceSet` ( digraph, vertex, distance ) | ( operation ) |

`‣ DigraphDistanceSet` ( digraph, vertex, distances ) | ( operation ) |

Returns: A list of vertices

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> gr := Digraph([[2], [3], [1, 4], [1, 3]]); <digraph with 4 vertices, 6 edges> gap> DigraphDistanceSet(gr, 2, [1, 2]); [ 3, 1, 4 ] gap> DigraphDistanceSet(gr, 3, 1); [ 1, 4 ] gap> DigraphDistanceSet(gr, 2, 0); [ 2 ]

`‣ DigraphGirth` ( digraph ) | ( attribute ) |

Returns: An integer, or `infinity`

.

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

, where `n` ^ 3)`n` is the number of vertices in `digraph`. If the digraph has known automorphisms [see `DigraphGroup`

(7.2-9)], then the performance is likely to be better.

For symmetric digraphs, see also `DigraphUndirectedGirth`

(5.3-7).

gap> gr := Digraph([[1], [1]]); <digraph with 2 vertices, 2 edges> gap> DigraphGirth(gr); 1 gap> gr := Digraph([[2, 3], [3], [4], []]); <digraph with 4 vertices, 4 edges> gap> DigraphGirth(gr); infinity gap> gr := Digraph([[2, 3], [3], [4], [1]]); <digraph with 4 vertices, 5 edges> gap> DigraphGirth(gr); 3

`‣ DigraphUndirectedGirth` ( digraph ) | ( attribute ) |

Returns: An integer or `infinity`

.

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.

If `digraph` has no cycles, then this function will return `infinity`

.

gap> gr := Digraph([[2, 4], [1, 3], [2, 4], [1, 3]]); <digraph with 4 vertices, 8 edges> gap> DigraphUndirectedGirth(gr); 4 gap> gr := Digraph([[2], [1, 3], [2]]); <digraph with 3 vertices, 4 edges> gap> DigraphUndirectedGirth(gr); infinity gap> gr := Digraph([[1], [], [4], [3]]); <digraph with 4 vertices, 3 edges> gap> DigraphUndirectedGirth(gr); 1

`‣ DigraphConnectedComponents` ( digraph ) | ( attribute ) |

Returns: A record.

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.3-10)) of the `DigraphSymmetricClosure`

(3.3-9) 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.

gap> gr := Digraph([[2], [3, 1], []]); <digraph with 3 vertices, 3 edges> gap> DigraphConnectedComponents(gr); rec( comps := [ [ 1, 2, 3 ] ], id := [ 1, 1, 1 ] ) gap> gr := Digraph([[1], [1, 2], []]); <digraph with 3 vertices, 3 edges> gap> DigraphConnectedComponents(gr); rec( comps := [ [ 1, 2 ], [ 3 ] ], id := [ 1, 1, 2 ] ) gap> gr := EmptyDigraph(0); <digraph with 0 vertices, 0 edges> gap> DigraphConnectedComponents(gr); rec( comps := [ ], id := [ ] )

`‣ DigraphConnectedComponent` ( digraph, vertex ) | ( operation ) |

Returns: A list of vertices.

If `vertex` is a vertex in the digraph `digraph`, then this operation returns the connected component of `vertex` in `digraph`. See `DigraphConnectedComponents`

(5.3-8) for more information.

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

`‣ DigraphStronglyConnectedComponents` ( digraph ) | ( attribute ) |

Returns: A record.

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.

gap> gr := Digraph([[2], [3, 1], []]); <digraph with 3 vertices, 3 edges> gap> DigraphStronglyConnectedComponents(gr); rec( comps := [ [ 3 ], [ 1, 2 ] ], id := [ 2, 2, 1 ] )

`‣ DigraphStronglyConnectedComponent` ( digraph, vertex ) | ( operation ) |

Returns: A list of vertices.

If `vertex` is a vertex in the digraph `digraph`, then this operation returns the strongly connected component of `vertex` in `digraph`. See `DigraphStronglyConnectedComponents`

(5.3-10) for more information.

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

`‣ DigraphBicomponents` ( digraph ) | ( attribute ) |

Returns: A pair of lists of vertices, or `fail`

.

If `digraph` is a bipartite digraph, i.e. if it satisfies `IsBipartiteDigraph`

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

gap> gr := CycleDigraph(3); <digraph with 3 vertices, 3 edges> gap> DigraphBicomponents(gr); fail gap> gr := ChainDigraph(5); <digraph with 5 vertices, 4 edges> gap> DigraphBicomponents(gr); [ [ 1, 3, 5 ], [ 2, 4 ] ] gap> gr := Digraph([[5], [1, 4], [5], [5], []]); <digraph with 5 vertices, 5 edges> gap> DigraphBicomponents(gr); [ [ 1, 3, 4 ], [ 2, 5 ] ]

`‣ ArticulationPoints` ( digraph ) | ( attribute ) |

Returns: A list of vertices.

A connected digraph is *biconnected* if it is still connected (in the sense of `IsConnectedDigraph`

(6.3-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.

Multiple edges and loops are ignored by this method.

The method used in this operation has complexity O(m+n) where m is the number of edges (counting multiple edges as one, and not counting loops) and n is the number of vertices in the digraph. See also `IsBiconnectedDigraph`

(6.3-4).

gap> ArticulationPoints(CycleDigraph(5)); [ ] gap> digraph := Digraph([[2, 7], [3, 5], [4], [2], [6], [1], []]);; gap> ArticulationPoints(digraph); [ 2, 1 ] gap> ArticulationPoints(ChainDigraph(5)); [ 4, 3, 2 ] gap> ArticulationPoints(NullDigraph(5)); [ ]

`‣ DigraphPeriod` ( digraph ) | ( attribute ) |

Returns: An integer.

This function returns the period of the digraph `digraph`.

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.3-6).

gap> gr := Digraph([[6], [1], [2], [3], [4, 4], [5]]); <multidigraph with 6 vertices, 7 edges> gap> DigraphPeriod(gr); 6 gap> gr := Digraph([[2], [3, 5], [4], [5], [1, 2]]); <digraph with 5 vertices, 7 edges> gap> DigraphPeriod(gr); 1 gap> gr := ChainDigraph(2); <digraph with 2 vertices, 1 edge> gap> DigraphPeriod(gr); 0 gap> IsAcyclicDigraph(gr); true

`‣ DigraphFloydWarshall` ( digraph, func, nopath, edge ) | ( operation ) |

Returns: A matrix.

If `digraph` is a digraph with n vertices, then this operation returns an n × 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 postive 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> gr := DigraphFromDigraph6String("+ECGOElR"); <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(gr, 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 ] ]

`‣ IsReachable` ( digraph, u, v ) | ( operation ) |

Returns: `true`

or `false`

.

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> gr := Digraph([[2], [3], [2, 3]]); <digraph with 3 vertices, 4 edges> gap> IsReachable(gr, 1, 3); true gap> IsReachable(gr, 2, 1); false gap> IsReachable(gr, 3, 3); true gap> IsReachable(gr, 1, 1); false

`‣ DigraphPath` ( digraph, u, v ) | ( operation ) |

Returns: A pair of lists, or `fail`

.

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:

`v`

is the list [v_1, v_2, ..., v_n].`a`

is the list of positive integers [a_1, a_2, ..., a_n-1] where for each each i < n, a_i is the position of v_i+1 in`OutNeighboursOfVertex(`

`digraph``,`

v_i`)`

corresponding to the edge e_i. This is can be useful if the position of a vertex in a list of out-neighours is significant, for example in orbit digraphs.

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> gr := Digraph([[2], [3], [2, 3]]); <digraph with 3 vertices, 4 edges> gap> DigraphPath(gr, 1, 3); [ [ 1, 2, 3 ], [ 1, 1 ] ] gap> DigraphPath(gr, 2, 1); fail gap> DigraphPath(gr, 3, 3); [ [ 3, 3 ], [ 2 ] ] gap> DigraphPath(gr, 1, 1); fail

`‣ IteratorOfPaths` ( digraph, u, v ) | ( operation ) |

Returns: An iterator.

If `digraph` is a digraph or a list of adjacencies which defines a digraph - see `OutNeighbours`

(5.2-5) - 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.3-17) for more information about the repesentation 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> gr := Digraph([[1, 4, 4, 2], [3, 5], [2, 3], [1, 2], [4]]); <multidigraph with 5 vertices, 11 edges> gap> iter := IteratorOfPaths(gr, 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(gr, 4, 3); <iterator> gap> NextIterator(iter); [ [ 4, 1, 2, 3 ], [ 1, 4, 1 ] ]

`‣ DigraphAllSimpleCircuits` ( digraph ) | ( attribute ) |

Returns: A list of lists of vertices.

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, ..., v_n], or any cyclic permutation thereof. For each simple circuit of `digraph`, `DigraphAllSimpleCircuits(`

includes precisely one such list to represent the circuit.`digraph`)

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

`‣ DigraphLongestSimpleCircuit` ( digraph ) | ( attribute ) |

Returns: A list of vertices, or `fail`

.

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.3-19).

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> gr := Digraph([[], [3], [2, 4], [5, 4], [4]]);; gap> DigraphLongestSimpleCircuit(gr); [ 4, 5 ] gap> gr := ChainDigraph(10);; gap> DigraphLongestSimpleCircuit(gr); fail gap> gr := Digraph([[3], [1], [1, 4], [1, 1]]);; gap> DigraphLongestSimpleCircuit(gr); [ 1, 3, 4 ]

`‣ DigraphLayers` ( digraph, vertex ) | ( operation ) |

Returns: A list.

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> gr := CompleteDigraph(4);; gap> DigraphLayers(gr, 1); [ [ 1 ], [ 2, 3, 4 ] ]

`‣ DigraphDegeneracy` ( digraph ) | ( attribute ) |

Returns: A non-negative integer, or `fail`

.

If `digraph` is a symmetric digraph without multiple edges - see `IsSymmetricDigraph`

(6.1-10) and `IsMultiDigraph`

(6.1-8) - 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> gr := DigraphSymmetricClosure(ChainDigraph(5));; gap> DigraphDegeneracy(gr); 1 gap> gr := CompleteDigraph(5);; gap> DigraphDegeneracy(gr); 4 gap> gr := Digraph([[1], [2, 4, 5], [3, 4], [2, 3, 4], [2], []]); <digraph with 6 vertices, 10 edges> gap> DigraphDegeneracy(gr); 1

`‣ DigraphDegeneracyOrdering` ( digraph ) | ( attribute ) |

Returns: A list of integers, or `fail`

.

If `digraph` is a digraph for which `DigraphDegeneracy(`

`digraph``)`

is a non-negative integer `k`

- see `DigraphDegeneracy`

(5.3-22) - 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> gr := DigraphSymmetricClosure(ChainDigraph(5));; gap> DigraphDegeneracyOrdering(gr); [ 5, 4, 3, 2, 1 ] gap> gr := CompleteDigraph(5);; gap> DigraphDegeneracyOrdering(gr); [ 5, 4, 3, 2, 1 ] gap> gr := Digraph([[1], [2, 4, 5], [3, 4], [2, 3, 4], [2], []]); <digraph with 6 vertices, 10 edges> gap> DigraphDegeneracyOrdering(gr); [ 1, 6, 5, 2, 4, 3 ]

`‣ HamiltonianPath` ( digraph ) | ( attribute ) |

Returns: A list or `fail`

.

Returns a Hamiltonian path if one exists, `fail`

if not.

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.3-19). 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> g := Digraph([[]]); <digraph with 1 vertex, 0 edges> gap> HamiltonianPath(g); [ 1 ] gap> g := Digraph([[2], [1]]); <digraph with 2 vertices, 2 edges> gap> HamiltonianPath(g); [ 1, 2 ] gap> g := Digraph([[3], [], [2]]); <digraph with 3 vertices, 2 edges> gap> HamiltonianPath(g); fail gap> g := Digraph([[2], [3], [1]]); <digraph with 3 vertices, 3 edges> gap> HamiltonianPath(g); [ 1, 2, 3 ]

`‣ GroupOfCayleyDigraph` ( digraph ) | ( attribute ) |

`‣ SemigroupOfCayleyDigraph` ( digraph ) | ( attribute ) |

Returns: A group or semigroup.

If `digraph` is a Cayley graph of a group `G`

and `digraph` belongs to the category `IsCayleyDigraph`

(3.1-2), then `GroupOfCayleyDigraph`

returns `G`

.

If `digraph` is a Cayley graph of a semigroup `S`

and `digraph` belongs to the category `IsCayleyDigraph`

(3.1-2), then `SemigroupOfCayleyDigraph`

returns `S`

.

See also `GeneratorsOfCayleyDigraph`

(5.4-2).

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

`‣ GeneratorsOfCayleyDigraph` ( digraph ) | ( attribute ) |

Returns: A list of generators.

If `digraph` is a Cayley graph of a group or semigroup with respect to a set of generators `gens`

and `digraph` belongs to the category `IsCayleyDigraph`

(3.1-2), then `GeneratorsOfCayleyDigraph`

return the list of generators `gens`

over which `digraph` is defined.

See also `GroupOfCayleyDigraph`

(5.4-1) or `SemigroupOfCayleyDigraph`

(5.4-1).

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

generated by GAPDoc2HTML