[Nauty] Nauty & Traces 2.7r1 is now the official release
Brendan McKay
Brendan.McKay at anu.edu.au
Wed May 20 15:53:11 AEST 2020
Nauty & Traces 2.7 (release 1) is now the official release.
All versions up to and including 2.6 are now obsolete.
Please see
https://users.cecs.anu.edu.au/~bdm/nauty/
<https://users.cecs.anu.edu.au/~bdm/nauty/>
https://pallini.di.uniroma1.it/ <https://pallini.di.uniroma1.it/>
for download links and documentation.
Appended below is a summary of the principle changes from 2.6 to 2.7.
As always, please report any problems to us.
Brendan McKay and Adolfo Piperno.
============================================
* -h and -k options for independent set size and clique size were added
to countg and pickg. For some graphs these use the program cliquer,
kindly provided by Sampo Nisjkanen and Patric Ostergard.
* Macros SWHIBIT, REMOVEHIBIT and ATMOSTONEBIT added to nauty.h.
* Added option -a to complg.
* Program copyg can now be used to make a simple filter. See the
instructions inside the source file and the example numleaves.c.
* Programs countg and pickg can now display some parameter values
as ranges instead of writing a separate line for each value. For
example, countg --ne:T will write a separate line for each number
of vertices and edges, with that line showing the range of the
number of triangles. Everything after the ':' is shown as a range.
There is also a switch -1 that causes output to be in a simple
numerical table easy to read from a program and a similar switch
-2 that omits counts.
* Program vcolg now handles digraphs and graphs with loops.
* genrang can now make random spanning trees of K(n1,n2)
* amtog has an "s" command for reading tournaments
* gentreeg made the same tree twice for n=2; thanks to Kevin Ryde
for reporting it.
* The configure script (compiled from configure.ac) was modified to
update some tests and remove some old code that is useless. The
time-critical parts of nauty are now compiled with
-march=native
if the compiler allows those switches. Since this may result in
a binary which does not run on older machines in the same family,
there is a configuration option --enable-generic to disable
these switches. To work around a bug with -march-native for
gcc version 7 on MacOSX computers (due to the linker not knowing
some of the instructions), the extra switch -mno-avx is also added
if it appears necessary.
* genspecialg can now make multiple special graphs at once.
The -b option has been extended to allow removing a matching from
a complete bipartite graph.
* watercluster2 has an option Z to write in digraph6 format.
* Problems for input of graphs with 0 vertices were fixed with help
from Kevin Ryde. However, note that many utilities in the package
will not work with such graphs. It is NOT TRUE that graphs of
order 0 are now supported. However, the primary function nauty()
(but not traces()) should work for both dense and sparse versions.
* Stronger measures are taken to ensure that the sort order used by
shortg is plain byte order. This corresponds to the C collation
order, also known as POSIX, but it may be different from the
collation order used by default on your command line. This means
that utilities like sort, uniq, comm and join might consider the
output of shortg to be out of order. To avoid this, define the
environment variable LC_ALL to equal the string "C".
bash: export LC_ALL=C
tcsh: setenv LC_ALL C
If LC_ALL is undefined, it will also be sufficient to define
LC_COLLATE to equal "C". The POSIX standard says that LC_ALL
takes precedence over LC_COLLATE if both are defined, but this
might not be true for older systems. If you really don't want
to change environment variables, you can compile shortg with
-DKEEP_SORT_LOCALE but beware that some collation orders are
are not even deterministic (i.e. different characters might
compare equal).
* The bipartite graph generator genbg now has a -Y switch to
specify the minimum number of common neighbours for two
vertices on the second side.
* A new version of Traces (including some bug fixes) is included.
See traces.c for more.
* New utilities: underlyingg takes the undirected graph underlying
a graph or digraph. assembleg combines a file of graphs (usually
connected graphs) as components to make disconnected graphs
of a specified size.
* geng has been modified to allow more than 32 vertices. The
makefile knows "geng" for up to 32 vertices, and "gengL" for
up to 64 vertices.
* pickg and countg now have -X to reverse the selection.
A change was made to allow these utilities to work on Windows
computers with sizeof(long) < sizeof(void*). Also, pickg
now writes a header if there is one in the input file.
* listg has -L that can be used in conjunction with -W or -M to
write the Laplacian matrix instead of the adjacency matrix.
* Fixed a possible bug in the combination "shortg -kt".
* You can change the archive manager (default "ar") by defining
the environment variable AR at configure time.
* Some portability issues in nautycliquer.c were fixed (thanks
to Isuru Fernando).
* The -B/--B switch of listg/countg is now isomomorphism-invariant.
It equals 0 for non-bipartite graph, and the smallest possible
side of a 2-colouring otherwise. This change reflects rewriting
of function bipartiteside() in gutil1.c. The values can differ
from those for nauty version <= 2.7rc1 when there are three or
more components.
* Fixed the type of the 4th parameter of options.usercanonproc.
* Check kill requests more often. If the global int variable
nauty_kill_request becomes nonzero, nauty and Traces will
exit at certain key points. In dreadnaut nauty_kill_request
is set if the user types control-C (if the operating system
provides this facility).
* nauty.h loads <limits.h> and <stdint.h> if they exist.
* Some features were added to assist installation on non-POSIX
systems or where 'configure' can't be easily run, such as
Microsoft Visual Studio. These changes are mostly in nauty.h.
1. The predefined names _MSC_VER, _WIN32 and _WIN64 are examined.
2. HAVE_HWLZCNT and HAVE_HWPOPCNT can be defined at compile time
(to 0 or 1) to indicate the presence of hardware lzcnt and
popcnt instructions.
3. The FIRSTBITNZ, FIRSTBIT and POPCOUNT macros can be defined
at compile time (though it is unlikely you will be able to do
much better than the default versions). FIRSTBIT is defined
in terms of FIRSTBITNZ if it isn't defined separately.
4. Loading of unavailable header files can be disabled by
predefining macros: AVOID_SYS_TYPES_H, AVOID_UNISTD_H,
AVOID_STRINGS_H and AVOID_SYS_WAIT_H.
There is more to do here; there are lots of variations in
different software versions and documentation is inconsistent.
Thanks to Andy Mercier for discussions so far.
* Bug fixed in directg that caused crash when digraphg6 output
was selected for more than WORDSIZE vertices.
* The external variables labelorg and nauty_kill_request were
moved into the "C" block of nauty.h for C++ compatibility.
* Identical BUGS in naugraph.c and sparsegraph.c.
The static sizes of dnwork[] and snwork[] were too small.
This bug first crept into version 2.6 beta 10. To meet this
bug, all of the following must be true:
(a) called densenauty() or sparsenauty() rather than calling
nauty() directly.
(b) processed graphs with 20 or more vertices.
(c) compiled naugraph.c or sparsegraph.c with an explicit
value of MAXN, rather than the default MAXN=0.
This includes using the libraries nauty1.a, nautyW1.a
or nautyL1.a. However nauty.a, nautyW.a and nautyL.a
were safe. Likewise, the utilities distributed with
nauty were also safe.
Thanks to James Trimble and Chris Jefferson for uncovering this.
Versions 2.6r12 and 2.7rc5 were fixed.
* A bug in nauty.h caused compilation failure on some hardware
without popcnt instructions. You didn't encounter this if you
didn't get compile-time error messages about POPCOUNT. Thanks
to Anthony Matos for reporting this error.
* Tweak the configure script to more reliably detect standard
function declarations and to improve the test for the POPCNT
instruction.
* Don't define INFINITY even if it isn't defined in math.h.
Note that nauty's infinity is NAUTY_INFINITY and plain
INFINITY is a required macro in the C standard.
* A bug prevented a filtering version of copyg (needs special
compilation, see copyg.c) from playing nice with incremental
sparse6 input. You didn't meet this bug unless you saw an
error message like "readg_inc: missing prior".
More information about the Nauty
mailing list