[Nauty] New release of nauty: 2.2b5

Brendan McKay bdm at cs.anu.edu.au
Tue May 6 01:04:01 EST 2003


nauty22b5.tar.gz, available at http://cs.anu.edu.au/~bdm/nauty,
has the following changes (apart from trivial adjustments):

1. The PRUNE facility of genbg had a bug which is now fixed.
   (The PRUNE facility of geng was fine already.)

2. naugroup.c contains a version of the group generator that
   allows the generation to be aborted.  (For documentation of
   naugroup.c, see nautyex3.c.)

3. There is a preliminary version of a new program "directg" for
   generating digraphs.  Description below.

As always, please report problems.

Brendan.

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

% directg --help

Usage: directg [-q] [-u|-T|-G] [-o] [-e#|-e#:#] [infile [outfile]]

 Read undirected graphs and orient their edges in all possible ways.
 Edges can be oriented in either or both directions.
 Isomorphic directed graphs derived from the same input are suppressed.

    -e#:#  specify a value or range of the number of directed edges
    -o     orient each egde in only one direction, never both

    -T  use a simple text output format (nv ne edges) instead of digraph6
    -G  like -T but includes group size as third item (if less than 2^32)
	  The group size does not include exchange of isolated vertices.
    -u  no output, just count them
    -q  suppress auxiliary information


The default output format (digraph6, similar to graph6) is not implemented
yet, so you need to use -T or -G to get output.

All oriented trees with 4 vertices:
% geng -cq 4 3 | directg -oT
4 3 0 3 1 3 2 3
4 3 0 3 1 3 3 2
4 3 0 3 3 1 3 2       the number of vertices, the number of
4 3 3 0 3 1 3 2       edges, a list of edges
4 3 0 2 0 3 1 3
4 3 0 2 0 3 3 1
4 3 0 2 3 0 1 3
4 3 2 0 0 3 1 3
>Z 2 graphs read from stdin; 8 digraphs written to stdout; 0.00 sec

All digraphs with 6 vertices:
% geng -q 6 | directg -u
>Z 156 graphs read from stdin; 1540944 digraphs generated; 23.30 sec

Weakly connected digraphs with 8 vertices and 14 edges:
% geng -cq 8 7:14 | directg -u -e14
>Z 5850 graphs read from stdin; 137134237 generated; 99.75 sec

Weakly connected digraphs with 9 vertices and 8-13 edges:
% geng -cq 9 8:13 | directg -u -e8:13
>Z 16058 graphs read from stdin; 196616399 generated; 159.60 sec

Tournaments of order 7:
% geng -cq 7 21 | directg -u -o
>Z 1 graphs read from stdin; 456 digraphs generated; 3.10 sec
(This is the worst case for the program and is certainly NOT a good way to
generate tournaments.  If you want some small tournaments you are better
off fetching them from http://cs.anu.edu.au/~bdm/data/digraphs.html.)

There is currently no method provided for generating strongly-connected
digraphs, but I'm thinking about it.  Nor is there a way to include loops.




More information about the Nauty mailing list