This is the manual for the **Digraphs** package version 0.13.0. This package was developed at the University of St Andrews by:

Jan De Beule,

Julius JonuĊĦas,

James D. Mitchell,

Michael C. Torpey, and

Wilf A. Wilson.

Additional contributions were made by:

Stuart Burrell,

Luke Elliott,

Christopher Jefferson,

Markus Pfeiffer,

Chris Russell, and

Finn Smith.

The **Digraphs** package contains a variety of methods for efficiently creating and storing 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-5). 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.

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