This is the manual for version 1.9.0 of the Digraphs package. This package was developed at the University of St Andrews by:
Jan De Beule,
Julius JonuĊĦas,
James D. Mitchell,
Maria Tsalakou,
Wilf A. Wilson, and
Michael C. Young.
Additional contributions were made by:
Marina Anagnostopoulou-Merkouri,
Finn Buck,
Stuart Burrell,
Reinis Cirpons,
Tom Conti-Leslie,
Luke Elliott,
Ewan Gilligan,
Max Horn,
Christopher Jefferson,
Markus Pfeiffer,
Lea Racine,
Christopher Russell,
Finn Smith,
Ben Spiers, and
Murray Whyte.
The Digraphs package contains a variety of methods for efficiently creating and storing mutable and immutable digraphs and computing information about them. Full explanations of all the functions contained in the package are provided below.
If the GRAPE package is available, it will be loaded automatically. Digraphs created with the Digraphs package can be converted to GRAPE graphs with Graph (3.2-3), and conversely GRAPE graphs can be converted to Digraphs objects with Digraph (3.1-7). GRAPE is not required for Digraphs to run.
The bliss tool [JK07] is included in this package. It is an open-source tool for computing automorphism groups and canonical forms of graphs, written by Tommi Junttila and Petteri Kaski. Several of the methods in the Digraphs package rely on bliss . If the NautyTracesInterface package for GAP is available then it is also possible to use nauty [MP14] for computing automorphism groups and canonical forms in Digraphs. See Section 7.2 for more details.
The edge-addition-planarity-suite is also included in Digraphs; see [BM04], [Boy06], [BM06], and [Boy12] . The edge-addition-planarity-suite is an open-source implementation of the edge addition planar graph embedding algorithm and related algorithms by John M. Boyer. See Section 6.7 for more details.
From version 1.0.0 of this package, digraphs can be either mutable or immutable. Mutable digraphs can be changed in-place by many of the methods in the package, which avoids unnecessary copying. Immutable digraphs cannot be changed in-place, but their advantage is that the value of an attribute of an immutable digraph is only ever computed once. Mutable digraphs can be converted into immutable digraphs in-place using MakeImmutable (Reference: MakeImmutable). One of the motivations for introducing mutable digraphs in version 1.0.0 was that in practice the authors often wanted to create a digraph and immediately modify it (removing certain edges, loops, and so on). Before version 1.0.0, this involved copying the digraph several times, with each copy being discarded almost immediately. From version 1.0.0, this unnecessary copying can be eliminated by first creating a mutable digraph, then changing it in-place, and finally converting the mutable digraph to an immutable one in-place (if desirable).
For the purposes of this package and its documentation, the following definitions apply:
A digraph \(E=(E^0,E^1,r,s)\), also known as a directed graph, consists of a set of vertices \(E^0\) and a set of edges \(E^1\) together with functions \(s, r: E^1 \to E^0\), called the source and range, respectively. The source and range of an edge is respectively the values of \(s, r\) at that edge. An edge is called a loop if its source and range are the same. A digraph is called a multidigraph if there exist two or more edges with the same source and the same range.
A directed walk on a digraph is a sequence of alternating vertices and edges \((v_1, e_1, v_2, e_2, ..., e_{n-1}, v_n)\) such that each edge \(e_i\) has source \(v_i\) and range \(v_{i+1}\). A directed path is a directed walk where no vertex (and hence no edge) is repeated. A directed circuit is a directed walk where \(v_1 = v_n\), and a directed cycle is a directed circuit where where no vertex is repeated, except for \(v_1 = v_n\).
The length of a directed walk \((v_1, e_1, v_2, e_2, ..., e_{n-1}, v_n)\) is equal to \(n-1\), the number of edges it contains. A directed walk (or path) \((v_1, e_1, v_2, e_2, ..., e_{n-1}, v_n)\) is sometimes called a directed walk (or path) from vertex \(v_1\) to vertex \(v_n\). A directed walk of zero length, i.e. a sequence \((v)\) for some vertex \(v\), is called trivial. A trivial directed walk is considered to be both a circuit and a cycle, as is the empty directed walk \(()\). A simple circuit is another name for a non-trivial and non-empty directed cycle.
generated by GAPDoc2HTML