As mentioned in the Introduction of this chapter it is possible to construct graphs having a sparse representation. That is, graphs which are represented by means of an adjacency list. This has an obvious advantage for graphs with a low edge density, in that it allows to construct much larger graphs than if they were represented by means of an adjacency matrix (the dense representation). See Section Bounds on the Graph Order for more details on this issue.
Another advantage of the sparse representation is for graph algorithms which are linear in the number of edges (the planarity tester and the triconnectivity tester), and more generally, for those algorithms based on the adjacency list representation (the flow-based algorithms and the shortest-paths algorithms). Further, the sparse representation is required when creating multigraphs (see Chapter MULTIGRAPHS) since they may have multiple edges.
A significant number, but not all, of the existing Magma functions have been written for both representations. Should a function designed for a matrix representation of the graph be applied to a graph with a sparse representation, then the graph is automatically converted without any user intervention. This is also true when the reverse conversion is required.
Without being exhaustive, we will list here the functions which can deal with both graph representations without having to perform an (internal) conversion.
The functions in Construction from Groups, Codes and Designs, Distances, Paths and Circuits in a Non-Weighted Graph, Matrices and Vector Spaces Associated with a Graph or Digraph, Directed Trees, Colourings, Cliques, Independent Sets, Automorphism Group of a Graph or Digraph, and Symmetry and Regularity Properties of Graphs deal with a graph as an adjacency matrix.
We emphasize again that should a conversion of the graph's representation take place due to internal specifications, the conversion takes place automatically, that is, without user intervention.
The only problem that may occur is when such a conversion concerns a (very) large graph and thus may possibly result in a lack of memory to create the required representation. This is where users might require control over which internal representation is used so as to minimise the likelihood of both representations coexisting. This is achieved by tuning the creation functions (as described in Section Construction of Graphs and Digraphs), and the following functions which determine the nature of a graph's representation.
When conversion of the graph's representation into the alternative one occurs the original representation is not deleted.
This set of functions determine the nature of a graph's representation.
> G := Graph<5 | { {1,2}, {2,3}, {3,4}, {4,5}, {5,1} }>;
> HasDenseRepOnly(G);
true
> A := AutomorphismGroup(G);
> HasDenseRepOnly(G);
true
The same example using a sparse graph representation:
> G := Graph<5 | { {1,2}, {2,3}, {3,4}, {4,5}, {5,1} } : SparseRep := true>;
> HasSparseRepOnly(G);
true
> A := AutomorphismGroup(G);
> HasDenseAndSparseRep(G);
true
Next the case when the graph's sparse representation remains unchanged:
> G := Graph<5 | { {1,2}, {2,3}, {3,4}, {4,5}, {5,1} } : SparseRep := true>;
> HasSparseRepOnly(G);
true
> IsPlanar(G);
true
> HasSparseRepOnly(G);
true
Finally the same example using a dense graph representation:
> G := Graph<5 | { {1,2}, {2,3}, {3,4}, {4,5}, {5,1} }>;
> HasDenseRepOnly(G);
true
> IsPlanar(G);
true
> HasDenseAndSparseRep(G);
true