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.
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])));
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: 1
Reading 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: 1
Divide the generated graphs into disjoint Classes classes
of very approximately equal size.
Class: RngIntElt Default: 1
When generated graphs are divided into disjoint Classes classes,
write only the Classth class.
Connected: BoolElt Default: false
Only generate connected graphs.
Biconnected: BoolElt Default: false
Only generate biconnected graphs.
TriangleFree: BoolElt Default: false
Only generate triangle--free graphs.
FourCycleFree: BoolElt Default: false
Only generate 4--cycle--free graphs.
Bipartite: BoolElt Default: false
Only 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: false
Canonically label output graphs.
SparseRep: BoolElt Default: false
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
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.
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
> );
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
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
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.
As an example one could download one of the files found
here.
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
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
[Next][Prev] [Right] [Left] [Up] [Index] [Root]