Graphs with a Sparse Representation

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.

-

Nearly all construction functions (Construction of Graphs and Digraphs),

-

All functions in The Vertex--Set and Edge--Set of a Graph, Subgraphs and Quotient Graphs, Incremental Construction of Graphs,

-

Some functions in Constructing Complements, Line Graphs; Contraction, Switching and Unions and Products of Graphs,

-

All functions in Converting between Graphs and Digraphs,

-

The basic invariants and predicates in Elementary Invariants of a Graph and Elementary Graph Predicates,

-

Almost all functions in Adjacency and Degree,

-

All functions in Connectedness in a Graph and all but the last in Connectedness in a Digraph,

-

The functions in Distances, Paths and Circuits in a Possibly Weighted Graph,

-

All functions in Spanning Trees of a Graph or Digraph.

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.

HasSparseRep(G) : Grph -> BoolElt

HasDenseRep(G) : Grph -> BoolElt

HasSparseRepOnly(G) : Grph -> BoolElt

HasDenseRepOnly(G) : Grph -> BoolElt

HasDenseAndSparseRep(G) : Grph -> BoolElt

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

> G := Graph<5 | { {1,2}, {2,3}, {3,4}, {4,5}, {5,1} } : SparseRep := true>;
> HasSparseRepOnly(G);
true
> A := AutomorphismGroup(G);
> HasDenseAndSparseRep(G);
true

> G := Graph<5 | { {1,2}, {2,3}, {3,4}, {4,5}, {5,1} } : SparseRep := true>;
> HasSparseRepOnly(G);
true
> IsPlanar(G);
true
> HasSparseRepOnly(G);
true

> G := Graph<5 | { {1,2}, {2,3}, {3,4}, {4,5}, {5,1} }>;
> HasDenseRepOnly(G);
true
> IsPlanar(G);
true
> HasDenseAndSparseRep(G);
true