[Nauty] new release of nauty

Brendan McKay Brendan.McKay at anu.edu.au
Fri Jul 1 22:52:27 AEST 2022


A new maintenance release of nauty&Traces is available:

https://users.cecs.anu.edu.au/~bdm/nauty/nauty27r4.tar.gz
https://pallini.di.uniroma1.it/nauty27r4.tar.gz

You are also invited to try the current beta version:

https://users.cecs.anu.edu.au/~bdm/nauty/nauty28b4.tar.gz
https://pallini.di.uniroma1.it/nauty28b4.tar.gz

Traces is not changed in this release.  The changes from 2.7r3
to 2.7r4 are these:

* Fixed an obscure bug in multig that might occur if the input
   graph has loops. No example of incorrect behaviour is known.

* multig has a new option -V that lets it read the -T outout of
   vcolg. Also, the output code has been made faster.
   A crash caused by the combination of -V and the INPUTGRAPH
   hook was fixed. New input hooks INPUTGRAPHC and OUTPROCC
   designed for use with -V were added.

* Fixed help text for -s and -S in pickg and countg

* Corrected argument parsing for genspecialg -T

* Fixed a problem with watercluster2 and the clang compiler.
   Note: right shift by the word size is undefined, and as an
   example BITMASK(WORDSIZE) is erroneous. The argument of
   BITMASK must be 0..WORDSIZE-1. Thanks to Enrico Porreca
   for reporting this.

The features of version 2.8 beta4 that are not in 2.7r4 are:

* 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
   As always, delptg --help gives details.

* gtnauty.c has a new procedure breakcellwt() to split a cell
   according to weights on the vertices

* directg has a new option -a for acyclic orientations

* Extra arguments can be added at compile time to the sort
   command run by shortg.  See EXTRA in shortg.c.

* 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.

* 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.

* gutil1.c has a procedure numcomponents(g,m,n) for counting
   the components of an undirected graph.

* gutil2.c has a procedure digoncount(g,m,n) that counts how
   many cycles of length 2 a digraph has. It also has a procedure
   numind3sets1(g,n) for counting independent sets of size 3,
   so far only for n <= WORDSIZE.

* countg/pickg now have an exanded set of available properties,
   using double letters. For example: -L is for loops, while
   -LL is for 2-cycles (of digraphs).
   Similarly -cc counts components.
   -ee counts edges in the complement (including loops in the
   case of digraphs, while -TT counts independent sets of size 3.
   Because --eee and similar are ambiguous, options can be
   separated by commas: --e,ee or --ee,e.

* 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 used in recent Macs.

* The new utility addptg adds additional vertices, with a
   choice of simple ways to connect them to the input graph.

Cheers, Brendan and Adolfo.


More information about the Nauty mailing list