[Nauty] Version 2.2 beta 3 released; future things
Brendan McKay
bdm at cs.anu.edu.au
Wed Nov 20 10:41:01 EST 2002
--------------------
Beta 3 has these changes:
* The validation tests (make checks) work again. They broke in
beta 2 because the random number generator changed.
* You can run nauty and all of gtools except shortg on a PC,
provided you install the environment djgpp. See README for
details. Thanks to Guenter Sternten for helping with this.
I will start to distribute binaries for PC when I install
the necessary tools to make DOS binaries on my Linux box.
If you aren't having trouble with beta 2, there is no good
reason to upgrade.
-------------------
Recent versions of nauty have the in-principle capability of
processing objects other than graphs. The same program can
even use nauty on several types of object at once. So far
I have not released any code for this but a few bits exist
in working protypes. Here is a list of what is planned.
1. Sparse graphs. Presently a graph needs n^2 bits of storage
irrespective of the number of edges, so getting past about
60,000 vertices is nearly impossible. This facility will allow
you to process graphs and multigraphs up to millions of vertices
provided they fit into memory at 16 bytes per edge. There will
be an option for allowing colours on the edges.
2. Hypergraphs/designs. This facility will treat hypergraphs as
objects of size equal to the number of points, irrespective of
the number of edges. Usually it will be more efficient than
converting the hypergraph into a bipartite graph.
3. Matrices. This facility will treat equivalence of integer
matrices under independent row and column permutations (and
maybe under transpose). An option will allow Hadamard
equivalence, which in addition considers multiplication of
rows and columns by -1.
Requests will be considered.
Cheers,
Brendan.
More information about the Nauty
mailing list