Choosing and Cages (code and manual)

C.M. de la Cruz and M.A. Pizaña
Version 10. August 5, 2025
License: GPLv3

This is software to compute (d,g)-cages and Choose(S,k,G).

A (d,g)-cage is a d-regular graph of girth g and minimal order.

Choose(S,k,G) is the set of all k-subsets of the set S, up to symmetries in group G, always selecting the minimum element in lexicographic order from each equivalence class under the symmetries in G.

This is also supplementary material for the paper On Cages and Choosing with Symmetries by the same authors (submitted).

Requirements

This software have been tested with Linux 6.8 and macOS 14.7.1, it should also work with Windows+WSL.
Besides that, the following software is also required:

Download

Installation

Test

In a terminal at your working directory, run GAP, then Read("cages.g") and then run a test like Cages(5,5). Sample session:

joe$ gap  
-- some GAP info here --  
gap> Read("cages.g");  
-- some YAGS info here --  
gap> L:=Cages(5,5);  
-- lots of progress data here --

Now L should be the list containing the four (5,5)-cages on 30 vertices.

Troubleshooting

Some installation procedures for nauty produce non-standard names for nauty’s programs. For instance nauty-dreadnaut instead of dreadnaut. It may be necessary to make symbolic links with the standard names for nauty’s programs dreadnaut geng and pickg.

Progress data

Progress data displayed by Cages(d,g) while running looks like this:

V10, dgn: [ 5, 5, 30 ], Suffix: F16TI, Ex: 4, ExG: 6, Datadir: Data10,  
Cases: 17, NodeCount: 1765, NPS: 1128, NumSols: 2,  
ET: 1.56 s, ETC: 20.6 s, ETCR: 20.6 s, Progress: 0.07050999412110523.

These fields have the following meanings:

V10 the version of the software.
dgn the degree, girth and order being considered.
Suffix optimization parameters used in the computation.
Ex the number of excess vertices (the ones exceeding the Moore bound).
ExG the number of excess graphs precomputed using nauty.
Datadir the subdirectory where data files are being stored.
Cases the number of pending cases (graphs) to be analyzed.
NodeCount the number of cases already analyzed.
NPS number of nodes (cases) analyzed per second.
NumSols number of solutions (cages) already found.
ET Elapsed Time.
ETC Estimated Time for Completion based on all cases so far.
ETCR Estimated Time for Completion based on Recently analyzed cases.
Progress fraction of total work done so far.

Main procedures: choosing

  1. Choose(S,k,Grp,Check)
    ChooseNext(S,k,Grp,Check,L)
    In the first form, returns all the k-subsets of the set S up to symmetries in group Grp. The generated k-subsets are always the minimal (in lexicographic order) k-subsets within its equivalent class under the symmetries of Grp. Check() is an optional user-provided procedure used to discard k-subsets whenever they fail to meet additional required conditions. We use this when generating cages for checking the girth condition. If not needed, ReturnTrue may be used in place.

    In its second form computes the k-subsets one at a time. L is a list that used to store the state of the computation, for computing the next k-subset at a later time. To use this form you should initialize a list to the empty list, i.e. L:=[]; and then pass it as a parameter to ChooseNext(S,k,Grp,L). Do not pass the empty list [] directly.

Main procedures: cages

  1. MooreBound(d,g)
    Returns the celebrated Moore lower bound for the order of a (d,g)-cage.

  2. Cages(d,g) and Cages(d,g,n)
    Returns the list of all (d,g)-cages.

    If n is not provided, this procedure starts searching for cages of order n=MooreBound(d,g). If there are no cages of that order, n is incremented and the search continues with the new order. Odd orders n are skipped when d is odd, since it is known that odd regular graphs of odd order do not exist.

    If n is provided the search starts at order max(n,MooreBound(d,g)).

  3. Cage(d,g) and Cage(d,g,n)
    The same as Cages(d,g) and Cages(d,g,n) but only returns the first cage found and stops.

  4. GenAll(d,g,n)
    Returns the list of all (d,g)-graphs on n vertices. Does not increment n.

  5. GenOne(d,g,n)
    Returns one (d,g)-graph on n vertices, if it exists. Otherwise returns fail.

  6. GenAllCases(ListOfCases)
    Calls GenAll() for each of the cases in ListOfCases. This procedure does not return the graphs found, but the corresponding state files are created (see section The state files below).

Main procedures: bounds

  1. BestUpperBound(d,g)
    Returns the best known upper bound for the order of a (d,g)-cage according to:
    G. Exoo and R. Jajcay Dynamic Cage Survey (2013) #DS16.

  2. BestLowerBound(d,g)
    Returns the best known lower bound in the literature for the order of a (d,g)-cage.

  3. BestLowerBoundExplain(d,g)
    Returns a list of all the lower bounds published in the literature for the order of a (d,g)-cage starting with the Moore bound. When there is more than one result in the literature published on the same bound, only the first one is reported. Each item in the list has the format [bound, author(s), year].

  4. OurBestLowerBound(d,g)
    Returns the best lower bound for the order of a (d,g)-cage that we have been able to produce using our algorithms.

  5. OurBestLowerBoundExplain(d,g)
    Returns the full list of lower bounds for the order of a (d,g)-cage that we have been able to produce using our algorithms. Each item has the format (see section Progress Data above): [ dgn, DirectoryAndFileSuffix, NumSols, ET, ETinNanoseconds, Progress, ETC, ETCinNanoseconds]. Since this procedure only considers finished computations, the last three fields are always Progress:=1., ETC:="0. ns" and ETCinNanoseconds:=0.

  6. OurBestPartialResultsExplain(d,g)
    Same as OurBestLowerBoundExplain(d,g), but also includes information about unfinished computations.

  7. UpdateOurData(Dirs)
    Scans the directories in list Dirs and all the state files in them (see section The state files below) to update information about the bounds already computed with our algorithms, affecting the results reported by OurBestLowerBound(d,g), OurBestLowerBoundExplain(d,g) and OurBestPartialResultsExplain(d,g). The files distributed with this software are already scanned and hence, calling this procedure is only necessary when adding additional state files to the data directories. The usual way to call this procedure is UpdateOurData(AllDirs), here AllDirs is a list whose default value is AllDirs:=["DataPrev","Data10u","Data10","Data"];.

The state record

Many of the previous procedures use a global variable state, which is a record, to store the state of the computation in such a way that all relevant information is readily available at all times (for instance within a GAP’s break loop after an interruption with Ctrl-C).

The state record is managed automatically by the procedures above and the user do not usually need to deal directly with it. However, direct access to it is also possible and it allows to access low level features like optimization parameters and data directories. The state record is also used to produce the state files (see next section). Default values for the state record are stored in the state0 record defined in cages.g. The default values for some of the fields are as follows:

state0.Datadir:="Data"; # Subdirectory where state files are stored.
state0.Suffix:=""; #Any string here will be inserted into the state file's name.
state0.useLnewreduce:=false; #Deprecated. Too slow if set to true.
state0.usePrevCons1:=16;  #(=r) use PrevCons1 when (S choose E) < 2^r (method selector).
state0.useexcess:=true; #Precompute excess graphs using nauty's geng and pickg.
state0.useparenttrivial:=infinity; #Always use Automorphism Group to reduce cases.

More detailed information on these and other fields can be found in the file cages.g. It is not recommended to modify other parameters in the state or state0 records.

The state files

The state record is stored once per minute on disc as a state file. In this way, a computation can be continued after an interruption without losing more than a minute of computing time. State files look like this state5.5.30.F16TI.g and are located in the data subdirectories DataPrev, Data10u, Data10 and Data. In the previous state filename, 5.5.30 codifies the values of the variables d, gand nused and F16TI codifies the efficiency parameters which, in this case, are the default values specified in the previous section.

If you want to continue a computation using a state file, you simply start a gap session and read the cages.g, then you read your state file and restart the computation as in the following sample session:

joe$ gap  
-- some GAP info here --  
gap> Read("cages.g");  
-- some YAGS info here --  
gap> Read("Data/state5.5.30.F16TI.g");  #loads state record
gap> Cages(state);  #continues computation
-- lots of progress data here --

Note that state is exactly the name of the global state record and not some other variable name: Reading the state file overwrites the values of the state record. The procedures that can be used in this way are: Cages(rec), Cage(rec), GenAll(rec) and GenOne(rec).

(Known) Bugs

  1. When a computation is restarted using a state file, the elapsed time timer is resumed. However, the elapsed time timer may get corrupted if the computer was turned off and then on between the time of interruption and the time of restart.

  2. Interrupting a computation in GAP 4.14 aborts subprocesses (unlike in GAP 4.10). Hence, when interrupting one of this processes with Ctrl-C our dreadnaut subprocess (which we use to compute automorphisms groups) dies. To restart that subprocess simply call DreadStart(); as in the sample session:

joe$ gap  
-- some GAP info here --  
gap> Read("cages.g");  
-- some YAGS info here --  
gap> L:=Cages(5,5);  
-- lots of progress data here --
------------------------------------------------ Now user types Ctrl-C --
^CError, user interrupt in
  stream![4] := true; at /opt/gap-4.14.0/lib/streams.gi:1553 called from 
ReadAllIoStreamByPty( stream, -1 ) at /opt/gap-4.14.0/lib/streams.gi:1575 called from
ReadAll( dreadstrm ) at isonauty.g:27 called from
DreadAsk( str ) at isonauty.g:76 called from
DreadLoadG( G ); at isonauty.g:289 called from
auto2( G1, r.Part ) at cages.g:441 called from
...  at *stdin*:4
you can 'return;'
brk> quit;
gap> L:=Cages(5,5); ######################################## This won't work now 
V10, dgn: [ 5, 5, 26 ], Suffix: F16TI, Ex: 0, ExG: 0, Datadir: Data, 
Cases: 1, NodeCount: 0, NPS: 0, NumSols: 0, 
ET: 11.8 ms, ETC: --, ETCR: --, Progress: 0..
Error, Child Process 41093 has stopped or died, status 2 in
  WRITE_IOSTREAM( stream![1], text, Length( text ) 
 ) at /opt/gap-4.14.0/lib/streams.gi:1618 called from 
WriteAll( stream, string ) at /opt/gap-4.14.0/lib/streams.gi:320 called from
WriteLine( dreadstrm, str ) at isonauty.g:19 called from
DreadAsk( str ) at isonauty.g:76 called from
DreadLoadG( G ); at isonauty.g:220 called from
Dread( G ); at isonauty.g:253 called from
...  at *stdin*:4
gap> DreadStart();  ######################################## Restart dreadnaut process
gap> L:=Cages(5,5); ######################################## Now this works well
-- lots of progress data here --