3 Creating digraphs

3.3 New digraphs from old

3.3-1 DigraphCopy

3.3-2 InducedSubdigraph

3.3-3 ReducedDigraph

3.3-4 MaximalSymmetricSubdigraph

3.3-5 UndirectedSpanningTree

3.3-6 QuotientDigraph

3.3-7 DigraphReverse

3.3-8 DigraphDual

3.3-9 DigraphSymmetricClosure

3.3-10 DigraphReflexiveTransitiveClosure

3.3-11 DigraphReflexiveTransitiveReduction

3.3-12 DigraphAddVertex

3.3-13 DigraphAddVertices

3.3-14 DigraphAddEdge

3.3-15 DigraphAddEdgeOrbit

3.3-16 DigraphAddEdges

3.3-17 DigraphRemoveVertex

3.3-18 DigraphRemoveVertices

3.3-19 DigraphRemoveEdge

3.3-20 DigraphRemoveEdgeOrbit

3.3-21 DigraphRemoveEdges

3.3-22 DigraphRemoveLoops

3.3-23 DigraphRemoveAllMultipleEdges

3.3-24 DigraphReverseEdges

3.3-25 DigraphDisjointUnion

3.3-26 DigraphEdgeUnion

3.3-27 DigraphJoin

3.3-28 LineDigraph

3.3-29 LineUndirectedDigraph

3.3-30 DoubleDigraph

3.3-31 BipartiteDoubleDigraph

3.3-32 DigraphAddAllLoops

3.3-33 DistanceDigraph

3.3-34 DigraphClosure

3.3-1 DigraphCopy

3.3-2 InducedSubdigraph

3.3-3 ReducedDigraph

3.3-4 MaximalSymmetricSubdigraph

3.3-5 UndirectedSpanningTree

3.3-6 QuotientDigraph

3.3-7 DigraphReverse

3.3-8 DigraphDual

3.3-9 DigraphSymmetricClosure

3.3-10 DigraphReflexiveTransitiveClosure

3.3-11 DigraphReflexiveTransitiveReduction

3.3-12 DigraphAddVertex

3.3-13 DigraphAddVertices

3.3-14 DigraphAddEdge

3.3-15 DigraphAddEdgeOrbit

3.3-16 DigraphAddEdges

3.3-17 DigraphRemoveVertex

3.3-18 DigraphRemoveVertices

3.3-19 DigraphRemoveEdge

3.3-20 DigraphRemoveEdgeOrbit

3.3-21 DigraphRemoveEdges

3.3-22 DigraphRemoveLoops

3.3-23 DigraphRemoveAllMultipleEdges

3.3-24 DigraphReverseEdges

3.3-25 DigraphDisjointUnion

3.3-26 DigraphEdgeUnion

3.3-27 DigraphJoin

3.3-28 LineDigraph

3.3-29 LineUndirectedDigraph

3.3-30 DoubleDigraph

3.3-31 BipartiteDoubleDigraph

3.3-32 DigraphAddAllLoops

3.3-33 DistanceDigraph

3.3-34 DigraphClosure

In this chapter we describe how to create digraphs.

`‣ IsDigraph` | ( category ) |

Every digraph in **Digraphs** belongs to the category `IsDigraph`

. Basic attributes and operations for digraphs are: `DigraphVertices`

(5.1-1), `DigraphRange`

(5.2-4), `DigraphSource`

(5.2-4), `OutNeighbours`

(5.2-5), and `DigraphEdges`

(5.1-3).

`‣ IsCayleyDigraph` | ( category ) |

`IsCayleyDigraph`

is a subcategory of `IsDigraph`

. Digraphs that are Cayley digraphs of a group and that are constructed by the operation `CayleyDigraph`

(3.1-10) are constructed in this category.

`‣ IsDigraphWithAdjacencyFunction` | ( category ) |

`IsDigraphWithAdjacencyFunction`

is a subcategory of `IsDigraph`

. Digraphs that are *created* using an adjacency function are constructed in this category.

`‣ DigraphType` | ( global variable ) |

`‣ DigraphFamily` | ( family ) |

The type of all digraphs is `DigraphType`

. The family of all digraphs is `DigraphFamily`

.

`‣ Digraph` ( obj[, source, range] ) | ( operation ) |

`‣ Digraph` ( list, func ) | ( operation ) |

`‣ Digraph` ( G, list, act, adj ) | ( operation ) |

Returns: A digraph.

**for a list (i.e. an adjacency list)**if

`obj`is a list of lists of positive integers in the range from`1`

to`Length(`

, then this function returns the digraph with vertices \(E ^ 0 = \)`obj`)`[1 .. Length(`

, and edges corresponding to the entries of`obj`)]`obj`.More precisely, there is an edge from vertex

`i`

to`j`

if and only if`j`

is in

; the source of this edge is`obj`[i]`i`

and the range is`j`

. If`j`

occurs in

with multiplicity`obj`[i]`k`

, then there are`k`

edges from`i`

to`j`

.**for three lists**if

`obj`is a duplicate-free list, and`source`and`range`are lists of equal length consisting of positive integers in the list`[1 .. Length(`

, then this function returns a digraph with vertices \(E ^ 0 = \)`obj`)]`[1 .. Length(`

, and`obj`)]`Length(`

edges. For each`source`)`i`

in`[1 .. Length(`

there exists an edge with source vertex`source`)]`source[i]`

and range vertex`range[i]`

. See`DigraphSource`

(5.2-4) and`DigraphRange`

(5.2-4).The vertices of the digraph will be labelled by the elements of

`obj`.**for an integer, and two lists**if

`obj`is an integer, and`source`and`range`are lists of equal length consisting of positive integers in the list`[1 ..`

, then this function returns a digraph with vertices \(E ^ 0 = \)`obj`]`[1 ..`

, and`obj`]`Length(`

edges. For each`source`)`i`

in`[1 .. Length(`

there exists an edge with source vertex`source`)]`source[i]`

and range vertex`range[i]`

. See`DigraphSource`

(5.2-4) and`DigraphRange`

(5.2-4).**for a list and a function**if

`list`is a list and`func`is a function taking 2 arguments that are elements of`list`, and`func`returns`true`

or`false`

, then this operation creates a digraph with vertices`[1 .. Length(`

and an edge from vertex`list`)]`i`

to vertex`j`

if and only if

returns`func`(`list`[i],`list`[j])`true`

.**for a group, a list, and two functions**The arguments will be

`G, list, act, adj`.Let

`G`be a group acting on the objects in`list`via the action`act`, and let`adj`be a function taking two objects from`list`as arguments and returning`true`

or`false`

. The function`adj`will describe the adjacency between objects from`list`, which is invariant under the action of`G`. This variant of the constructor returns a digraph with vertices the objects of`list`and directed edges`[x, y]`

when`f(x, y)`

is`true`

.The action of the group

`G`on the objects in`list`is stored in the attribute`DigraphGroup`

(7.2-9), and is used to speed up operations like`DigraphDiameter`

(5.3-1).**for a Grape package graph**if

`obj`is a Grape package graph (i.e. a record for which the function`IsGraph`

returns`true`

), then this function returns a digraph isomorphic to`obj`.**for a binary relation**if

`obj`is a binary relation on the points`[1 .. n]`

for some posititve integer \(n\), then this function returns the digraph defined by`obj`. Specifically, this function returns a digraph which has \(n\) vertices, and which has an edge with source`i`

and range`j`

if and only if`[i,j]`

is a pair in the binary relation`obj`.

gap> gr := Digraph([ > [2, 5, 8, 10], [2, 3, 4, 2, 5, 6, 8, 9, 10], [1], > [3, 5, 7, 8, 10], [2, 5, 7], [3, 6, 7, 9, 10], [1, 4], > [1, 5, 9], [1, 2, 7, 8], [3, 5]]); <multidigraph with 10 vertices, 38 edges> gap> gr := Digraph(["a", "b", "c"], ["a"], ["b"]); <digraph with 3 vertices, 1 edge> gap> gr := Digraph(5, [1, 2, 2, 4, 1, 1], [2, 3, 5, 5, 1, 1]); <multidigraph with 5 vertices, 6 edges> gap> Petersen := Graph(SymmetricGroup(5), [[1, 2]], OnSets, > function(x, y) return Intersection(x, y) = []; end);; gap> Digraph(Petersen); <digraph with 10 vertices, 30 edges> gap> b := BinaryRelationOnPoints( > [[3], [1, 3, 5], [1], [1, 2, 4], [2, 3, 5]]); Binary Relation on 5 points gap> gr := Digraph(b); <digraph with 5 vertices, 11 edges> gap> gr := Digraph([1 .. 10], ReturnTrue); <digraph with 10 vertices, 100 edges>

The next example illustrates the uses of the fourth and fifth variants of this constructor. The resulting digraph is a strongly regular graph, and it is actually the point graph of the van Lint-Schrijver partial geometry, [vLS81]. The algebraic description is taken from the seminal paper of Calderbank and Kantor [CK86].

gap> f := GF(3 ^ 4); GF(3^4) gap> gamma := First(f, x -> Order(x) = 5); Z(3^4)^64 gap> L := Union([Zero(f)], List(Group(gamma))); [ 0*Z(3), Z(3)^0, Z(3^4)^16, Z(3^4)^32, Z(3^4)^48, Z(3^4)^64 ] gap> omega := Union(List(L, x -> List(Difference(L, [x]), y -> x - y))); [ Z(3)^0, Z(3), Z(3^4)^5, Z(3^4)^7, Z(3^4)^8, Z(3^4)^13, Z(3^4)^15, Z(3^4)^16, Z(3^4)^21, Z(3^4)^23, Z(3^4)^24, Z(3^4)^29, Z(3^4)^31, Z(3^4)^32, Z(3^4)^37, Z(3^4)^39, Z(3^4)^45, Z(3^4)^47, Z(3^4)^48, Z(3^4)^53, Z(3^4)^55, Z(3^4)^56, Z(3^4)^61, Z(3^4)^63, Z(3^4)^64, Z(3^4)^69, Z(3^4)^71, Z(3^4)^72, Z(3^4)^77, Z(3^4)^79 ] gap> adj := function(x, y) > return x - y in omega; > end; function( x, y ) ... end gap> digraph := Digraph(AsList(f), adj); <digraph with 81 vertices, 2430 edges> gap> group := Group(Z(3)); <group with 1 generators> gap> act := \*; <Operation "*"> gap> digraph := Digraph(group, List(f), act, adj); <digraph with 81 vertices, 2430 edges>

`‣ DigraphByAdjacencyMatrix` ( adj ) | ( operation ) |

Returns: A digraph.

If `adj` is the adjacency matrix of a digraph in the sense of `AdjacencyMatrix`

(5.2-1), then this operation returns the digraph which is defined by `adj`.

Alternatively, if `adj` is a square boolean matrix, then this operation returns the digraph with `Length(`

`adj``)`

vertices which has the edge `[i,j]`

if and only if `adj``[i][j]`

is `true`

.

gap> DigraphByAdjacencyMatrix([ > [0, 1, 0, 2, 0], > [1, 1, 1, 0, 1], > [0, 3, 2, 1, 1], > [0, 0, 1, 0, 1], > [2, 0, 0, 0, 0]]); <multidigraph with 5 vertices, 18 edges> gap> gr := DigraphByAdjacencyMatrix([ > [true, false, true], > [false, false, true], > [false, true, false]]); <digraph with 3 vertices, 4 edges> gap> OutNeighbours(gr); [ [ 1, 3 ], [ 3 ], [ 2 ] ]

`‣ DigraphByEdges` ( edges[, n] ) | ( operation ) |

Returns: A digraph.

If `edges` is list of pairs of positive integers, then this function returns the digraph with the minimum number of vertices `m`

such that its edges equal `edges`.

If the optional second argument `n` is a positive integer with

(with `n` >= m`m`

defined as above), then this function returns the digraph with `n` vertices and edges `edges`.

See `DigraphEdges`

(5.1-3).

gap> DigraphByEdges( > [[1, 3], [2, 1], [2, 3], [2, 5], [3, 6], > [4, 6], [5, 2], [5, 4], [5, 6], [6, 6]]); <digraph with 6 vertices, 10 edges> gap> DigraphByEdges( > [[1, 3], [2, 1], [2, 3], [2, 5], [3, 6], > [4, 6], [5, 2], [5, 4], [5, 6], [6, 6]], 12); <digraph with 12 vertices, 10 edges>

`‣ EdgeOrbitsDigraph` ( G, edges[, n] ) | ( operation ) |

Returns: A new digraph.

If `G` is a permutation group, `edges` is an edge or list of edges, and `n` is a non-negative integer such that `G` fixes `[1 .. `

setwise, then this operation returns a new digraph with `n`]`n` vertices and the union of the orbits of the edges in ` edges ` under the action of the permutation group `G`. An edge in this context is simply a pair of positive integers.

If the optional third argument `n` is not present, then the largest moved point of the permutation group `G` is used by default.

gap> digraph := EdgeOrbitsDigraph(Group((1, 3), (1, 2)(3, 4)), > [[1, 2], [4, 5]], 5); <digraph with 5 vertices, 12 edges> gap> OutNeighbours(digraph); [ [ 2, 4, 5 ], [ 1, 3, 5 ], [ 2, 4, 5 ], [ 1, 3, 5 ], [ ] ] gap> RepresentativeOutNeighbours(digraph); [ [ 2, 4, 5 ], [ ] ]

`‣ DigraphByInNeighbours` ( in ) | ( operation ) |

`‣ DigraphByInNeighbors` ( in ) | ( operation ) |

Returns: A digraph.

If `in` is a list of lists of positive integers in the range `[1 .. Length(`

, then this function returns the digraph with vertices \(E^0=\)`in`)]`[1 .. Length(`

, and edges corresponding to the entries of `in`)]`in`. More precisely, there is an edge with source vertex `i`

and range vertex `j`

if `i`

is in

.`in`[j]

If `i`

occurs in

with multiplicity `in`[j]`k`

, then there are `k`

multiple edges from `i`

to `j`

.

See `InNeighbours`

(5.2-6).

gap> gr := DigraphByInNeighbours([ > [2, 5, 8, 10], [2, 3, 4, 5, 6, 8, 9, 10], > [1], [3, 5, 7, 8, 10], [2, 5, 7], [3, 6, 7, 9, 10], [1, 4], > [1, 5, 9], [1, 2, 7, 8], [3, 5]]); <digraph with 10 vertices, 37 edges> gap> gr := DigraphByInNeighbours([[2, 3, 2], [1], [1, 2, 3]]); <multidigraph with 3 vertices, 7 edges>

`‣ CayleyDigraph` ( G[, gens] ) | ( operation ) |

Returns: A digraph.

Let `G` be any group and let `gens` be a list of elements of `G`. This function returns the Cayley graph of the group with respect `gens`. The vertices are the elements of `G`. There exists an edge from the vertex `u`

to the vertex `v`

if and only if there exists a generator `g`

in `gens` such that `x * g = y`

.

If the optional second argument `gens` is not present, then the generators of `G` are used by default. The digraph created by this operation belongs to the category `IsCayleyDigraph`

(3.1-2), the group `G` can be recovered from the digraph using `GroupOfCayleyDigraph`

(5.4-1), and the generators `gens` can be obtained using `GeneratorsOfCayleyDigraph`

(5.4-2).

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

`‣ AsBinaryRelation` ( digraph ) | ( operation ) |

Returns: A binary relation.

If `digraph` is a digraph with a positive number of vertices \(n\), and no multiple edges, then this operation returns a binary relation on the points `[1..n]`

. The pair `[i,j]`

is in the binary relation if and only if `[i,j]`

is an edge in `digraph`.

gap> gr := Digraph([[3, 2], [1, 2], [2], [3, 4]]); <digraph with 4 vertices, 7 edges> gap> AsBinaryRelation(gr); Binary Relation on 4 points

`‣ AsDigraph` ( trans[, n] ) | ( operation ) |

Returns: A digraph, or `fail`

.

If `trans` is a transformation, and `n` is a non-negative integer such that the restriction of `trans` to `[1 .. `

defines a transformation of `n`]`[1 .. `

, then `n`]`AsDigraph`

returns the functional digraph with `n` vertices defined by `trans`. See `IsFunctionalDigraph`

(6.1-7).

Specifically, the digraph returned by `AsDigraph`

has `n` edges: for each vertex `x`

in `[1 .. `

, there is a unique edge with source `n`]`x`

; this edge has range `x^`

.`trans`

If the optional second argument `n` is not supplied, then the degree of the transformation `trans` is used by default. If the restriction of `trans` to `[1 .. `

does not define a transformation of `n`]`[1 .. `

, then `n`]`AsDigraph(`

returns `trans`, `n`)`fail`

.

gap> f := Transformation([4, 3, 3, 1, 7, 9, 10, 4, 2, 3]); Transformation( [ 4, 3, 3, 1, 7, 9, 10, 4, 2, 3 ] ) gap> AsDigraph(f); <digraph with 10 vertices, 10 edges> gap> AsDigraph(f, 4); <digraph with 4 vertices, 4 edges> gap> AsDigraph(f, 5); fail

`‣ Graph` ( digraph ) | ( operation ) |

Returns: A Grape package graph.

If `digraph` is a digraph without multiple edges, then this operation returns a Grape package graph that is isomorphic to `digraph`.

If `digraph` is a multidigraph, then since Grape does not support multiple edges, the multiple edges will be reduced to a single edge in the result. In order words, for a multidigraph this operation will return the same as `Graph(DigraphRemoveAllMultipleEdges(`

`digraph``))`

.

gap> Petersen := Graph(SymmetricGroup(5), [[1, 2]], OnSets, > function(x, y) return Intersection(x, y) = []; end); rec( adjacencies := [ [ 3, 5, 8 ] ], group := Group([ (1,2,3,5,7) (4,6,8,9,10), (2,4)(6,9)(7,10) ]), isGraph := true, names := [ [ 1, 2 ], [ 2, 3 ], [ 3, 4 ], [ 1, 3 ], [ 4, 5 ], [ 2, 4 ], [ 1, 5 ], [ 3, 5 ], [ 1, 4 ], [ 2, 5 ] ], order := 10, representatives := [ 1 ], schreierVector := [ -1, 1, 1, 2, 1, 1, 1, 1, 2, 2 ] ) gap> Digraph(Petersen); <digraph with 10 vertices, 30 edges> gap> Graph(last); rec( adjacencies := [ [ 3, 5, 8 ] ], group := Group([ (1,2,3,5,7) (4,6,8,9,10), (2,4)(6,9)(7,10) ]), isGraph := true, names := [ [ 1, 2 ], [ 2, 3 ], [ 3, 4 ], [ 1, 3 ], [ 4, 5 ], [ 2, 4 ], [ 1, 5 ], [ 3, 5 ], [ 1, 4 ], [ 2, 5 ] ], order := 10, representatives := [ 1 ], schreierVector := [ -1, 1, 1, 2, 1, 1, 1, 1, 2, 2 ] )

`‣ AsGraph` ( digraph ) | ( attribute ) |

Returns: A Grape package graph.

If `digraph` is a digraph, then this method returns the same as `Graph`

(3.2-3), except that the result will be stored as a mutable attribute of `digraph`.

If `AsGraph(`

`digraph``)`

is called subsequently, then the same **GAP** object will be returned as before.

gap> d := Digraph([[1, 2], [3], []]); <digraph with 3 vertices, 3 edges> gap> g := AsGraph(d); rec( adjacencies := [ [ 1, 2 ], [ 3 ], [ ] ], group := Group(()), isGraph := true, names := [ 1 .. 3 ], order := 3, representatives := [ 1, 2, 3 ], schreierVector := [ -1, -2, -3 ] )

`‣ AsTransformation` ( digraph ) | ( attribute ) |

Returns: A transformation, or `fail`

If `digraph` is a functional digraph, then `AsTransformation`

returns the transformation which is defined by `digraph`. See `IsFunctionalDigraph`

(6.1-7). Otherwise, `AsTransformation(`

`digraph``)`

returns `fail`

.

If `digraph` is a functional digraph with \(n\) vertices, then `AsTransformation(`

`digraph``)`

will return the transformation `f`

of degree at most \(n\) where for each \(1 \leq i \leq n\), `i ^ f`

is equal to the unique out-neighbour of vertex `i`

in `digraph`.

gap> gr := Digraph([[1], [3], [2]]); <digraph with 3 vertices, 3 edges> gap> gr := CycleDigraph(3); <digraph with 3 vertices, 3 edges> gap> AsTransformation(gr); Transformation( [ 2, 3, 1 ] ) gap> AsPermutation(last); (1,2,3) gap> gr := Digraph([[2, 3], [], []]); <digraph with 3 vertices, 2 edges> gap> AsTransformation(gr); fail

`‣ DigraphCopy` ( digraph ) | ( operation ) |

Returns: A digraph.

This function returns a new copy of `digraph`, retaining none of the attributes or properties of `digraph`.

gap> gr := CycleDigraph(10); <digraph with 10 vertices, 10 edges> gap> DigraphCopy(gr) = gr; true

`‣ InducedSubdigraph` ( digraph, verts ) | ( operation ) |

Returns: A digraph.

If `digraph` is a digraph, and `verts` is a subset of the vertices of `digraph`, then this operation returns a digraph constructed from `digraph` by retaining precisely those vertices in `verts`, and those edges whose source and range vertices are both contained in `verts`.

The vertices of the induced subdigraph are `[1..Length(verts)]`

but the original vertex labels can be accessed via `DigraphVertexLabels`

(5.1-9).

gap> gr := Digraph([[1, 1, 2, 3, 4, 4], [1, 3, 4], [3, 1], [1, 1]]); <multidigraph with 4 vertices, 13 edges> gap> InducedSubdigraph(gr, [1, 3, 4]); <multidigraph with 3 vertices, 9 edges> gap> DigraphVertices(last); [ 1 .. 3 ]

`‣ ReducedDigraph` ( digraph ) | ( attribute ) |

Returns: A digraph.

This function returns a digraph isomorphic to the subdigraph of `digraph` induced by the set of non-isolated vertices, i.e. the set of those vertices of `digraph` which are the source or range of some edge in `digraph`. See `InducedSubdigraph`

(3.3-2).

The vertex and edge labels of the graph are preserved. A vertex in the new digraph can be matched to the corresponding vertex in `digraph` by using the label.

The ordering of the vertices is preserved.

gap> d := Digraph([[1, 2], [], [], [1, 4], []]); <digraph with 5 vertices, 4 edges> gap> r := ReducedDigraph(d); <digraph with 3 vertices, 4 edges> gap> OutNeighbours(r); [ [ 1, 2 ], [ ], [ 1, 3 ] ] gap> DigraphEdges(d); [ [ 1, 1 ], [ 1, 2 ], [ 4, 1 ], [ 4, 4 ] ] gap> DigraphEdges(r); [ [ 1, 1 ], [ 1, 2 ], [ 3, 1 ], [ 3, 3 ] ] gap> DigraphVertexLabel(r, 3); 4 gap> DigraphVertexLabel(r, 2); 2

`‣ MaximalSymmetricSubdigraph` ( digraph ) | ( attribute ) |

`‣ MaximalSymmetricSubdigraphWithoutLoops` ( digraph ) | ( attribute ) |

Returns: A digraph.

If `digraph` is a digraph, then `MaximalSymmetricSubdigraph`

returns a symmetric digraph without multiple edges which has the same vertex set as `digraph`, and whose edge list is formed from `digraph` by ignoring the multiplicity of edges, and by ignoring edges `[u,v]`

for which there does not exist an edge `[v,u]`

.

The digraph returned by `MaximalSymmetricSubdigraphWithoutLoops`

is the same, except that loops are removed.

See `IsSymmetricDigraph`

(6.1-10), `IsMultiDigraph`

(6.1-8), and `DigraphHasLoops`

(6.1-1) for more information.

gap> gr := Digraph([[2, 2], [1, 3], [4], [3, 1]]); <multidigraph with 4 vertices, 7 edges> gap> not IsSymmetricDigraph(gr) and IsMultiDigraph(gr); true gap> OutNeighbours(gr); [ [ 2, 2 ], [ 1, 3 ], [ 4 ], [ 3, 1 ] ] gap> sym := MaximalSymmetricSubdigraph(gr); <digraph with 4 vertices, 4 edges> gap> IsSymmetricDigraph(sym) and not IsMultiDigraph(sym); true gap> OutNeighbours(sym); [ [ 2 ], [ 1 ], [ 4 ], [ 3 ] ]

`‣ UndirectedSpanningTree` ( digraph ) | ( attribute ) |

`‣ UndirectedSpanningForest` ( digraph ) | ( attribute ) |

Returns: A digraph, or `fail`

.

If `digraph` is a digraph with at least one vertex, then `UndirectedSpanningForest`

returns an undirected spanning forest of `digraph`, otherwise this attribute returns `fail`

. See `IsUndirectedSpanningForest`

(4.1-2) for the definition of an undirected spanning forest.

If `digraph` is a digraph with at least one vertex and whose `MaximalSymmetricSubdigraph`

(3.3-4) is connected (see `IsConnectedDigraph`

(6.3-2)), then `UndirectedSpanningTree`

returns an undirected spanning tree of `digraph`, otherwise this attribute returns `fail`

. See `IsUndirectedSpanningTree`

(4.1-2) for the definition of an undirected spanning tree.

Note that for a digraph that has an undirected spanning tree, the attribute `UndirectedSpanningTree`

returns the same digraph as the attribute `UndirectedSpanningForest`

.

gap> gr := Digraph([[1, 2, 1, 3], [1], [4], [3, 4, 3]]); <multidigraph with 4 vertices, 9 edges> gap> UndirectedSpanningTree(gr); fail gap> forest := UndirectedSpanningForest(gr); <digraph with 4 vertices, 4 edges> gap> OutNeighbours(forest); [ [ 2 ], [ 1 ], [ 4 ], [ 3 ] ] gap> IsUndirectedSpanningForest(gr, forest); true gap> DigraphConnectedComponents(forest).comps; [ [ 1, 2 ], [ 3, 4 ] ] gap> DigraphConnectedComponents(MaximalSymmetricSubdigraph(gr)).comps; [ [ 1, 2 ], [ 3, 4 ] ] gap> UndirectedSpanningForest(MaximalSymmetricSubdigraph(gr)) > = forest; true gap> gr := CompleteDigraph(4); <digraph with 4 vertices, 12 edges> gap> tree := UndirectedSpanningTree(gr); <digraph with 4 vertices, 6 edges> gap> IsUndirectedSpanningTree(gr, tree); true gap> tree = UndirectedSpanningForest(gr); true gap> UndirectedSpanningForest(EmptyDigraph(0)); fail

`‣ QuotientDigraph` ( digraph, p ) | ( operation ) |

Returns: A digraph.

If `digraph` is a digraph, and `p` is a partition of the vertices of `digraph`, then this operation returns a new digraph constructed by amalgamating all vertices of `digraph` which lie in the same part of `p`.

A partition of the vertices of `digraph` is a list of non-empty disjoint lists, such that the union of all the sub-lists is equal to the vertex set of `digraph`. In particular, each vertex must appear in precisely one sub-list.

The vertices of `digraph` in part `i`

of `p` will become vertex `i`

in the quotient, and every edge of `digraph` with source in part `i`

and range in part `j`

becomes an edge from `i`

to `j`

in the quotient. In particular, this means that the quotient of a digraph without multiple edges can have multiple edges.

gap> gr := Digraph([[2, 1], [4], [1], [1, 3, 4]]); <digraph with 4 vertices, 7 edges> gap> DigraphVertices(gr); [ 1 .. 4 ] gap> DigraphEdges(gr); [ [ 1, 2 ], [ 1, 1 ], [ 2, 4 ], [ 3, 1 ], [ 4, 1 ], [ 4, 3 ], [ 4, 4 ] ] gap> p := [[1], [2, 4], [3]]; [ [ 1 ], [ 2, 4 ], [ 3 ] ] gap> qr := QuotientDigraph(gr, p); <multidigraph with 3 vertices, 7 edges> gap> DigraphVertices(qr); [ 1 .. 3 ] gap> DigraphEdges(qr); [ [ 1, 2 ], [ 1, 1 ], [ 2, 2 ], [ 2, 1 ], [ 2, 3 ], [ 2, 2 ], [ 3, 1 ] ] gap> QuotientDigraph(EmptyDigraph(0), []); <digraph with 0 vertices, 0 edges>

`‣ DigraphReverse` ( digraph ) | ( operation ) |

Returns: A digraph.

If `digraph` is a digraph, then this operation returns a digraph constructed from `digraph` by reversing the orientation of every edge.

gap> gr := Digraph([[3], [1, 3, 5], [1], [1, 2, 4], [2, 3, 5]]); <digraph with 5 vertices, 11 edges> gap> DigraphReverse(gr); <digraph with 5 vertices, 11 edges> gap> OutNeighbours(last); [ [ 2, 3, 4 ], [ 4, 5 ], [ 1, 2, 5 ], [ 4 ], [ 2, 5 ] ] gap> gr := Digraph([[2, 4], [1], [4], [3, 4]]); <digraph with 4 vertices, 6 edges> gap> DigraphEdges(gr); [ [ 1, 2 ], [ 1, 4 ], [ 2, 1 ], [ 3, 4 ], [ 4, 3 ], [ 4, 4 ] ] gap> DigraphEdges(DigraphReverse(gr)); [ [ 1, 2 ], [ 2, 1 ], [ 3, 4 ], [ 4, 1 ], [ 4, 3 ], [ 4, 4 ] ]

`‣ DigraphDual` ( digraph ) | ( attribute ) |

Returns: A digraph.

If `digraph` is a digraph without multiple edges, then this returns the *dual* of `digraph`. The *dual* is sometimes called the *complement*.

The *dual* of `digraph` has the same vertices as `digraph`, and there is an edge in the dual from `i`

to `j`

whenever there is no edge from `i`

to `j`

in `digraph`.

gap> gr := Digraph([[2, 3], [], [4, 6], [5], [], > [7, 8, 9], [], [], []]); <digraph with 9 vertices, 8 edges> gap> DigraphDual(gr); <digraph with 9 vertices, 73 edges>

`‣ DigraphSymmetricClosure` ( digraph ) | ( attribute ) |

Returns: A digraph.

If `digraph` is a digraph, then this attribute gives the minimal symmetric digraph which has the same vertices and contains all the edges of `digraph`.

A digraph is *symmetric* if its adjacency matrix `AdjacencyMatrix`

(5.2-1) is symmetric. For a digraph with multiple edges this means that there are the same number of edges from a vertex `u`

to a vertex `v`

as there are from `v`

to `u`

; see `IsSymmetricDigraph`

(6.1-10).

gap> gr := Digraph([[1, 2, 3], [2, 4], [1], [3, 4]]); <digraph with 4 vertices, 8 edges> gap> gr1 := DigraphSymmetricClosure(gr); <digraph with 4 vertices, 11 edges> gap> IsSymmetricDigraph(gr1); true gap> List(OutNeighbours(gr1), AsSet); [ [ 1, 2, 3 ], [ 1, 2, 4 ], [ 1, 4 ], [ 2, 3, 4 ] ] gap> gr := Digraph([[2, 2], [1]]); <multidigraph with 2 vertices, 3 edges> gap> gr1 := DigraphSymmetricClosure(gr); <multidigraph with 2 vertices, 4 edges> gap> OutNeighbours(gr1); [ [ 2, 2 ], [ 1, 1 ] ]

`‣ DigraphReflexiveTransitiveClosure` ( digraph ) | ( attribute ) |

`‣ DigraphTransitiveClosure` ( digraph ) | ( attribute ) |

Returns: A digraph.

If `digraph` is a digraph with no multiple edges, then these attributes return the (reflexive) transitive closure of `digraph`.

A digraph is *reflexive* if it has a loop at every vertex, and it is *transitive* if whenever `[i,j]`

and `[j,k]`

are edges of `digraph`, `[i,k]`

is also an edge. The *(reflexive) transitive closure* of a digraph `digraph` is the least (reflexive and) transitive digraph containing `digraph`.

Let \(n\) be the number of vertices of `digraph`, and let \(m\) be the number of edges. For an arbitrary digraph, these attributes will use a version of the Floyd-Warshall algorithm, with complexity \(O(n^3)\). However, for a topologically sortable digraph [see `DigraphTopologicalSort`

(5.1-7)], these attributes will use methods with complexity \(O(m + n + m \cdot n)\) when this is faster.

gap> gr := DigraphFromDiSparse6String(".H`eOWR`Ul^"); <digraph with 9 vertices, 8 edges> gap> IsReflexiveDigraph(gr) or IsTransitiveDigraph(gr); false gap> OutNeighbours(gr); [ [ 4, 6 ], [ 1, 3 ], [ ], [ 5 ], [ ], [ 7, 8, 9 ], [ ], [ ], [ ] ] gap> trans := DigraphTransitiveClosure(gr); <digraph with 9 vertices, 18 edges> gap> OutNeighbours(trans); [ [ 4, 5, 6, 7, 8, 9 ], [ 1, 3, 4, 5, 6, 7, 8, 9 ], [ ], [ 5 ], [ ], [ 7, 8, 9 ], [ ], [ ], [ ] ] gap> reflextrans := DigraphReflexiveTransitiveClosure(gr); <digraph with 9 vertices, 27 edges> gap> OutNeighbours(reflextrans); [ [ 1, 4, 5, 6, 7, 8, 9 ], [ 1, 2, 3, 4, 5, 6, 7, 8, 9 ], [ 3 ], [ 4, 5 ], [ 5 ], [ 6, 7, 8, 9 ], [ 7 ], [ 8 ], [ 9 ] ]

`‣ DigraphReflexiveTransitiveReduction` ( digraph ) | ( operation ) |

`‣ DigraphTransitiveReduction` ( digraph ) | ( operation ) |

Returns: A digraph.

If `digraph` is a topologically sortable digraph [see `DigraphTopologicalSort`

(5.1-7)] with no multiple edges, then these operations return the (reflexive) transitive reduction of `digraph`.

The (reflexive) transitive reduction of such a digraph is the unique least subgraph such that the (reflexive) transitive closure of the subgraph is equal to the (reflexive) transitive closure of `digraph` [see `DigraphReflexiveTransitiveClosure`

(3.3-10)]. In order words, it is the least subgraph of `digraph` which retains the same reachability as `digraph`.

Let \(n\) be the number of vertices of an arbitrary digraph, and let \(m\) be the number of edges. Then these operations use methods with complexity \(O(m + n + m \cdot n)\).

gap> gr := Digraph([[1, 2, 3], [3], [3]]);; gap> DigraphHasLoops(gr); true gap> gr1 := DigraphReflexiveTransitiveReduction(gr); <digraph with 3 vertices, 2 edges> gap> DigraphHasLoops(gr1); false gap> OutNeighbours(gr1); [ [ 2 ], [ 3 ], [ ] ] gap> gr2 := DigraphTransitiveReduction(gr); <digraph with 3 vertices, 4 edges> gap> DigraphHasLoops(gr2); true gap> OutNeighbours(gr2); [ [ 2, 1 ], [ 3 ], [ 3 ] ] gap> DigraphReflexiveTransitiveClosure(gr) > = DigraphReflexiveTransitiveClosure(gr1); true gap> DigraphTransitiveClosure(gr) > = DigraphTransitiveClosure(gr2); true

`‣ DigraphAddVertex` ( digraph[, label] ) | ( operation ) |

Returns: A digraph.

The operation returns a new digraph constructed from `digraph` by adding a single new vertex.

If the optional second argument `label` is a **GAP** object, then the new vertex will be labelled `label`.

gap> gr := CompleteDigraph(3); <digraph with 3 vertices, 6 edges> gap> new := DigraphAddVertex(gr); <digraph with 4 vertices, 6 edges> gap> DigraphVertices(new); [ 1 .. 4 ] gap> new := DigraphAddVertex(gr, Group([(1, 2)])); <digraph with 4 vertices, 6 edges> gap> DigraphVertexLabels(new); [ 1, 2, 3, Group([ (1,2) ]) ]

`‣ DigraphAddVertices` ( digraph, m[, labels] ) | ( operation ) |

Returns: A digraph.

For a non-negative integer `m`, this operation returns a new digraph constructed from `digraph` by adding `m` new vertices.

If the optional third argument `labels` is a list of length `m` consisting of **GAP** objects, then the new vertices will be labelled according to this list.

gap> gr := CompleteDigraph(3); <digraph with 3 vertices, 6 edges> gap> new := DigraphAddVertices(gr, 3); <digraph with 6 vertices, 6 edges> gap> DigraphVertices(new); [ 1 .. 6 ] gap> new := DigraphAddVertices(gr, 2, [Group([(1, 2)]), "d"]); <digraph with 5 vertices, 6 edges> gap> DigraphVertexLabels(new); [ 1, 2, 3, Group([ (1,2) ]), "d" ] gap> DigraphAddVertices(gr, 0) = gr; true

`‣ DigraphAddEdge` ( digraph, edge ) | ( operation ) |

Returns: A digraph.

If `edge` is a pairs of vertices of `digraph`, then this operation returns a new digraph constructed from `digraph` by adding a new edge with source `edge``[1]`

and range `edge``[2]`

.

gap> gr1 := Digraph([[2], [3], []]); <digraph with 3 vertices, 2 edges> gap> DigraphEdges(gr1); [ [ 1, 2 ], [ 2, 3 ] ] gap> gr2 := DigraphAddEdge(gr1, [3, 1]); <digraph with 3 vertices, 3 edges> gap> DigraphEdges(gr2); [ [ 1, 2 ], [ 2, 3 ], [ 3, 1 ] ] gap> gr3 := DigraphAddEdge(gr2, [2, 3]); <multidigraph with 3 vertices, 4 edges> gap> DigraphEdges(gr3); [ [ 1, 2 ], [ 2, 3 ], [ 2, 3 ], [ 3, 1 ] ]

`‣ DigraphAddEdgeOrbit` ( digraph, edge ) | ( operation ) |

Returns: A new digraph.

This operation returns a new digraph with the same vertices and edges as `digraph` and with additional edges consisting of the orbit of the edge `edge` under the action of the `DigraphGroup`

(7.2-9) of `digraph`. If `edge` is already an edge in `digraph`, then `digraph` is returns unchanged.

An edge is simply a pair of vertices of `digraph`.

gap> gr1 := CayleyDigraph(DihedralGroup(8)); <digraph with 8 vertices, 24 edges> gap> gr2 := DigraphAddEdgeOrbit(gr1, [1, 8]); <digraph with 8 vertices, 32 edges> gap> DigraphEdges(gr1); [ [ 1, 2 ], [ 1, 3 ], [ 1, 4 ], [ 2, 1 ], [ 2, 8 ], [ 2, 6 ], [ 3, 5 ], [ 3, 4 ], [ 3, 7 ], [ 4, 6 ], [ 4, 7 ], [ 4, 1 ], [ 5, 3 ], [ 5, 2 ], [ 5, 8 ], [ 6, 4 ], [ 6, 5 ], [ 6, 2 ], [ 7, 8 ], [ 7, 1 ], [ 7, 3 ], [ 8, 7 ], [ 8, 6 ], [ 8, 5 ] ] gap> DigraphEdges(gr2); [ [ 1, 2 ], [ 1, 3 ], [ 1, 4 ], [ 1, 8 ], [ 2, 1 ], [ 2, 8 ], [ 2, 6 ], [ 2, 3 ], [ 3, 5 ], [ 3, 4 ], [ 3, 7 ], [ 3, 2 ], [ 4, 6 ], [ 4, 7 ], [ 4, 1 ], [ 4, 5 ], [ 5, 3 ], [ 5, 2 ], [ 5, 8 ], [ 5, 4 ], [ 6, 4 ], [ 6, 5 ], [ 6, 2 ], [ 6, 7 ], [ 7, 8 ], [ 7, 1 ], [ 7, 3 ], [ 7, 6 ], [ 8, 7 ], [ 8, 6 ], [ 8, 5 ], [ 8, 1 ] ] gap> gr3 := DigraphRemoveEdgeOrbit(gr2, [1, 8]); <digraph with 8 vertices, 24 edges> gap> gr3 = gr1; true

`‣ DigraphAddEdges` ( digraph, edges ) | ( operation ) |

Returns: A digraph.

If `edges` is a (possibly empty) list of pairs of vertices of `digraph`, then this operation returns a new digraph constructed from `digraph` by adding the edges specified by `edges`. More precisely, for every `edge`

in `edges`, a new edge will be added with source `edge[1]`

and range `edges[2]`

.

If an edge is included in `edges` with multiplicity `k`

, then it will be added `k`

times.

gap> func := function(n) > local source, range, i; > source := []; > range := []; > for i in [1 .. n - 2] do > Add(source, i); > Add(range, i + 1); > od; > return Digraph(n, source, range); > end;; gap> gr := func(1024); <digraph with 1024 vertices, 1022 edges> gap> gr := DigraphAddEdges(gr, > [[1023, 1024], [1, 1024], [1023, 1024], [1024, 1]]); <multidigraph with 1024 vertices, 1026 edges>

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

Returns: A digraph.

If `v` is a vertex of `digraph`, then this operation returns a new digraph constructed from `digraph` by removing vertex `v`, along with any edge whose source or range vertex is `v`.

If `digraph` has `n`

vertices, then the vertices of the new digraph are `[1..n-1]`

, but the original labels can be accessed via `DigraphVertexLabels`

(5.1-9).

gap> gr := Digraph(["a", "b", "c"], > ["a", "a", "b", "c", "c"], > ["b", "c", "a", "a", "c"]); <digraph with 3 vertices, 5 edges> gap> DigraphVertexLabels(gr); [ "a", "b", "c" ] gap> DigraphEdges(gr); [ [ 1, 2 ], [ 1, 3 ], [ 2, 1 ], [ 3, 1 ], [ 3, 3 ] ] gap> new := DigraphRemoveVertex(gr, 2); <digraph with 2 vertices, 3 edges> gap> DigraphVertexLabels(new); [ "a", "c" ]

`‣ DigraphRemoveVertices ` ( digraph, verts ) | ( operation ) |

Returns: A digraph.

If `verts` is a (possibly empty) duplicate-free list of vertices of `digraph`, then this operation returns a new digraph constructed from `digraph` by removing every vertex in `verts`, along with any edge whose source or range vertex is in `verts`.

If `digraph` has `n`

vertices, then the vertices of the new digraph are `[1 .. n-Length(`

, but the original labels can be accessed via `verts`)]`DigraphVertexLabels`

(5.1-9).

gap> gr := Digraph([[3], [1, 3, 5], [1], [1, 2, 4], [2, 3, 5]]); <digraph with 5 vertices, 11 edges> gap> SetDigraphVertexLabels(gr, ["a", "b", "c", "d", "e"]); gap> new := DigraphRemoveVertices(gr, [2, 4]); <digraph with 3 vertices, 4 edges> gap> DigraphVertexLabels(new); [ "a", "c", "e" ]

`‣ DigraphRemoveEdge` ( digraph, edge ) | ( operation ) |

Returns: A digraph.

If one of the following holds:

`digraph`is a digraph with no multiple edges, and`edge`is a pair of vertices of`digraph`, or`digraph`is any digraph and`edge`is the index of an edge of`digraph`,

then this operation returns a new digraph constructed from `digraph` by removing the edges specified by `edges`. If, in the first case, the pair of vertices `edge` does not specify an edge of `digraph`, then a new copy of `digraph` will be returned.

gap> gr := CycleDigraph(250000); <digraph with 250000 vertices, 250000 edges> gap> gr := DigraphRemoveEdge(gr, [250000, 1]); <digraph with 250000 vertices, 249999 edges> gap> gr := DigraphRemoveEdge(gr, 10); <digraph with 250000 vertices, 249998 edges>

`‣ DigraphRemoveEdgeOrbit` ( digraph, edge ) | ( operation ) |

Returns: A new digraph.

This operation returns a new digraph with the same vertices as `digraph` and with the orbit of the edge `edge` (under the action of the `DigraphGroup`

(7.2-9) of `digraph`) removed. If `edge` is not an edge in `digraph`, then `digraph` is returned unchanged.

An edge is simply a pair of vertices of `digraph`.

gap> gr1 := CayleyDigraph(DihedralGroup(8)); <digraph with 8 vertices, 24 edges> gap> gr2 := DigraphAddEdgeOrbit(gr1, [1, 8]); <digraph with 8 vertices, 32 edges> gap> DigraphEdges(gr1); [ [ 1, 2 ], [ 1, 3 ], [ 1, 4 ], [ 2, 1 ], [ 2, 8 ], [ 2, 6 ], [ 3, 5 ], [ 3, 4 ], [ 3, 7 ], [ 4, 6 ], [ 4, 7 ], [ 4, 1 ], [ 5, 3 ], [ 5, 2 ], [ 5, 8 ], [ 6, 4 ], [ 6, 5 ], [ 6, 2 ], [ 7, 8 ], [ 7, 1 ], [ 7, 3 ], [ 8, 7 ], [ 8, 6 ], [ 8, 5 ] ] gap> DigraphEdges(gr2); [ [ 1, 2 ], [ 1, 3 ], [ 1, 4 ], [ 1, 8 ], [ 2, 1 ], [ 2, 8 ], [ 2, 6 ], [ 2, 3 ], [ 3, 5 ], [ 3, 4 ], [ 3, 7 ], [ 3, 2 ], [ 4, 6 ], [ 4, 7 ], [ 4, 1 ], [ 4, 5 ], [ 5, 3 ], [ 5, 2 ], [ 5, 8 ], [ 5, 4 ], [ 6, 4 ], [ 6, 5 ], [ 6, 2 ], [ 6, 7 ], [ 7, 8 ], [ 7, 1 ], [ 7, 3 ], [ 7, 6 ], [ 8, 7 ], [ 8, 6 ], [ 8, 5 ], [ 8, 1 ] ] gap> gr3 := DigraphRemoveEdgeOrbit(gr2, [1, 8]); <digraph with 8 vertices, 24 edges> gap> gr3 = gr1; true

`‣ DigraphRemoveEdges` ( digraph, edges ) | ( operation ) |

Returns: A digraph.

If one of the following holds:

`digraph`is a digraph with no multiple edges, and`edges`is a list of pairs of vertices of`digraph`, or`digraph`is any digraph and`edges`is a list of indices of edges of`digraph`,

then this operation returns a new digraph constructed from `digraph` by removing all of the edges specified by `edges` [see `DigraphRemoveEdge`

(3.3-19)].

gap> gr := CycleDigraph(250000); <digraph with 250000 vertices, 250000 edges> gap> gr := DigraphRemoveEdges(gr, [[250000, 1]]); <digraph with 250000 vertices, 249999 edges> gap> gr := DigraphRemoveEdges(gr, [10]); <digraph with 250000 vertices, 249998 edges>

`‣ DigraphRemoveLoops` ( digraph ) | ( operation ) |

Returns: A digraph.

If `digraph` is a digraph, then this operation returns a new digraph constructed from `digraph` by removing every loop. A loop is an edge with equal source and range.

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

`‣ DigraphRemoveAllMultipleEdges` ( digraph ) | ( operation ) |

Returns: A digraph.

If `digraph` is a digraph, then this operation returns a new digraph constructed from `digraph` by removing all multiple edges. The result is the largest subdigraph of `digraph` which does not contain multiple edges.

gap> gr1 := Digraph([[1, 2, 3, 2], [1, 1, 3], [2, 2, 2]]); <multidigraph with 3 vertices, 10 edges> gap> gr2 := DigraphRemoveAllMultipleEdges(gr1); <digraph with 3 vertices, 6 edges> gap> OutNeighbours(gr2); [ [ 1, 2, 3 ], [ 1, 3 ], [ 2 ] ]

`‣ DigraphReverseEdges` ( digraph, edges ) | ( operation ) |

`‣ DigraphReverseEdge` ( digraph, edge ) | ( operation ) |

Returns: A digraph.

If `digraph` is a digraph without multiple edges, and `edges` is either:

a list of pairs of vertices of

`digraph`(the entries of each pair corresponding to the source and the range of an edge, respectively),a list of positions of elements in the list

`DigraphEdges`

(5.1-3),

then `DigraphReverseEdges`

returns a new digraph constructed from `digraph` by reversing the orientation of every edge specified by `edges`. If only one edge is to be reversed, then `DigraphReverseEdge`

can be used instead. In this case, the second argument should just be a single vertex-pair or a single position.

Note that even though `digraph` cannot have multiple edges, the output may have multiple edges.

gap> gr := DigraphFromDiSparse6String(".Tg?i@s?t_e?_qEsC"); <digraph with 21 vertices, 8 edges> gap> DigraphEdges(gr); [ [ 1, 2 ], [ 1, 7 ], [ 1, 8 ], [ 5, 21 ], [ 7, 19 ], [ 9, 1 ], [ 11, 2 ], [ 21, 1 ] ] gap> gr2 := DigraphReverseEdges(gr, [1, 2, 4]); <digraph with 21 vertices, 8 edges> gap> gr = DigraphReverseEdges(gr2, [[7, 1], [2, 1], [21, 5]]); true gap> gr2 := DigraphReverseEdge(gr, 5); <digraph with 21 vertices, 8 edges> gap> gr2 = DigraphReverseEdge(gr, [7, 19]); true

`‣ DigraphDisjointUnion` ( gr1, gr2, ... ) | ( function ) |

`‣ DigraphDisjointUnion` ( list ) | ( function ) |

Returns: A digraph.

In the first form, if `gr1`, `gr2`, etc. are digraphs, then `DigraphDisjointUnion`

returns their disjoint union. In the second form, if `list` is a non-empty list of digraphs, then `DigraphDisjointUnion`

returns the disjoint union of the digraphs contained in the list.

For a disjoint union of digraphs, the vertex set is the disjoint union of the vertex sets, and the edge list is the disjoint union of the edge lists.

More specifically, for a collection of digraphs `gr1`, `gr2`, `...`

, the disjoint union with have `DigraphNrVertices(`

`gr1``)`

`+`

`DigraphNrVertices(`

`gr2``)`

`+`

`...`

vertices. The edges of `gr1` will remain unchanged, whilst the edges of the `i`

th digraph, `gr``[i]`

, will be changed so that they belong to the vertices of the disjoint union corresponding to `gr``[i]`

. In particular, the edges of `gr``[i]`

will have their source and range increased by `DigraphNrVertices(`

`gr1``)`

`+`

`...`

`+`

`DigraphNrVertices(`

`gr``[i-1])`

.

Note that previously set `DigraphVertexLabels`

(5.1-9) will be lost.

gap> gr1 := CycleDigraph(3); <digraph with 3 vertices, 3 edges> gap> OutNeighbours(gr1); [ [ 2 ], [ 3 ], [ 1 ] ] gap> gr2 := CompleteDigraph(3); <digraph with 3 vertices, 6 edges> gap> OutNeighbours(gr2); [ [ 2, 3 ], [ 1, 3 ], [ 1, 2 ] ] gap> union := DigraphDisjointUnion(gr1, gr2); <digraph with 6 vertices, 9 edges> gap> OutNeighbours(union); [ [ 2 ], [ 3 ], [ 1 ], [ 5, 6 ], [ 4, 6 ], [ 4, 5 ] ]

`‣ DigraphEdgeUnion` ( gr1, gr2, ... ) | ( function ) |

`‣ DigraphEdgeUnion` ( list ) | ( function ) |

Returns: A digraph.

In the first form, if `gr1`, `gr2`, etc. are digraphs, then `DigraphEdgeUnion`

returns their edge union. In the second form, if `list` is a non-empty list of digraphs, then `DigraphEdgeUnion`

returns the edge union of the digraphs contained in the list.

The vertex set of the edge union of a collection of digraphs is the *union* of the vertex sets, whilst the edge list of the edge union is the *concatenation* of the edge lists. The number of vertices of the edge union is equal to the *maximum* number of vertices of one of the digraphs, whilst the number of edges of the edge union will equal the *sum* of the number of edges of each digraph.

Note that previously set `DigraphVertexLabels`

(5.1-9) will be lost.

gap> gr := CycleDigraph(10); <digraph with 10 vertices, 10 edges> gap> DigraphEdgeUnion(gr, gr); <multidigraph with 10 vertices, 20 edges> gap> gr1 := Digraph([[2], [1]]); <digraph with 2 vertices, 2 edges> gap> gr2 := Digraph([[2, 3], [2], [1]]); <digraph with 3 vertices, 4 edges> gap> union := DigraphEdgeUnion(gr1, gr2); <multidigraph with 3 vertices, 6 edges> gap> OutNeighbours(union); [ [ 2, 2, 3 ], [ 1, 2 ], [ 1 ] ] gap> union = DigraphByEdges( > Concatenation(DigraphEdges(gr1), DigraphEdges(gr2))); true

`‣ DigraphJoin` ( gr1, gr2, ... ) | ( function ) |

`‣ DigraphJoin` ( list ) | ( function ) |

Returns: A digraph.

In the first form, if `gr1`, `gr2`, etc. are digraphs, then `DigraphJoin`

returns their join. In the second form, if `list` is a non-empty list of digraphs, then `DigraphJoin`

returns the join of the digraphs contained in the list.

The join of a collection of digraphs `gr1`, `gr2`, `...`

is formed by first taking the `DigraphDisjointUnion`

(3.3-25) of the collection. In the disjoint union, if \(i \neq j\) then there are no edges between vertices corresponding to digraphs `gr``[i]`

and `gr``[j]`

in the collection; the join is created by including all such edges.

For example, the join of two empty digraphs is a complete bipartite digraph.

Note that previously set `DigraphVertexLabels`

(5.1-9) will be lost.

gap> gr := CompleteDigraph(3); <digraph with 3 vertices, 6 edges> gap> IsCompleteDigraph(DigraphJoin(gr, gr)); true gap> gr2 := CycleDigraph(3); <digraph with 3 vertices, 3 edges> gap> DigraphJoin(gr, gr2); <digraph with 6 vertices, 27 edges>

`‣ LineDigraph` ( digraph ) | ( operation ) |

`‣ EdgeDigraph` ( digraph ) | ( operation ) |

Returns: A digraph.

Given a digraph `digraph`, the operation returns the digraph obtained by associating a vertex with each edge of `digraph`, and creating an edge from a vertex `v`

to a vertex `u`

if and only if the terminal vertex of the edge associated with `v`

is the start vertex of the edge associated with `u`

.

gap> LineDigraph(CompleteDigraph(3)); <digraph with 6 vertices, 12 edges> gap> LineDigraph(ChainDigraph(3)); <digraph with 2 vertices, 1 edge>

`‣ LineUndirectedDigraph` ( digraph ) | ( operation ) |

`‣ EdgeUndirectedDigraph` ( digraph ) | ( operation ) |

Returns: A digraph.

Given a symmetric digraph `digraph`, the operation returns the symmetric digraph obtained by associating a vertex with each edge of `digraph`, ignoring directions and multiplicites, and adding an edge between two vertices if and only if the corresponding edges have a vertex in common.

gap> LineUndirectedDigraph(CompleteDigraph(3)); <digraph with 3 vertices, 6 edges> gap> LineUndirectedDigraph(DigraphSymmetricClosure(ChainDigraph(3))); <digraph with 2 vertices, 2 edges>

`‣ DoubleDigraph` ( digraph ) | ( operation ) |

Returns: A digraph.

Let `digraph` be a digraph with vertex set `V`

. This function returns the double digraph of `digraph`. The vertex set of the double digraph is the orginal vertex set together with a duplicate. The edges are `[u_1, v_2]`

and `[u_2, v_1]`

if and only if `[u, v]`

is an edge in `digraph`, together with the original edges and their duplicates.

gap> gamma := Digraph([[2], [3], [1]]); <digraph with 3 vertices, 3 edges> gap> DoubleDigraph(gamma); <digraph with 6 vertices, 12 edges>

`‣ BipartiteDoubleDigraph` ( digraph ) | ( operation ) |

Returns: A digraph.

Let `digraph` be a digraph with vertex set `V`

. This function returns the bipartite double digraph of `digraph`. The vertex set of the double digraph is the orginal vertex set together with a duplicate. The edges are `[u_1, v_2]`

and `[u_2, v_1]`

if and only if `[u, v]`

is an edge in `digraph`. The resulting graph is bipartite, since the orignal edges are not included in the resulting digraph.

gap> gamma := Digraph([[2], [3], [1]]); <digraph with 3 vertices, 3 edges> gap> BipartiteDoubleDigraph(gamma); <digraph with 6 vertices, 6 edges>

`‣ DigraphAddAllLoops` ( digraph ) | ( operation ) |

Returns: A digraph.

For a digraph `digraph` this operation return a copy of `digraph` such that a loop is added for every vertex which did not have a loop in `digraph`.

gap> gr := EmptyDigraph(13); <digraph with 13 vertices, 0 edges> gap> gr := DigraphAddAllLoops(gr); <digraph with 13 vertices, 13 edges> gap> OutNeighbours(gr); [ [ 1 ], [ 2 ], [ 3 ], [ 4 ], [ 5 ], [ 6 ], [ 7 ], [ 8 ], [ 9 ], [ 10 ], [ 11 ], [ 12 ], [ 13 ] ] gap> gr := Digraph([[1, 2, 3], [1, 3], [1]]); <digraph with 3 vertices, 6 edges> gap> gr := DigraphAddAllLoops(gr); <digraph with 3 vertices, 8 edges> gap> OutNeighbours(gr); [ [ 1, 2, 3 ], [ 1, 3, 2 ], [ 1, 3 ] ]

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

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

Returns: A digraph.

The first argument is a digraph, the second argument is a non-negative integer or a list of positive integers. This operation returns a digraph on the same set of vertices as `digraph`, with two vertices being adjacent if and only if the distance between them in `digraph` equals `i` or is a number in `list`. See `DigraphShortestDistance`

(5.3-2).

gap> digraph := DigraphFromSparse6String( > ":]n?AL`BC_DEbEF`GIaGHdIJeGKcKL_@McDHfILaBJfHMjKM"); <digraph with 30 vertices, 90 edges> gap> DistanceDigraph(digraph, 1); <digraph with 30 vertices, 90 edges> gap> DistanceDigraph(digraph, [1, 2]); <digraph with 30 vertices, 270 edges>

`‣ DigraphClosure` ( digraph, k ) | ( operation ) |

Returns: A digraph

Given a symmetric loopless digraph with no multiple edges `digraph`, the * k-closure of digraph* is defined to be the unique smallest symmetric loopless digraph

`C`

with no multiple edges on the vertices of `C`

is less than `IsSymmetricDigraph`

(6.1-10), `DigraphHasLoops`

(6.1-1), `IsMultiDigraph`

(6.1-8), and `OutDegreeOfVertex`

(5.2-9).The operation `DigraphClosure`

returns the `k`-closure of `digraph`.

gap> gr := CompleteDigraph(6);; gap> DigraphRemoveEdges(gr, [[1, 2], [2, 1]]);; gap> closure := DigraphClosure(gr, 6); <digraph with 6 vertices, 30 edges> gap> IsCompleteDigraph(closure); true

`‣ RandomDigraph` ( n[, p] ) | ( operation ) |

Returns: A digraph.

If `n` is a positive integer, then this function returns a random digraph with `n` vertices and without multiple edges. The result may or may not have loops.

If the optional second argument `p` is a float with value \(0 \leq \) ` p ` \( \leq 1\), then an edge will exist between each pair of vertices with probability approximately `p`. If `p` is not specified, then a random probability will be assumed (chosen with uniform probability).

gap> RandomDigraph(1000); <digraph with 1000 vertices, 364444 edges> gap> RandomDigraph(10000, 0.023); <digraph with 10000 vertices, 2300438 edges>

`‣ RandomMultiDigraph` ( n[, m] ) | ( operation ) |

Returns: A digraph.

If `n` is a positive integer, then this function returns a random digraph with `n` vertices. If the optional second argument `m` is a positive integer, then the digraph will have `m` edges. If `m` is not specified, then the number of edges will be chosen randomly (with uniform probability) from the range `[1 .. `

\({n \choose 2}\)`]`

.

The method used by this function chooses each edge from the set of all possible edges with uniform probability. No effort is made to avoid creating multiple edges, so it is possible (but not guaranteed) that the result will have multiple edges. The result may or may not have loops.

gap> RandomMultiDigraph(1000); <multidigraph with 1000 vertices, 216659 edges> gap> RandomMultiDigraph(1000, 950); <multidigraph with 1000 vertices, 950 edges>

`‣ RandomTournament` ( n ) | ( operation ) |

Returns: A digraph.

If `n` is a non-negative integer, this function returns a random tournament with `n` vertices. See `IsTournament`

(6.1-11).

gap> RandomTournament(10); <digraph with 10 vertices, 45 edges>

`‣ ChainDigraph` ( n ) | ( operation ) |

Returns: A digraph.

If `n` is a positive integer, this function returns a chain with `n` vertices and

edges. Specifically, for each vertex `n` - 1`i`

(with `i`

< `n`

), there is a directed edge with source `i`

and range `i + 1`

.

The `DigraphReflexiveTransitiveClosure`

(3.3-10) of a chain represents a total order.

gap> ChainDigraph(42); <digraph with 42 vertices, 41 edges>

`‣ CompleteDigraph` ( n ) | ( operation ) |

Returns: A digraph.

If `n` is a non-negative integer, this function returns the complete digraph with `n` vertices. See `IsCompleteDigraph`

(6.1-5).

gap> CompleteDigraph(20); <digraph with 20 vertices, 380 edges>

`‣ CompleteBipartiteDigraph` ( m, n ) | ( operation ) |

Returns: A digraph.

A complete bipartite digraph is a digraph whose vertices can be partitioned into two non-empty vertex sets, such there exists a unique edge with source `i`

and range `j`

if and only if `i`

and `j`

lie in different vertex sets.

If `m` and `n` are positive integers, this function returns the complete bipartite digraph with vertex sets of sizes `m` (containing the vertices `[1 .. m]`

) and `n` (containing the vertices `[m + 1 .. m + n]`

).

gap> CompleteBipartiteDigraph(2, 3); <digraph with 5 vertices, 12 edges>

`‣ CompleteMultipartiteDigraph` ( orders ) | ( operation ) |

Returns: A digraph.

For a list `orders` of `n`

positive integers, this function returns the digraph containing `n`

independent sets of vertices of orders `[`

. Moreover, each vertex is adjacent to every other not contained in the same independent set.`l`[1] .. `l`[n]]

gap> CompleteMultipartiteDigraph([5, 4, 2]); <digraph with 11 vertices, 76 edges>

`‣ CycleDigraph` ( n ) | ( operation ) |

Returns: A digraph.

If `n` is a positive integer, this function returns a *cycle* digraph with `n` vertices and `n` edges. Specifically, for each vertex `i`

(with `i`

< `n`

), there is a directed edge with source `i`

and range `i + 1`

. In addition, there is an edge with source `n`

and range `1`

.

gap> CycleDigraph(1); <digraph with 1 vertex, 1 edge> gap> CycleDigraph(123); <digraph with 123 vertices, 123 edges>

`‣ EmptyDigraph` ( n ) | ( operation ) |

`‣ NullDigraph` ( n ) | ( operation ) |

Returns: A digraph.

If `n` is a non-negative integer, this function returns the *empty* or *null* digraph with `n` vertices. An empty digraph is one with no edges.

`NullDigraph`

is a synonym for `EmptyDigraph`

.

gap> EmptyDigraph(20); <digraph with 20 vertices, 0 edges> gap> NullDigraph(10); <digraph with 10 vertices, 0 edges>

`‣ JohnsonDigraph` ( n, k ) | ( operation ) |

Returns: A digraph.

If `n` and `k` are non-negative integers, then this operation returns a symmetric digraph which corresponds to the undirected *Johnson graph* \(J(n, k)\).

The *Johnson graph* \(J(n, k)\) has vertices given by all the `k`-subsets of the range `[1 .. `

, and two vertices are connected by an edge iff their intersection has size \(\textit{k} - 1\).`k`]

gap> gr := JohnsonDigraph(3, 1); <digraph with 3 vertices, 6 edges> gap> OutNeighbours(gr); [ [ 2, 3 ], [ 1, 3 ], [ 1, 2 ] ] gap> gr := JohnsonDigraph(4, 2); <digraph with 6 vertices, 24 edges> gap> OutNeighbours(gr); [ [ 2, 3, 4, 5 ], [ 1, 3, 4, 6 ], [ 1, 2, 5, 6 ], [ 1, 2, 5, 6 ], [ 1, 3, 4, 6 ], [ 2, 3, 4, 5 ] ] gap> JohnsonDigraph(1, 0); <digraph with 1 vertex, 0 edges>

generated by GAPDoc2HTML