[Nauty] Announcing nauty and Traces version 2.8.6
Brendan McKay
Brendan.McKay at anu.edu.au
Thu Nov 17 14:34:16 AEDT 2022
This is a major release of nauty and Traces. Please report any problems
to us.
As usual, the files can be downloaded from these places:
https://users.cecs.anu.edu.au/~bdm/nauty/
https://pallini.di.uniroma1.it
Good luck! Brendan & Adolfo.
Changes from nauty 2.7 to nauty 2.8.6
-----------------------------------
* New utilities: (as always, use --help to get help)
- addptg : add additional vertices in various ways
- ancestorg : removes a specified number of final vertices
- productg : product of two graphs (such as Cartesian product)
- genposetg : generate posets (mostly written by Gunnar Brinkmann)
- dimacs2g : read files of graphs in DIMACS format
* Changes to existing utilities:
- geng got sigificantly faster for connected graphs with a
small number of edges. However, if you want trees the program
gentreeg is still much faster. There are also new options:
-k generate graphs without K4
-T generate chordal graphs
-S generate split graphs
-P generate perfect graphs
-F generate claw-free graphs
All the options can be used in combination unless the program
complains.
There is a program callgeng2.c that shows how geng can be
called in multiple threads. Read the instructions at the
start of the source file. It has a target in the makefile but
it might not work with all operating systems and compilers.
- countg/pickg now have an expanded set of available properties,
using double letters. Because --eee and similar are ambiguous,
options can be separated by commas: --e,ee or --ee,e.
Here are all the options added since version 2.7:
-LL 2-cycles (of digraphs)
-ee non-edges (including non-loops for digraphs)
-TT independent sets of size 3
-x sources
-xx sinks
-W 4-cycles (undirected only so far)
-WW diamonds (4-cycles with diagonal), only undirected
- gentreeg now allows a range of number of vertices.
Example: forests on 15 vertices with no isolated vertices:
gentreeg 2:15 | assembleg -n15cL
Also new option -i for no vertices of degree 2.
Fixed output for n=1, diameter > 0.
- genrang has an option -M# can be used in conjunction with
-d (pseudo-random regular graphs). It runs a Markov chain
for #*n steps. The chain has a uniform distribution as
its limit and, although the precise rate of convergence
is unknown, running it with a decent number of iterations
will produce a more uniform distribution than -d alone.
- listg has a new option -S for use with -M or -W to write
the signless Laplacian.
- subdivideg now works for digraphs.
- delptg has several new options:
-v select which vertices to delete
-m lower bound on minimum degree of output graphs
-a delete a clique
-b delete an independent set
-i leave vertices as isolates rather than removing them
-r delete a random set of vertices
- multig has a new option -V that lets it read the -T outout of
vcolg. Also, the output code has been made faster.
- vcolg has new options bounding the number of vertices of each
colour and bounding the vertex degrees for each colour. Also
the output code has been made faster.
- directg has a new option -a for acyclic orientations
* New functions
- gutil1.c has new procedures:
numcomponents(g,m,n) for counting the components of an
undirected graph, and
sources_sinks(g,m,n,*sources,*sinks) for counting sources
and sinks in digraphs.
- gutil2.c has new procedures:
digoncount(g,m,n) that counts how many cycles of length 2
a digraph has.
numind3sets1(g,n) for counting independent sets of size 3,
so far only for n <= WORDSIZE.
numsquares(g,m,n) counts 4-cycles in undirected graphs.
- gtnauty.c has a new procedure
breakcellwt() to split a cell according to weights on the
vertices
- naututil.c has new procedures
settolist() for converting a set into a list of integers
listtoset() for converting a list of integers into a set
Functions nextelement(), permset(), setsize(), setinter(),
settolist() and listtoset() now work for multi-word sets
even if nauty is compiled with MAXN=WORDSIZE.
* Miscellaneous
- The default "make" now creates the 16-bit libraries nautyS.a
and nautyS1.a. There are new targets for making thread-enabled
libraries nautyT.a, nautyT1.a, nautyTW.a, nautyTW1.a,
nautyTL.a and nautyTL1.a; these are not built by "make all".
- The compiler switch -march=native is omitted if the build is
for Alpine Linux. This is due to a problem with the compiler
issuing illegal instructions. Thanks to Gordon Royle for
helping with this.
- Changes were made to the configure script and nauty.h to
support ARM64 (aarch64) architecture. So far this is only
tested on the Apple M1 architecture.
- Bugs were fixed in multig (if multiple edges were present,
also combination of -V and the INPUTGRAPH hook),
genspecialg (argument parsing for -T), pickg/countg (help
text for -s,-S), and watercluster2 (shifting right by the
wordsize is undefined! This only effected clang.)
- Programs that use randomisation now initialise the random
generator from the high-resolution realtime clock if possible.
Specifically, it uses the first available of gettimeofday(),
clock_gettime() and time(). This makes it much less likely
that processes started close together will use the same seed.
- The proceedure gtools_getline() in gtools.c, which is used by
most utilities for reading graphs, is now faster except for
for very small graphs.
* A new version of Traces is included, that fixes a bug reported
by Aleksandr Krotov and makes other improvements. A side-effect
is that the canonical labelling made by Traces has changed.
* Nauty now uses a more standard version numbering system such as
2.8.6. Corrections will be made to the most recent version only,
and beta versions will be released only rarely.
More information about the Nauty
mailing list