[Nauty] Announcing new edition of nauty&Traces

Brendan McKay Brendan.McKay at anu.edu.au
Sat Feb 27 23:39:35 AEDT 2016

We are pleased to announce the first official release of nauty version 
2.6, which includes Traces 2.1.

You can fetch it from the usual pages:

As always, please report any problems, even minor ones.

A summary of the changes since version 2.6/2.0 is below.

Brendan McKay and Adolfo Piperno.


Changes from nauty 2.5 to nauty 2.6

Changes to dreadnaut:
* dreadnaut now catches control-C when nauty or Traces is running.
   This uses the global variable nauty_kill_request.
* new command "vv" to display sorted degree sequence.
* new command "r&" to relabel according to the partition.
* new command "->>" to flush the output.
* new command "B" to turn on output flushing at the end of every
   command.  Command "-B" turns it off.  Default off.
* Command with short arguments now have to be all on one line.
   Most errors cause the rest of the input line to be skipped.
* The "R" command now preserves the colouring.

Changes to nauty:
* nauty has an extra hook usercanonproc().
* The maximum number of vertices is now 2 billion.
* Many modern processors have instructions POPCNT and CLZ* that can
   help nauty.  The configuration script now looks for them and
   attempts to use them if possible.

New file formats (see formats.txt for definitions):
* sparse6 format is now extended with "incremental sparse6"
   format. Graphs in incremental sparse6 format specify only the
   differences from the previous graph.
   As yet, incremental sparse6 is only supported by copyg (which
   has new options -i/-I to write this format), listg, pickg and
   countg. For listg, pickg and countg, the -p switch might not work
   if the input is incremental.
* The new format digraph6 is for directed graphs.  There are
   procedures for reading and writing it in gtools.c.
   The following programs can handle digraph6 so far:
     labelg, shortg, ranlabg, directg, gentourng, amtog, complg,
     copyg, dretog, catg, listg, showg, converse, converseg, delptg,
     deledgeg, countg/pickg (partially), genrang (partially), genspecialg

New utilities:
*  converseg : take converse of a digraph
*  cubhamg : hamiltonian cycles in subcubic graphs
*  hamheuristic : heuristic for hamiltonian cycles
*  twohamg : partition quartic graphs into two hamiltonian cycles
*  genspecialg : generate special graphs like paths and cycles
*  gentreeg : generateg trees, based on a program of Li and Ruskey.
*  genquarticg : generate quartic graphs, written with Narjess Afzaly.
*  dretodot : reads one graph in dreadnaut format and writes a picture
      of it in dot format. You can use tools in the graphviz library
      to deal with it.
*  vcolg : colours the vertices of graphs in all distinct ways.
      If you choose the number of colours to be 2, this the same as
      adding loops in all distinct ways.
*  delptg : delete vertices.
As always, run the command with argument "-help" to get instructions.

Extra options in existing utilities:
* amtog now properly handles loops.  (Recall that loops are ok
     in sparse6 format but not in graph6 format.)
   amtog has a switch -o that allows selecting one colour class of
   a coloured graph, and -w to suppress the warning about loops.
* copyg has -z for writing digraph6 format. An undirected graph
   can be written as a digraph, but not vice-versa.
* directg default output format is directg6.
   directg has a new option -s for splitting into cases.
* dretog allows "d" command for digraph input.
* Option -B added to countg and pickg.
* complg has new option -R.
* genrang has new option -d that makes random regular graphs of
   any degree but does not guarantee uniform distribution.
   Also option -T for random tournaments.
   Some options now work for bipartite graphs; specify the number
   of vertices on each side like n1,n2.
* labelg has extra options -C and -W. These can help to determine
     what is different between two different programs that generate
     almost the same output.
* linegraphg has -t for making the total graph.

Other changes:
* Traces has substantial improvements.
* Extra argument macros SWDOUBLE, SWREALRANGE, SWSEQUENCE in gtools.h.
* girth() in gutil1.c got the wrong answer for K2.  Thanks to
   Sean Irvine for reporting it.
* gtools.c defines checkgline() to check if a graph input
   line looks ok.
* The procedures in gtnauty.c, used by labelg and other utilities,
   had an old limit of 2^22 (4 million+) vertices.  This limit is
   now removed.  Also a new procedure setlabptn() was added to set
   lab/ptn according to an integer weight.
* planarg -p had a bug causing wrong output for n >= 65536.  Fixed.
* The structured type bigint has disappeared in favour of integer type
   nauty_counter, which is "unsigned long long" if that exists and
   "unsigned long" is only 32 bits, or "unsigned long" otherwise.
   This means that some plugins for geng/genbg/gentourng may need
   to be revised.

More information about the Nauty mailing list