README file for nauty 2.4
This file is only of historical interest as this version is very old.
Brendan McKay, bdm@cs.anu.edu.au
------------------------------------------------------------
The most recent distribution of nauty can be found at
http://cs.anu.edu.au/~bdm/nauty .
The manual nug.pdf is available at that site and is also included
in the distribution package.
Note that nauty is copyright but free to use for most purposes.
The details are in the file nauty.h.
The code in the file planarity.c (used by the planarg program)
is copyright to the Magma project.
------------------------------------------------------------
INSTALLATION.
The first step is to unpack the archive. On Unix-ish systems
you can use one of these commands:
tar xzf nauty24.tar.gz
or
gunzip -c nauty24.tar.gz | tar xf -
This will write all the files into the subdirectory nauty24.
Go to that directory.
If you have a working shell, and make, you can run
./configure
followed by
make all
to compile nauty for your system.
If that succeeds without problem, you will have have the
program dreadnaut ready to run.
If you have problems during compilation, it may be that the
configuration scripts are inadequate for your system. Usually it
is because of some missing system header, incompatible typedef,
or similar. Please send the details to the author.
If you don't have a shell or make, manually edit the files nauty.h,
naututil.h and gtools.h as distributed. The parts between the lines
======= near the start are the main things to look at. After this
manual editing, you can use makefile as a guide to compilation.
Programs which use an older version of nauty need to be
recompiled (** not just relinked **). Make sure they use the
DEFAULTOPTIONS_GRAPH or DEFAULTOPTIONS_SPARSEGRAPH macro to define
the fields of the options parameter.
See below for compiling on a PC under DJGPP.
If you are using Windows in an environment that needs Windows line
endings (which is a configuration option in Cygwin, for example),
then you might prefer to use nauty24.zip rather than
nauty24.tar.gz.
------------------------------------------------------------
TESTING.
After compiling nauty successfully, it is recommended that you run
the included test programs. The simplest way is
make checks
------------------------------------------------------------
MAILING LIST.
There is a mailing list for announcements and discussion about
nauty and related topics. You can subscribe at
http://dcsmail.anu.edu.au/cgi-bin/mailman/listinfo/nauty-list
------------------------------------------------------------
OTHER FILES IN THE PACKAGE.
A few additional goodies are included.
sumlines.c - This is a program designed to digest the outputs from
multiple runs of a program (such as a computation split into multiple
parts). Lines matching given patterns can be counted and checked,
and numbers appearing in them can be accumulated. Instructions appear
in the source file. See the option GMP near the head of the program
before trying to compile.
naugroup.h, naugroup.c - These define procedures for exhaustively
listing a group found by nauty. This is done in a space-efficient way.
A sample program appears in nautyex3.c, but so far there is no
complete documentation.
------------------------------------------------------------
DJGPP.
The Unix-like environment DJGPP can be used to run nauty and gtools on
DOS/Win computers. DJGPP is available at http://www.delorie.com/djgpp .
The program shortg does not work since DJGPP does not provide a working
pipe() system call. Using the bash shell is recommended. In DOS,
Windows NT and early Windows editions, you will need to convert all
long file names to the 8+3 limits. Thanks to Guenter Sterntenbrink
for helping with this.
If configure gives an error message similar to this:
can not guess host type: you must specify one
then try
./configure --host=i686
or use i586 for Pentium 2. If all of those fail, try
./configure --host=unknown
------------------------------------------------------------
Making 32-bit executables on 64-bit Linux systems.
(In bash or sh:)
CFLAGS=-m32 CXXFLAGS=-m32 LDFLAGS=-m32 ./configure
make clean; make
This requires the libraries ia32-libs and libc6-dev-i386.
------------------------------------------------------------
RECENT CHANGES.
Here we list substantive changes made since the first 2.2 release.
Nov 16, 2002: Replaced rng.c after communication with Don Knuth.
The previous version had a bug (mine!) when there was no explicit
initialization done by the user. It appears the error had no
impact on nauty (which only uses rng.c for the "s" command in
dreadnaut, and for genrang, but both always initialize).
No change to the nauty version number but beta=2.
Nov 18, 2000: Adjusted the makefile and countg/testg to work in
the DOS/Win environment DJGPPP (see the previous section).
May 1, 2003: Fixed PRUNE feature of genbg.
May 3, 2003: Added utility directg for making all orientations of graphs.
Oct 4, 2003: Added options -a, -Z, -d, -z to genbg. Also, the -l
(canonical label) option now preserves the colouring.
Nov 17, 2003: Renamed INFINITY to NAUTY_INFINITY since many C header
libraries define INFINITY. If INFINITY is not defined by
the system, you can still use it.
Nov 19, 2003: Added program biplabg to relabel bipartite graphs with the
colour classes contiguous.
Feb 13, 2004: Revised C options for solaris on pentium
Mar 1, 2004: dretog knows !...\n type of comment
May 7, 2004: geng can be called from another program (see instructions
in geng.c.)
May 29, 2004: added definition of SETWORD_FORMAT used to write a setword
with printf( ) - see nauty.h
Sep 11, 2004: Added utility multig for making multigraphs based on
provided simple graphs; similar to directg
Oct 16, 2004: To avoid problems caused by system-dependent handling of
external declarations, nauty() no longer accepts NULL as
the value of options.dispatch. To get the previous
behaviour, use the value &graph_dispatch. This will be
handled automatically if programs calling nauty use
DEFAULTOPTIONS to declare options and are recompiled.
Even better is to use DEFAULTOPTIONS_GRAPH.
May 5, 2005: A bug in the writing of sparse6 was found and fixed.
This is procedure ntos6() in gtools.c, which is invoked
by writes6(). The bug could only happen if all the
following are true:
1. n = 2, 4, 8 or 16 (for n=2, only if the graph has loops)
2. Vertex n-2 has non-zero degree, but vertex n-1 has
zero degree.
These conditions never happen for graphs generated by
geng or genbg, nor for regular graphs or connected graphs,
nor for graphs canonically labelled by nauty (except maybe
with some unusual vertex colouring or invariant).
If the conditions do happen, the buggy routine may
(with some probability) add a spurious loop to vertex n-1.
In the package is a utility checks6:
Usage: checks6 [-w] [infile [outfile]]
Check a file of graphs, optionally write corrected version
-w Write corrected graphs (default is not to write)
------now we start version 2.3 (not released) and 2.4------
Nov 10, 2004: Use faster routine getc_unlocked() for reading graphs if
available. It can make a surprising difference.
Nov 17, 2004: If putenv() or setenv() are available, we set LC_COLLATE to
"C" before executing "sort" in shortg. This should alleviate
collation issues with sort. However, note that many
utilities use the locale these days so you are advised to
have LC_COLLATE defined to be "C" always when you are dealing
with files of graphs.
Six counters in statsblk became "unsigned long" instead of
"long". nauty doesn't actually use these, but we might as
well give them twice as long before they overflow.
Nov 24, 2004: Made geng faster for generating trees. The output labelling
may be different from before. A very much faster tree
generator is in the works.
Jan 17, 2005: Added two items to dispatch vectors:
init : used for initialising something at the start
cleanup : used for doing something at the end, such as
freeing space allocated by init()
See the manual for calling sequences.
May 20, 2005: Update graph6 and sparse6 formats to allow much large sizes.
The limit is now 68719476735 vertices (best of luck getting
close to that!).
Nov 12, 2005: Changed NAUTY_INFINITY to 2^30+2 in BIGNAUTY case
2006 various: Procedures for sparse graphs implemented.
New program planarg to test for planarity and find
planar embeddings: planarg -help for details.
The planarity code was written by Paulette Lieby for the
Magma project and used with permission.
labelg got -S to use sparse graphs.
genbg -N changed to genbg -n (only Gordon uses this).
genrang gained -R switch for regular graphs in text format.
gtools.c has code for reading and writing planarcode.
listg got a compile time option to select "Matrix" or
"array" for Maple output.
pickg/countg got -T for counting triangles
Better configuration for MacOSX.
Nov 22, 2006: Removed usertcellproc from options. Greater functionality
is now available using the new targetcell field in the
dispatch vector. The u8 command has gone from dreadnaut.
Changed bestcell to targetcell in dispatch vector.
Nov 29, 2006: Added extraoptions field (currently unused) to optionblk
Dec 9, 2006: Added an invariant adjacencies_sg(), recommended for digraphs
when using sparse representation.
Dec 10, 2006: Remove BIGNAUTY, whose usefulness has passed. Now the types
shortish and permutation are synonymous with int always.
The limit on the number of vertices is 2^30 unless int
has only 16 bits (still any of them around?) in which
case it is 2^15-3. Programs previously linked with
files like nautyB.o can now be linked with nauty.o.
Alternatively, "make bigs" will create files like
nautyB.o by copying.
June 26, 2007: Fixed an error in listg -s reported by Evan Heidtmann.
July 12, 2007: Added -f option to directg.
Aug 14, 2007: Added -i,-I,-K options to shortg, parallel to labelg.
Since -k is used in labelg in place of -I, changed labelg
to use -I also, with -k remaining as an undocumented
compatibility feature.
Aug-Sep 2007: Minor things:
* naututil-h.in now defines CPUTIME=0.0 as a last resort
* gtools.c now implements EDGECODE (not used anywhere yet)
* fixed definition of SG_FREE in nausparse.h (not used)
* geng favours space over time for n > 28
Oct 14, 2007: Added -T switch to shortg to specify scratch directory.
Mar 3, 2008: Fixed makefile for compilation in a 64-bit environment.
Oct 11, 2008: Added -l and -m to genrang
Nov 29, 2008: Slightly improved -c for geng and genbg
Added tournament generator gentourng.
Mar 3, 2009: Added -V to directg.
Generated by dwww version 1.15 on Sat May 18 06:04:53 CEST 2024.