[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