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

- GAP 4.14.0
- YAGS 0.0.6
- Nauty&Traces 2.7000

## Downloads

- The web page for this software is here.
- Direct download: wcages10.zip.
- Only wcages in nauty’s .g6 format: wcages.zip
- Only adjacencies of wcages (one per parameter tuple): sample.adj
- Only summary of results (number of solutions, etc.): table.csv (semicolon-separated-values format).

## Installation

- Install GAP
- Install YAGS
- Install nauty
- Create a working directory `~/WCAGES/`
- Unpack `wcages10.zip` in that directory.

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

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

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

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