A substantial number of algorithms have been implemented for graph theory. Both simple graphs and simple digraphs are supported as well as multigraphs and multidigraphs. In each case vertices and/or edges may be labelled or unlabelled. Graphs may be represented using the adjacency matrix (dense representation), or using an adjacency list (sparse representation). Thus, graphs with millions of vertices may be handled if the sparse representation is used,. The algorithms implemented for graphs are mainly concerned with determining various properties of the graph, such as planarity, and locating important substructures such as cliques. A linear time algorithm is used to test whether a graph is planar. The nauty program developed by B. Mckay is used to compute the automorphism group of a graph and to test whether two graphs are isomorphic.
Besides graphs, flow networks have been implemented. A flow network (or transportation network) is a directed graph where each edge has a capacity associated with it. An edge represents a flow of material between two vertices and the capacity represents the maximal amount of material that can be transported along the edge in some fixed time interval. The fundamental network flow problem is to determine a maximum flow at minimum cost from a specified source to a specified sink. Two sophisticated algorithms for computing the maximum flow are provided: the Dinic algorithm and the push-relabel algorithm; these were improved and implemented by P. Lieby.
Incidence structures arise in various areas of discrete mathematics including in the study of finite groups. A range of related incidence structures including general (finite) incidence structures, near-linear and linear spaces, and t-designs have been implemented in Magma. A particularly useful algorithm provided for incidence structures is a test for t-balance. Other functionality is concerned with searching for resolutions, parallelisms, and parallel classes. An efficient backtrack algorithm developed by W. Unger is provided for computing the automorphism group and for testing pairs of designs for isomorphism.
A structure closely related to block designs is the finite plane. This is separate type in Magma and some geometric tools are provided. Both the affine and projective versions of a plane are available. Finite planes may be constructed over either finite fields or finite nearfields. Some special constructions for finite planes such as Hughes' planes are also provided. Tools for finding substructures such as the Baer subplane and k-arcs are available but much is missing. Again finding the collineation group of a plane and testing planes for isomorphism is performed using the backtrack algorithm mentioned above.
Another structure closely related to t-designs is the Hadamard matrix. The main algorithms implemented are concerned with testing Hadamard matrices for equivalence and for computing their automorphism group. These functions are based on Mckay's nauty program. Associated with equivalence testing is the provision of a function to compute a canonical form for an isomorphism class of Hadamard matrices. A large database of Hadamard matrices is provided.