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).
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:
~/WCAGES/wcages10.zip in that directory.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.
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 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).
Choose(S,k,Grp,Check)ChooseNext(S,k,Grp,Check,L)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.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.MBoundP(a,b,g)
Returns the Moore-like lower bound for the order of a
(a,b,g)-wcage.
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)).
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.
GenAll(a,b,g,n)
Returns the list of all (a,b,g)-wgraphs on n vertices. Does
not increment n.
GenOne(a,b,g,n)
Returns one (a,b,g)-wgraph on n vertices, if it exists. Otherwise
returns fail.
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).
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.
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.
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"];.
state recordMany 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 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).
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.
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 --