Weighted Cages (code and manual)

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

This is software to compute (a,b,g)-wcages.

A weighted graph (wgraph) is a graph with weights assigned to the edges. Here we consider only weights 1 and 2. Hence, a wgraph G can be represented as a pair of graphs G=(L,H) where L is the subgraph of G induced by light edges (weight 1) and H is the subgraph of G induced by the heavy edges (weight 2). We require that V(G)=V(L)=V(H), Intersection(E(L),E(H)) = emptyset and Union(E(L),E(H))= E(G). The weight of a cycle is the sum of the weights of its edges. The weighted girth of G is the minimum weight of a cycle in G.

An (a,b,g)-wcage is a weighted graph G=(L,H) where L is a-regular, H is b-regular, the weighted girth of G is g, and G is of minimum order subject to those restrictions.

This is also supplementary material for the paper Weighted Cages, Discrete Applied Mathematics 384 (2026) 293-308. (doi, author version) by a superset of the above authors.

This software is an adaptation of the code developed for (normal) cages as a supplementary material for the paper On cages and choosing with symmetries, The Electronic Journal of Combinatorics 33 (2026) P1.54. ( doi).

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:

Downloads

Installation

Test

In a terminal at your working directory, load GAP, then Read("wcages.g") and then run a test like WCages(2,2,7). Sample session:

joe$ gap  
-- some GAP info here --  
gap> Read("wcages.g");  
-- some YAGS info here --  
gap> L:=WCages(2,2,7);  
-- lots of progress data here (about 10 minutes) --

Now L should be a list containing the three (2,2,7)-wcages on 19 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 WCages(a,b,g) while running looks like this:

V10, abgn: [ 2, 2, 7, 19 ], Suffix: F16FI, Ex: 0, ExG: 0, Datadir: Data, 
Cases: 13, NodeCount: 4302, NPS: 253, NumSols: 3, 
ET: 17.2 s, ETC: 1.07 min, ETCR: 1.63 min, Progress: 0.2108910608139003.

These fields have the following meanings:

V10 the version of the software.
abgn the degrees, girth and order being considered.
Suffix optimization parameters used in the computation.
Ex the number of excess vertices.
ExG the number of excess wgraphs precomputed using nauty.
Datadir the subdirectory where data files are being stored.
Cases the number of pending cases (wgraphs) to be analyzed.
NodeCount the number of cases already analyzed.
NPS number of nodes (cases) analyzed per second.
NumSols number of solutions (wcages) 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.

Note: Ex and ExG are zero unless state0.useexcess is activated (not recommended, see section The state record below).

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 wcages 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 is 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: wcages

  1. MBoundP(a,b,g)
    Returns the Moore-like lower bound for the order of a (a,b,g)-wcage.

  2. WCages(a,b,g) and WCages(a,b,g,n)
    Returns the list of all (a,b,g)-wcages.

    If n is not provided, this procedure starts searching for wcages of order n=MBoundP(a,b,g). If there are no wcages of that order, n is incremented and the search continues with the new order. Odd orders n are skipped when a or b 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,MBoundP(a,b,g)).

  3. WCage(a,b,g) and WCage(a,b,g,n)
    The same as WCages(a,b,g) and WCages(a,b,g,n) but only returns the first wcage found and stops.

  4. GenAll(a,b,g,n)
    Returns the list of all (a,b,g)-wgraphs on n vertices. Does not increment n.

  5. GenOne(a,b,g,n)
    Returns one (a,b,g)-wgraph 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 wgraphs found, but the corresponding state files are created (see section The state files below).

Main procedures: bounds

  1. OurBestLowerBound(a,b,g)
    Returns the best lower bound for the order of an (a,b,g)-wcage that we have been able to produce using our algorithms.

  2. OurBestLowerBoundExplain(a,b,g)
    Returns the full list of lower bounds for the order of a (a,b,g)-wcage that we have been able to produce using our algorithms. Each item has the format (see section Progress Data above): [ abgn, DirectoryAndFileSuffix, NumSols, ET, ETinNanoseconds, Progress, ETC, ETCinNanoseconds]. Finished computations have the last three fields as follows: Progress:=1., ETC:="0. ns" and ETCinNanoseconds:=0.

  3. 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(a,b,g) and OurBestLowerBoundExplain(a,b,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:=["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 wcages.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 wgraphs 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 wcages.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 state2.2.7.19.F16TI.g and are located in the data subdirectories Data10 and Data. In the previous state filename, 2.2.7.19 codifies the values of the variables a, b, g and n used and F16FI 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 wcages.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("wcages.g");  
-- some YAGS info here --  
gap> Read("Data/state2.2.7.19.F16TI.g");  #loads state record
gap> WCages(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: WCages(rec), WCage(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 automorphism groups) dies. To restart that subprocess simply call DreadStart(); as in the sample session:

joe$ gap  
-- some GAP info here --  
gap> Read("wcages.g");  
-- some YAGS info here --  
gap> L:=WCages(2,2,7);  
-- lots of progress data here --
------------------------------------------------ Now user types Ctrl-C --
^CError, user interrupt in
  bn[i] := NAME_FUNC( FILTERS[bn[i]] ); at /opt/gap-4.14.0/lib/filter.g:450 called from 
NamesFilter( x ) at /opt/gap-4.14.0/pkg/yags/lib/kernel.gi:46 called from
func( elm ) at /opt/gap-4.14.0/lib/list.gi:2885 called from
First( AvailableGraphCategories, function ( x )
      return NamesFilter( x )[1] in ctgs;
  end ) at /opt/gap-4.14.0/pkg/yags/lib/kernel.gi:46 called from
CallFuncList( GraphCategory, arg ) at /opt/gap-4.14.0/pkg/yags/lib/kernel.gi:61 called from
TargetGraphCategory( G ) at /opt/gap-4.14.0/pkg/yags/lib/kernel.gi:797 called from
...  at *stdin*:7
you can 'return;'
brk> quit;
gap> L:=WCages(2,2,7); ######################################## This won't work now 
V10, abgn: [ 2, 2, 7, 17 ], Suffix: F16FI, Ex: 0, ExG: 0, Datadir: Datatest, 
Cases: 1, NodeCount: 0, NPS: 0, NumSols: 0, 
ET: 11.3 ms, ETC: --, ETCR: --, Progress: 0..
Error, Child Process 74452 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:265 called from
auto2( G, r.Part ) at wcages.g:422 called from
...  at *stdin*:10
gap> DreadStart();  ######################################## Restart dreadnaut process
gap> L:=WCages(2,2,7); ######################################## Now this works well
-- lots of progress data here --