Graph Databases and Graph Generation

Magma provides interfaces to some databases of certain graphs of interest. These databases are not provided by default with Magma, but may be downloaded from the optional databases section of the Magma website.

Strongly Regular Graphs

A catalogue of strongly regular graphs is available. This catalogue has been put together from various sources by B. McKay and can be found at

http://cs.anu.edu.au/~bdm/data/

Graphs in the database are indexed by a sequence of four parameters. They are, in order: the order of the graph, its degree, the number of common neighbours to each pair of adjacent vertices, and the number of common neighbours to each pair of non-adjacent vertices.

StronglyRegularGraphsDatabase() -> DB

Opens the database of strongly regular graphs.

Classes(D): DB -> SeqEnum

Returns all the parameter sequences used to index the graphs in the database \(D\).

NumberOfClasses(D): DB -> RngIntElt

Returns the number of “classes” of graphs in the database \(D\).

NumberOfGraphs(D): DB -> RngIntElt

Returns the number of graphs in the database \(D\).

NumberOfGraphs(D, S): DB, SeqEnum -> RngIntElt

Returns the number of graphs in the database \(D\) with parameter sequence \(S\).

Graphs(D, S): DB, SeqEnum -> SeqEnum

Returns (in a sequence) all the graphs in the database \(D\) with parameter sequence \(S\).

Graph(D, S, i): DB, SeqEnum, RngIntElt -> GrphUnd

Returns the \(i\)th graph in the database \(D\) with parameter sequence \(S\).

RandomGraph(D): DB -> GrphUnd

Returns a random graph in the database \(D\).

RandomGraph(D, S): DB, SeqEnum -> GrphUnd

Returns a random graph in the database \(D\) with parameter sequence \(S\).

for G in D do ... end for;

The database of strongly regular graphs may appear as the range in the for-statement.

Example: Strongly Regular Graphs (ex-a88364)

The following few statements illustrate the basic access functions to the database of strongly regular graphs.

> D :=  StronglyRegularGraphsDatabase();
> Cs := Classes(D);
> Cs;
[
  [ 25, 8, 3, 2 ],
  [ 25, 12, 5, 6 ],
  [ 26, 10, 3, 4 ],
  [ 27, 10, 1, 5 ],
  [ 28, 12, 6, 4 ],
  [ 29, 14, 6, 7 ],
  [ 35, 16, 6, 8 ],
  [ 35, 14, 4, 6 ],
  [ 36, 15, 6, 6 ],
  [ 37, 18, 8, 9 ],
  [ 40, 12, 2, 4 ]
]
> assert NumberOfClasses(D) eq #Cs;
> 
> NumberOfGraphs(D);
43442
> 
> for i in [1..#Cs] do
>     NumberOfGraphs(D, Cs[i]);
> end for;
1
15
10
1
4
41
3854
180
32548
6760
28
> 
> gs := Graphs(D, Cs[2]);
> 
> g :=  Graph(D, Cs[2], Random(1, NumberOfGraphs(D, Cs[2])));

Run in calculatorCopy input

Small Graphs

An enumeration of small graphs with various properties has been created by B. McKay and may be found at

http://cs.anu.edu.au/~bdm/data/graphs.html

Certain of these databases are available from within Magma: Simple graphs, Eulerian graphs, planar connected graphs, and self-complementary graphs.

Creation of Small Graph Databases

SmallGraphDatabase(n : parameters): RngIntElt -> DB

IncludeDisconnected: Bool                    Default: false

Opens the database of simple graphs with \(n\) vertices, \(2 \leq n \leq 10\). If the optional parameter IncludeDisconnected is set to true then the database will also include non-connected graphs.

EulerianGraphDatabase(n : parameters): RngIntElt -> DB

IncludeDisconnected: Bool                    Default: false

Opens the database of Eulerian graphs with \(n\) vertices, \(3 \leq n \leq 11\). If the optional parameter IncludeDisconnected is set to true then the database will also include non-connected graphs. The allowed range of \(n\) for non-connected graphs is \(2 \leq n \leq 12\).

PlanarGraphDatabase(n): RngIntElt -> DB

Opens the database of planar connected graphs with \(n\) vertices, \(2 \leq n \leq 11\).

SelfComplementaryGraphDatabase(n): RngIntElt -> DB

Opens the database of self-complementary graphs with \(n\) vertices, \(n \in \{4, 5, 8, 9,\) \(12, 13, 16, 17, 20\}\). For \(n = 20\) this is not a complete enumeration.

Access functions

# D: DB -> RngIntElt

Returns the number of graphs in the database \(D\).

Graph(D, i): DB, RngIntElt -> GrphUnd

Returns the \(i\)th graph in the database \(D\).

Random(D): DB -> GrphUnd

Returns a random graph from the database \(D\).

for G in D do ... end for;

A database of small graphs may appear as the range in the for-statement.

Generating Graphs

We provide an interface to a graph generation programme, also due to B. McKay (see [McKay, 1998]). For the time being, users wanting to benefit from this facility must download the generation programme themselves directly from

http://cs.anu.edu.au/~bdm/nauty/

Important restriction: Since this program runs within a Unix pipe it is only available to users running Magma on a Unix platform.

And a note of caution: When the graph generation programme is used to generate reasonably large graphs (\(n > 17\)) it can be observed that the procedure of closing down the pipe (ie. closing the stream) may take some time. This will happen when the closing down attempt is made before the programme has completed the generation of all the graphs.

GenerateGraphs(n : parameters): RngIntElt -> IO

FirstGraph   : RngIntElt                    Default: 1
MinEdges     : RngIntElt                    Default: 
MaxEdges     : RngIntElt                    Default: 
Classes      : RngIntElt                    Default: 1
Class        : RngIntElt                    Default: 1
Connected    : BoolElt                      Default: false
Biconnected  : BoolElt                      Default: false
TriangleFree : BoolElt                      Default: false
FourCycleFree: BoolElt                      Default: false
Bipartite    : BoolElt                      Default: false
MinDeg       : RngIntElt                    Default: 
MaxDeg       : RngIntElt                    Default: 
Canonical    : BoolElt                      Default: false
SparseRep    : BoolElt                      Default: false

Opens a pipe to the graph generation programme to generate all graphs of order \(n\). Only available on Unix platforms.

The GenerateGraphs intrinsic allows the user to drive the generation programme via a set of parameters. These parameters are described below.

Once the generation programme has been downloaded from

http://cs.anu.edu.au/~bdm/nauty/

and compiled (using make geng), the resulting executable (named geng – it is compulsory that the resulting executable’s name be geng) can be placed anywhere in the user’s directory tree. The environment variable MAGMA_NAUTY must then be set to the path where the executable/command geng is to be found.

Reading of the generated graphs starts at the FirstGraph-th graph.

Generate graphs with minimum number of edges MinEdges.

Generate graphs with maximum number of edges MaxEdges.

Divide the generated graphs into disjoint Classes classes of very approximately equal size.

When generated graphs are divided into disjoint Classes classes, write only the Classth class.

Only generate connected graphs.

Only generate biconnected graphs.

Only generate triangle–free graphs.

Only generate \(4\)–cycle–free graphs.

Only generate bipartite graphs.

Specify a lower bound for the minimum degree.

Specify an upper bound for the maximum degree.

Canonically label output graphs.

If true, generate the graphs in Sparse6 format (see below).

NextGraph(I: parameters): IO -> BoolElt, GrphUnd

SparseRep: Bool                    Default: false

Returns true if and only if I/O object \(I\) is not at the end of input. In this case the next graph is returned as well.

The graphs in \(I\) must be in either of the output formats Graph6 or Sparse6. Details on the Graph6 and Sparse6 format can be found at

http://cs.anu.edu.au/~bdm/data/formats.html

If SparseRep is true then the resulting graph will have a sparse representation. This of course is of special interest if the graphs read from \(I\) are also in Sparse6 format.

Example: Graph Generation (ex-56c803)

The following statements should help clarify the usage of the graph generation programme.

> I := GenerateGraphs (12:
>     FirstGraph:= 10,
>     Connected:= true,
>     Biconnected:= true,
>     TriangleFree:= true,
>     FourCycleFree:= true,
>     Bipartite:= true,
>     MinDeg:= 1,
>     MaxDeg:= 9
> );

Run in calculatorCopy input

We’ll read all the graphs from the 10th graph onwards (one can check that 28 graphs have been generated):

> count := 0;
> while true do
>     more := NextGraph(I);
>     if more then
>       count +:= 1;
>     else
>       break;
>     end if;
> end while;
> count;
19

Run in calculatorCopy input

If one wants to work with sparse graphs, it is recommended to proceed as follows:

> I := GenerateGraphs (6: SparseRep := true);
> count := 0;
> while true do
>     more := NextGraph(I: SparseRep := true);
>     if more then
>       count +:= 1;
>     else
>       break;
>     end if;
> end while;
> count;
156

Run in calculatorCopy input

A General Facility

In order to give users more flexibility in dealing with certain graph files the intrinsic OpenGraphFile is provided. It allows one to open either a graph file or a pipe to a graph generation programme. Since in both cases (file or Unix pipe) the outcome is the access to a stream of graphs, we henceforth refer to the graphs to be read as a graph stream.

The usual restriction: The OpenGraphFile which opens a pipe is only available to users running Magma on a Unix platform.

Accessing and reading the graph stream: Reading the graph stream is achieved by the above described access function NextGraph. As mentioned there, the graphs in the graph stream must be in either of the output formats Graph6 or Sparse6. This is why OpenGraphFile is restricted to streams of graphs in format Graph6 or Sparse6.

Details on the Graph6 and Sparse6 format can be found at

http://cs.anu.edu.au/~bdm/data/formats.html.

OpenGraphFile(s, f, p): MonStgElt, RngIntElt, RngIntElt -> IO

Opens a graph file or pipe at position \(p\). If the stream to be opened is a Unix pipe then the string \(s\) must have the format “cmd command” where command stands for the command to run including necessary parameters. If the stream to be opened is a file the string \(s\) has format “filename”.

The integer \(f\) indicates that the record length is fixed, which is true for streams in Graph6 format with every graph having the same order. This permits rapid positioning to position \(p\) in that case. If in doubt, use \(f = 0\). Also, positioning to 0 or positioning to 1 has the same effect of positioning to the start of the stream.

Opening a pipe is only available on Unix platforms. The I/O object \(I\) must contain graphs in Graph6 and Sparse6 format.

Example: Graph General Access (ex-49cbde)

As an example one could download one of the files found at

http://cs.anu.edu.au/~bdm/data/

Assuming this has been done, one can then proceed to read the graphs in the file:

> I := OpenGraphFile("/home/paule/graph/bdm_data/sr251256.g6", 0, 0);
> 
> count := 0;
> more, g := NextGraph(I);
> while more do
>    count +:= 1;
>    more, g := NextGraph(I);
> end while;
> count;
15

Run in calculatorCopy input

Alternatively one could also drive the graph generation programme (or any other suitable programme for that matter) described in Generating Graphs using the OpenGraphFile access function.

The graph generation programme’s name is geng (which can be found at

http://cs.anu.edu.au/~bdm/nauty/)

and has a help facility:

> I := OpenGraphFile("cmd /home/paule/graph/bdm_pgr/nauty/geng -help", 0, 0);

Usage: geng [-cCmtfbd#D#] [-uygsnh] [-lvq] [-x#X#] n [mine[:maxe]] [res/mod]
[file]

 Generate all graphs of a specified class.

      n    : the number of vertices (1..32)
 mine:maxe : a range for the number of edges
              #:0 means '# or more' except in the case 0:0
   res/mod : only generate subset res out of subsets 0..mod-1

     -c    : only write connected graphs
     -C    : only write biconnected graphs
     -t    : only generate triangle-free graphs
     -f    : only generate 4-cycle-free graphs
     -b    : only generate bipartite graphs
                (-t, -f and -b can be used in any combination)
     -m    : save memory at the expense of time (only makes a
                difference in the absence of -b, -t, -f and n <= 30).
     -d#   : a lower bound for the minimum degree
     -D#   : a upper bound for the maximum degree
     -v    : display counts by number of edges
     -l    : canonically label output graphs

     -u    : do not output any graphs, just generate and count them
     -g    : use graph6 output (default)
     -s    : use sparse6 output
     -y    : use the obsolete y-format instead of graph6 format
     -h    : for graph6 or sparse6 format, write a header too

     -q    : suppress auxiliary output (except from -v)

  See program text for much more information.

Run in calculatorCopy input

Finally, here is a typical run of this graph generation programme:

> I := OpenGraphFile(
> "cmd /home/paule/graph/bdm_pgr/nauty/geng 15 -cCtfb -v", 0, 0);
>A geng -Ctfbd2D14 n=15 e=15-22
>C 4 graphs with 16 edges
>C 45 graphs with 17 edges
>C 235 graphs with 18 edges
>C 294 graphs with 19 edges
>C 120 graphs with 20 edges
>C 13 graphs with 21 edges
>C 1 graphs with 22 edges
>Z 712 graphs generated in 1.38 sec

Run in calculatorCopy input