Introduction

Both directed and undirected graphs are supported by Magma. In the case of undirected graphs, neither multiple edges nor loops are permitted. In the case of directed graphs, loops are permitted but multiple edges are disallowed. Both directed and undirected graphs may have vertex labellings and/or edge labellings.

Magma also supports two equivalent graph representations: A graph as an adjacency matrix (the dense representation), or a graph as an adjacency list (the sparse representation). The latter is better suited for sparse graphs and for some algorithms especially written with the sparse representation in mind. Also, one immediate advantage of the sparse representation is the possibility of creating much larger (sparse) graphs as would be possible using the dense representation, since the storage space for the adjacency list is linear in the number of edges, while the storage space for the matrix is quadratic in the order of the graph.

Users will have the choice of creating graphs with either representation. If no indication is given, graphs are always created as dense graphs. As of today, only a handfull of Magma functions have been (re)written which can deal with the sparse representation. If necessary, the graph will be internally converted to whichever representation the chosen function requires. We emphasize that this process is completely transparent to users.

Given a graph G, unless otherwise stated, the vertex set of G will be written as V or V(G) if it might be ambiguous, while the edge set of G will be written as E or E(G). We shall frequently use the term (p, q) graph to refer to a graph having p vertices and q edges.