[Nauty] nauty & traces beta version 2.9.4b5

[Brendan McKay]

Dear nauty people,

The beta release 2.9.4b5 is available at
https://users.cecs.anu.edu.au/~bdm/nauty/nauty2_9_4b5.tar.gz
My intention is to make this version 2.9.4 if there are no complaints 
for a while.

Here is a list of the changes since version 2.9.3.  At the end, I give a 
few hints
about using nauty that you might find helpful.

Cheers, Brendan.

-----------------------------------------------------------------

* listg -b (DIMACS format) now knows digraphs

* The code in nauty.h that used Windows intrinsics _BitScanReverse and
   _BitScanReverse64 was wrong, but is now fixed thanks to Tom Sirgedas.
   You did not meet this problem if the nautest program (run by "make 
tests")
   didn't report errors, and in general you didn't meet it if you weren't
   using a Windows IDE like MSVS.

* Corrected documentation for nbrhoodg -D, no change to the code.

* gentreeg -i made homeomorphically irreducible trees already but now it
   is documented.

* productg -A says to make the product of the first graph and each of the
   the remaining input graphs. Without -A, only the product of the first two
   graphs is made.

* The command OO in dreadnaut has changed. If group orbits are defined,
   the partition is set to the intersection of the previous partition 
(that with
   one cell if not otherwise defined) and the partition of vertices 
according
   to the length of their orbits. This is done in a canonical way. This is
   of use in some very difficult problems where (for Traces especially) the
   group can be found much faster than a canonical labelling. Then an
   alternative canonical labelling can be made with the sequence
   -c x OO +c x
   with a partition optionally defined beforehand.

* If the zlib library is available, utilities countneg, countg, pickg, 
copyg,
   uniqg and dimacs2g can transparently read gzipped inputs in addition to
   plain text inputs. This is implemented via functions in the files
   ngztools.h and ngztools.c. If zlib is not available, only plain text
   files can be read, as before. Note that on most systems you need the
   zlib development tools as well as the library to compile with zlib.
   To disable this facility, configure with --disable-zlib .

* dimacs2g no longer uses gunzip but instead uses the zlib facility 
described
   in the previous comment. dimacs2g also has new switches -z (interpret
   the input as a digraph) and -f (write the vertex colouring defined in the
   syntax of Bliss, see 
https://users.aalto.fi/~tjunttil/bliss/fileformat.html).
   -f only makes sense when the output format is dreadnaut.

* A new utility combineg constructs functions of graphs.  For example:
   combineg -e'l(P,C7)'  -- lexicographic product Petersen[7-cycle]
   combineg -e'c(L(K5),L(K5),L(K5))' -- Cartesian product of three copies
       of the linegraph of K5.
   Graphs in the input can be included in the expression, using the names
   G1, G2, ...  The special name G (without a number) refers to all the
   graphs in the input following the numbered graphs.
   combineg -e'C(t(G7,P3))' -- the complement of the tensor product of the
       7th input graph with the path P3.
   combineg -e'G,c(G,P)' -- write each input graph followed by its cartesian
       product with Petersen's graph.
   Run combineg --help to see all the available functions.

* The function countorbits() in gtnauty.c now reports that a graph with no
   edges has 0 edge orbits and 0 arcorbits. This effects countg/pickg 
options
   O and OO. Thanks to Allan Bickle.

* The utility uniqg has new options -O and -N.  If you use uniqg -xFILE -O
   then uniqg passes through any graph which is isomorphic to a graph in 
FILE.
   Similarly, uniqg -xFILE -N passes through any graph which is not
   isomorphic to any graph in FILE. In both cases the output graphs are
   identical to the input graphs (no canonical labelling) and isomorphic
   graphs in the input are not removed. The space requirement is determined
   only by the number of graphs in FILE, no matter how many inputs there 
are.

* Fixed a bug in vcolg when there were more than 128 colours.

-------------------------------------------------------------

Two Tips.

1. If you use dreadnaut, you are probably annoyed that you can't edit the
    input line except to erase back to the error, and you can't bring up
    previous input lines. The usual way of implementing those is to do
    input via the readline library, but readline has an incompatible
    license so that isn't an option. However, there is a way. Install the
    utility "rlwrap". It is available on Linuxes via the usual package
    mechanism and on Mac from either MacPorts or HomeBrew. Then you
    can start dreadnaut like "rlwrap dreadnaut" and it will look exactly the
    same except that you can use arrow keys and other editing functions.

2. Utilities like "sort", "comm", "uniq" compare lines according to the
    specified locale. Different locales imply different comparisons between
    characters. Execute the command "locale" and you will see a list of
    variables that include LANG, LC_COLLATE and LC_ALL. Probably all
    them except LC_ALL will be set to something like "en_US.UTF-8".
    The order of characters is decided like this: if LC_ALL is defined
    use it, otherwise if LC_COLLATE is defined use it, otherwise use LANG.

    Some locales even treat different characters as equal for collating
    purposes, so it isn't a good idea to use arbitrary locales for
    sorting files of graphs.  For this reason, shortg uses the special
    locale "C", which orders characters according to their binary value.
    The difference is very significant:
          With C:                   A < B < a < b
          With en_US.UTF-8: a < A < b < B

    To be sure of getting the same order as shortg when using utilities
    like "sort", you can do it like this in most shells: "LC_ALL=C sort"
    Personally I set my shell initialisation files to define
    LC_COLLATE=C and leave LC_ALL undefined. Don't set LC_ALL to "C"
    permanently, since it might stop you from editing non-ASCII files.