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.
A catalogue of strongly regular graphs is available. This catalogue has been put together from various sources by B. McKay and can be found here. 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.
Opens the database of strongly regular graphs.
Returns all the parameter sequences used to index the graphs in the database D.
Returns the number of "classes" of graphs in the database D.
Returns the number of graphs in the database D.
Returns the number of graphs in the database D with parameter sequence S.
Returns (in a sequence) all the graphs in the database D with parameter sequence S.
Returns the ith graph in the database D with parameter sequence S.
Returns a random graph in the database D.
Returns a random graph in the database D with parameter sequence S.
The database of strongly regular graphs may appear as the range in the for-statement.
> 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])));
An enumeration of small graphs with various properties has been created by B. McKay and may be found here. Certain of these databases are available from within Magma: Simple graphs, Eulerian graphs, planar connected graphs, and self-complementary graphs.
IncludeDisconnected: Bool Default: false
Opens the database of simple graphs with n vertices, 2 ≤n ≤10. If the optional parameter IncludeDisconnected is set to true then the database will also include non-connected graphs.
IncludeDisconnected: Bool Default: false
Opens the database of Eulerian graphs with n vertices, 3 ≤n ≤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 ≤n ≤12.
Opens the database of planar connected graphs with n vertices, 2 ≤n ≤11.
Opens the database of self-complementary graphs with n vertices, n ∈{4, 5, 8, 9, 12, 13, 16, 17, 20}. For n = 20 this is not a complete enumeration.
Returns the number of graphs in the database D.
Returns the ith graph in the database D.
Returns a random graph from the database D.
A database of small graphs may appear as the range in the for-statement.
We provide an interface to a graph generation programme, also due to B. McKay (see [McK98]). 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.
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.
FirstGraph: RngIntElt Default: 1Reading of the generated graphs starts at the FirstGraph-th graph.MinEdges: RngIntElt Default:Generate graphs with minimum number of edges MinEdges.MaxEdges: RngIntElt Default:Generate graphs with maximum number of edges MaxEdges.Classes: RngIntElt Default: 1Divide the generated graphs into disjoint Classes classes of very approximately equal size.Class: RngIntElt Default: 1When generated graphs are divided into disjoint Classes classes, write only the Classth class.Connected: BoolElt Default: falseOnly generate connected graphs.Biconnected: BoolElt Default: falseOnly generate biconnected graphs.TriangleFree: BoolElt Default: falseOnly generate triangle--free graphs.FourCycleFree: BoolElt Default: falseOnly generate 4--cycle--free graphs.Bipartite: BoolElt Default: falseOnly generate bipartite graphs.MinDeg: RngIntElt Default:Specify a lower bound for the minimum degree.MaxDeg: RngIntElt Default:Specify an upper bound for the maximum degree.Canonical: BoolElt Default: falseCanonically label output graphs.SparseRep: BoolElt Default: falseIf true, generate the graphs in Sparse6 format (see below).
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 here.
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.
> 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):
> count := 0; > while true do > more := NextGraph(I); > if more then > count +:= 1; > else > break; > end if; > end while; > count; 19If 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
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 here.
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.
> 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 using the OpenGraphFile access function.
The graph generation programme's name is geng (which can be found here) 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.
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