A graph G consists of a set of vertices and a set of edges, where each edge denotes a connection between two of the vertices. A graph is simple if it has no loops (a loop is an edge connecting a vertex to itself) and has at most one edge between any given pair of vertices. A directed graph (shortened to digraph) is one in which the connections are “one-way”: An edge from u to v is not equivalent to an edge from v to u. Consequently, a simple digraph may have an edge from v to u as well as one from u to v.
Non-simple graphs (and digraphs) are called multigraphs (respectively, multidigraphs or directed multigraphs). Magma supports all four of these graph types. In the rest of this section, the term “graph” will be used as an inclusive term for all of these graph types.
Vertices and edges of a graph may have additional information associated to them. In the case of vertices it is traditional to think of this as assigning a colour to each vertex. Edges are very commonly assigned numeric values, which are usually referred to as “weights”.
Graphs arise naturally in a good many contexts, and this is reflected in the rich variety of construction tools that Magma provides for graphs. To start with, there is a completely general means of specifying a graph via either an explicit listing of the edge relations or an adjacency matrix. Graphs may also be constructed from groups (Cayley graph, Schreier graph, orbital graph, closure graph, Paley graph, Paley tournament) and designs (incidence graph, point graph, block graph, line graph, Hadamard graph). Then there are iterative techniques for constructing graphs from other graphs; examples include addition or removal of vertices and/or edges, union, product, complement, contraction, and switching.
Magma also provides easy ways to create graphs of various well-known families, such as bipartite graphs, multipartite graphs, complete graphs, k-cube graphs, polygon graphs, path graphs, and others. It is also possible to create random graphs and trees. Additionally, several optional databases of graphs are made available for use with Magma. These include a database of strongly regular graphs, and several databases of small graphs, including Eulerian graphs, planar graphs, and self-complementary graphs.
A clique of a graph is a set of vertices such that any two are connected to each other. An independent set is a set of vertices such that no two of them are connected to each other. An independent set thus corresponds to a clique in the complement graph.
Two algorithms are provided for finding cliques in a graph, depending on whether the aim is to find cliques of a given size, or to find the largest possible cliques. To find the largest clique size the branch and bound algorithm of Bron and Kerbosch is preferred. When the size is specified in advance then the algorithm used is a dynamic one due to Walker, Myrvold, and Prsa.
Note that the Magma implementation of the branch and bound algorithm has been adapted into a variant that can also search for non-maximal cliques of a given size. Also, the dynamic algorithm can be iterated in order to determine a maximum clique size. Consequently, each approach can be used to solve each problem, and which is the better option will depend on the structure of the graph. In general, though, the above algorithm choices are often best.
An important (and difficult) problem in the theory of graphs is to determine whether two graphs are isomorphic. A related problem is to determine a canonical representation of a given graph; if this can be done then it leads to a simple test for isomorphism: Two graphs are isomorphic exactly when their canonical representations are the same.
Magma takes this approach to the graph isomorphism problem, using B. McKay's excellent nauty software, widely regarded as state of the art in this area and included in Magma with his permission. Additionally, nauty is able to produce the full group of automorphisms of a graph, solving another problem of key importance.
In each case the morphisms will take into consideration any vertex-colouring of the graphs, ensuring that consistent colouring properties are maintained. As an example of this in action, Hadamard matrices can be represented by an equivalent graph with a suitable vertex colouring; thus the graph algorithms above make it possible to find canonical forms of Hadamard matrices. This is important for efficient use of the Hadamard matrix database.
Multigraphs further extend to networks, which in this context are directed multigraphs where each edge has associated to it a cost and a capacity. This enables modelling of problems involving flow, where items or information must travel along the network, subject to constraints of cost. The two key problems in this area are maximum flow and minimum cut. In maximum flow, the goal is to determine just how much can travel from one point in the network to another; this includes producing a valid routing of that amount while minimising the associated cost. For minimum cut, on the other hand, the aim is to compute sets of key network edges which must be preserved in order to maintain that rate of flow.
Magma includes two algorithms for solving these problems: The Dinic algorithm and a general push-relabel algorithm. Both have the same theoretical complexity in the general case, but several heuristics (such as those described by Cherkassky and Golberg) are applicable to the general push-relabel algorithm that make it faster in most cases. The exception is the case of very sparse networks in which all edges have the same capacity; in such cases the Dinic algorithm performs better.
These tools find natural application in real world situations wherever networks arise. Examples include freight transportation, traffic planning, communication networks, supply chain management, timetabling, and more. Generally speaking, applying maximum flow enables efficient use of the network, and minimum cut identifies critical components. Both combine to guide expansion of the network in order to obtain larger flows while increasing reliability (such as by adding redundancy for critical paths).
The graph theory machinery is used very widely. Perhaps one of the largest areas of application is to the study of questions in algebraic graph theory. This work is mainly carried out by three groups: The group headed by M. Conder at the University of Auckland, a group based in the Former Republic of Yugoslavia including A. Malnic, D. Marusic and P. Potocnik, and finally the group of C. Praeger at the University of Western Australia.
Other significant applications have been to the factorisation of certain types of graph, and graph theoretic constructions for codes, designs and planes. An application by G. Brown uses a Magma graph as the basis of a database of geometric objects. The Magma profiler also uses the graph theory machinery to manage trees of function calls. Approximately 200 papers have been located that cite Magma for computations in graph theory. Some earlier papers are listed at: