[Nauty] Re: New nauty version limited release
Brendan McKay
bdm at cs.anu.edu.au
Thu Oct 28 20:58:01 EST 2004
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.
More information about the Nauty
mailing list