[Nauty] Re: New nauty version limited release

[Brendan McKay]

After a few useful feedbacks (thanks!), version 2.2 (final) is
now on the web page.  Since my preliminary announcement, the
following changes have been
1. make the change from INFINITY to NAUTY_INFINITY slightly more
   robust.
2. add -A and -B output options for multig.
3. fixed a problem in genrang that you didn't encounter unless the
   program refused to run at all.

Repeating the important comments from before:

> --> 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.
    -A  write as the upper triangle of an adjacency matrix, row by row,
        including the diagonal, and preceded by the number of vertices
    -B  write as an integer matrix preceded by the number of rows and
        number of columns, where -f determines the number of rows
>     -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 -B
> 
> 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:
% genbg 4 5 | multig -m3e12 -f4 -B
  >A genbg n=4+5 e=0:20 d=0:0 D=5:4 
  >A multig -m3f4e12:12
  >Z 1053 graphs generated in 0.00 sec
  4 5  0 0 0 0 3  0 0 0 0 3  0 0 0 0 3  0 0 0 0 3
  4 5  0 0 0 3 3  0 0 0 0 3  0 0 0 0 3  0 0 0 0 0
  4 5  0 0 0 3 0  0 0 0 0 3  0 0 0 0 3  0 0 0 0 3
  4 5  0 0 0 1 2  0 0 0 0 3  0 0 0 0 3  0 0 0 0 3
  4 5  0 0 0 1 3  0 0 0 0 3  0 0 0 0 3  0 0 0 0 2
  4 5  0 0 0 2 1  0 0 0 0 3  0 0 0 0 3  0 0 0 0 3
  ...
> Thus the 4th output is
> 
>      0  0  0  1  2
>      0  0  0  0  3
>      0  0  0  0  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 -B
  >A genbg n=4+5 e=5:20 d=1:1 D=5:4 
  >A multig -m3f4e12:12
  >Z 633 graphs generated in 0.00 sec
  4 5  1 1 1 1 0  0 0 0 0 3  0 0 0 0 3  0 0 0 0 2
  4 5  2 1 1 1 0  0 0 0 0 3  0 0 0 0 2  0 0 0 0 2
  4 5  2 1 1 1 0  0 0 0 0 3  0 0 0 0 3  0 0 0 0 1
  4 5  2 2 1 1 0  0 0 0 0 2  0 0 0 0 2  0 0 0 0 2
  4 5  2 2 1 1 0  0 0 0 0 3  0 0 0 0 2  0 0 0 0 1
  ...

> Thus the 1st output 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.