A simple graph is a graph in which each edge joins two distinct vertices and two distinct vertices are joined by at most one edge. A simple digraph, whose edges are directed, is defined in an analogous manner. Thus, loops and multiple edges are not permitted in simple graphs and simple digraphs. A graph (digraph) with loops and/or multiple edges joining a fixed pair of vertices is called a multigraph (resp. multidigraph). A multidigraph whose edges are assigned a capacity is more commonly called a network.
In this chapter the term "graph" is used when referring to a simple undirected graph, while the term "digraph" is used when referring to a simple directed graph. Sometimes the term "graph" is used as the generic term for the incidence structure on vertices and edges. Such uses should be clear from the context in which they occur.
There are five Magma graph objects: the undirected simple graph of type GrphUnd, the directed simple graph of type GrphDir, the undirected multigraph of type GrphMultUnd, the directed multigraph of type GrphMultDir, and the network of type GrphNet. The simple graphs are all of type Grph, while the multigraphs (including the network) are of type GrphMult. There is a caveat here with respect to simple digraphs and loops: for historical reasons, Magma allows loops in digraphs.
Simple graphs and digraphs are covered in this chapter, while multigraphs, multidigraphs are covered in Chapter MULTIGRAPHS and networks in Chapter NETWORKS. All types of graphs may have vertex labellings and/or edge labellings. In addition, assigning weights and/or capacities to graph edges is also possible, thus allowing to run shortest-paths and flow-based algorithms over the graphs.
Importantly, from the present version (V2.11) onwards, all the standard graph construction functions (see Subsections Subgraphs and Quotient Graphs and Incremental Construction of Graphs) respect the graph's support set and vertex and edge decorations. That is, the resulting graph will have a support set and vertex and edge decorations compatible with the original graph and the operation performed on that graph.
Magma employs two distinct data structures for representing graphs. A graph may be represented in the form of an adjacency matrix (the dense representation) or in the form of an adjacency list (the sparse representation). The latter is better suited for sparse graphs and for algorithms which have been designed with the adjacency list representation in mind. An advantage of the sparse representation is the possibility of creating much larger (sparse) graphs than would be possible using the dense representation, since memory requirements for the adjacency list representation is linear in the number of edges, while memory requirements for the adjacency matrix representation is quadratic in the number of vertices (order) of the graph. This is covered in detail in Section Bounds on the Graph Order.
Further, multigraphs and multidigraphs (and networks) may only be represented by an adjacency list since they may contain multiple edges. Users have control over the choice of representation when creating simple graphs or digraphs. If no indication is given, simple graphs and digraphs are always created with the dense representation. At the time of the present release (V2.11), a significant part of Magma functions are able to work directly with either of the representations. However, wherever necessary, a graph will be converted internally to whichever representation is required by a given function. We emphasize that this process is completely transparent to users and requires no intervention on their part.
For a concise and comprehensive overview on graph theory and algorithms, the reader is referred to [Eve79]; in [TCR90] they'll find a clear exposure of some graph algorithms, and [AMO93] is the recommended reference for flow problems in graphs.