[Nauty] New release of nauty: 2.2b5

[Sterten at aol.com]

Brendan wrote:

 >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.

I like this directg. 
To build it with GCC and all my old .o files from the
last version still present, I had to copy the new naugroup.c,directg.c
and run :

gcc -c naugroup.c
gcc -c -O2 directg.c  { with O2 it's about 2 times faster on my PC ! }
gxx directg.o gtools.o nauty.o nautil.o naugraph.o naugroup.o -o directg.exe

 >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.

you mean:
all 4 possibilities between 2 different vertices are included,
so all  irreflexive  relations or binary adjacency matrices with 0 in the 
main diagonal are allowed.
For a possible further restriction we can use the -o switch.

 >Isomorphic directed graphs derived from the same input are suppressed.
 >
 >    -e#:#  specify a value or range of the number of directed edges

total number of edges, not edges between two vertices

 >    -o     orient each egde in only one direction, never both

0 or 1 directed edge between two vertices
typo egde

 >    -T  use a simple text output format (nv ne edges) instead of digraph6

I'd like the adjacency matrix as additional option (just 0s and 1s)
in one line with an optional blank when the source-vertex changes

 >    -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.

group is automorphism-group

 >    -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

c for connected, q for quiet, n=4 (vertices), m=3 edges
no cycle can occur, since the graph is connected
3 edges are required for the graph to be connected
geng -cqtf 4 | directg -oT
should also work (triangles and squares excluded)


 >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

there should be a mode
directg 6
or geng -qd 6
to perform this IMO.

 >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

hmm, I don't know the definition of weakly connected or tournament ATM,
and am too lazy to look it up ...

 >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.)

"good" means "fast" here ? 
But it's still useful to have this directg.exe method at hand.

 >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.

...yet ? or never will be ?
I assume loops are edges v-->v


the next step would be to allow multiple edges, e.g. <n edges for any pair of
vertices, which would count groupoids. Can it be thus extended in theory ?



Guenter
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.anu.edu.au/mailman/private/nauty/attachments/20030511/26792b3d/attachment.html