# 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.

```magma
> 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])));

```

## 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`

```magma
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`

```magma
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](../../references.md#cite-bdm-graph-gen)]). 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`

```magma
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 `Class`th 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`

```magma
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.

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

```

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

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

```

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

```magma
> 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

```

## 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`](#function-graph-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:

```magma
> 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

```

Alternatively one could also drive the graph generation programme (or any other suitable programme for that matter) described in [Generating Graphs](#graph-subsec-generate) 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:

```magma
> 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.

```

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

```magma
> 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

```