[Nauty] New nauty version limited release

[Brendan McKay]

Nauty peoples,

A new version of nauty/gtools can be downloaded from
    http://cs.anu.edu.au/~bdm/nauty/nauty22.tar.gz
    http://cs.anu.edu.au/~bdm/nauty/nauty22.zip
Use the second URL for DOS/Windows and the first for everything else.

I will wait for problems to be reported before advertising this
version on the web page, so if you have nothing better to do please
try it out and let me know of even trivial problems.

--> You should recompile all programs that call nauty before
--> concluding that nauty has problems.

Changes to the core nauty procedures:
* Made more compilers happy by extending prototypes even to nested
  procedure arguments.
* Changed INFINITY to NAUTY_INFINITY because INFINITY is defined by
  the latest ISO C standard as a floating-point value.
* Added a macro SETWORD_FORMAT giving a fprintf() format string for
  writing values of type setword.
* nauty() no longer allows options.dispatch==NULL, which used to 
  default to &dispatch_graph.  If you are using DEFAULTOPTIONS to
  declare the options structure, recompiling should suffice.
  Alternatively, get With It by using DEFAULTOPTIONS_GRAPH, like this:
      static DEFAULTOPTIONS_GRAPH(options);

New utilities:
* biplabg reads bipartite graphs and relabels them such that the
  colour classes are contiguous.  The first colour class is defined
  to be the set of all vertices which have the same colour as the
  first vertex in the same component.
* multig reads simple graphs and changes their edges into multiple
  edges in all distinct ways.  See below.

Cheers, Brendan.

=========================multig================================
% multig --help

Usage: multig [-q] [-u|-T|-G] [-e#|-e#:#] [-m#] [-f#] [infile [outfile]]

 Read undirected loop-free graphs and replace their edges with multiple
  edges in all possible ways (multiplicity at least 1).
  Isomorphic multigraphs derived from the same input are suppressed.
  If the input graphs are non-isomorphic then the output graphs are also.

    -e# | -e#:#  specify a value or range of the total number of edges
                 counting multiplicities
    -m# maximum edge multiplicity (minimum is 1)
	Either -e or -m with a finite maximum must be given
    -f#  Use the group that fixes the first # vertices setwise
    -T  use a simple text output format (nv ne {v1 v2 mult})
    -G  like -T but includes group size as third item (if less than 10^10)
	  The group size does not include exchange of isolated vertices.
    -u  no output, just count them
    -q  suppress auxiliary information

This can be used in conjunction with a source of simple graphs to
generate nonisomorphic multigraphs.  I'll give two examples.

-------------------
A.  Generate all multigraphs on 7 vertices and 20 edges.

% geng 7 1:20 | multig -u -e20
>A geng -d0D6 n=7 e=1-20
>Z 1042 graphs generated in 0.00 sec
>A multig -ue20:20
>Z 1042 graphs read from stdin; 28819926 multigraphs generated; 9.92 sec

   geng generated 1042 simple graphs with from 1 to 20 edges,
   then multig added multiplicities to the edges so that the total
   multiplicity is 20.  Each simple edge gets multiplicity at least 1.

 To get the multigraphs, change -u into -T or -G.  For -T the
 output is like this:
7 1 0 6 20
7 2 0 6 10 1 6 10
7 2 0 6 11 1 6 9
7 2 0 6 12 1 6 8
7 2 0 6 13 1 6 7
...lots deleted
7 19 0 2 1 0 3 1 0 4 2 0 5 1 0 6 1 1 2 1 1 3 1 1 4 1 1 5 1 1 6 1 2 4 1 2 5 1 2 6 1 3 4 1 3 5 1 3 6 1 4 5 1 4 6 1 5 6 1
7 19 0 2 2 0 3 1 0 4 1 0 5 1 0 6 1 1 2 1 1 3 1 1 4 1 1 5 1 1 6 1 2 4 1 2 5 1 2 6 1 3 4 1 3 5 1 3 6 1 4 5 1 4 6 1 5 6 1
7 20 0 2 1 0 3 1 0 4 1 0 5 1 0 6 1 1 2 1 1 3 1 1 4 1 1 5 1 1 6 1 2 3 1 2 4 1 2 5 1 2 6 1 3 4 1 3 5 1 3 6 1 4 5 1 4 6 1 5 6 1


Each line is
  <# vertices> <# non-zero edges> {<vertex> <vertex> <multiplicity}*

-------------------
B.  Generate the 4 x 5 integer matrices with total sum 12
    and entries {0,1,2,3}.

% genbg 4 5 | multig -m3e12 -f4 -T

The genbg command makes bipartite graphs with 4 vertices of the first
colour and 5 of the second colour.  The multig command changes each edge
to one of {1,2,3} since a limit of 3 is given by -m3.  The parameter
-e12 says that the total sum of all edges is 12.  The -f4 says that
in considering isomorphisms the first 4 vertices are not mixed with
the others.  (For this application you would normally use -f with the
number of vertices in the first class.)

The output is like this:
9 4 0 8 3 1 8 3 2 8 3 3 8 3
9 4 0 7 3 0 8 3 1 8 3 2 8 3
9 4 0 7 3 1 8 3 2 8 3 3 8 3
9 5 0 7 1 0 8 2 1 8 3 2 8 3 3 8 3
 .... 46209 lines removed
9 12 0 4 1 0 6 1 0 7 1 0 8 1 1 4 1 1 7 1 2 5 1 2 6 1 2 7 1 2 8 1 3 5 1 3 8 1
9 12 0 4 1 0 6 1 0 7 1 1 4 1 1 7 1 1 8 1 2 5 1 2 6 1 2 7 1 2 8 1 3 5 1 3 8 1
9 12 0 4 1 0 6 1 0 7 1 0 8 1 1 4 1 1 7 1 1 8 1 2 5 1 2 6 1 3 5 1 3 7 1 3 8 1
9 12 0 4 1 0 6 1 0 7 1 1 4 1 1 7 1 1 8 1 2 5 1 2 6 1 2 8 1 3 5 1 3 7 1 3 8 1

Thus the 4th output is

       4  5  6  7  8

   0:  0  0  0  1  2
   1:  0  0  0  0  3
   2:  0  0  0  0  3
   3:  0  0  0  0  3

The parameters of  genbg  can restrict the structure somewhat; for example
using -d1:1 will ensure that no row or column is entirely zero.

% genbg -d1:1 4 5 | multig -m3e12 -f4 -T
9 7 0 4 1 0 5 1 0 6 1 0 7 1 1 8 3 2 8 3 3 8 2
9 7 0 4 2 0 5 1 0 6 1 0 7 1 1 8 3 2 8 2 3 8 2
9 7 0 4 2 0 5 1 0 6 1 0 7 1 1 8 3 2 8 3 3 8 1
9 7 0 4 2 0 5 2 0 6 1 0 7 1 1 8 2 2 8 2 3 8 2
 .... and 20025 more

The first one is

  1  1  1  1  0
  0  0  0  0  3
  0  0  0  0  3
  0  0  0  0  2

multig cannot presently generate loops.  That will change.