1
2README file for nauty 2.2.
3
4Brendan McKay, bdm@cs.anu.edu.au
5
6------------------------------------------------------------
7
8The most recent distribution of nauty can be found at
9http://cs.anu.edu.au/~bdm/nauty .
10
11The manual nug.pdf is available at that site and is also included
12in the distribution package.
13
14Note that nauty is copyright but free to use for most purposes.
15The details are in the file nauty.h.
16
17------------------------------------------------------------
18
19INSTALLATION.
20
21The first step is to unpack the archive. On Unix-ish systems
22you can use one of these commands:
23
24 tar xfz nauty22.tar.gz
25or
26 gunzip -c nauty22.tar.gz | tar xf -
27
28This will write all the files into the subdirectory nauty22.
29Go to that directory.
30
31If you have a working shell, and make, you can run
32 ./configure
33followed by
34 make all
35to compile nauty for your system.
36
37If that succeeds without problem, you will have two versions of
38dreadnaut:
39
40dreadnaut : graphs up to 32765 vertices
41dreadnautB : graphs limited only by your available RAM
42
43If you have problems during compilation, it may be that the
44configuration scripts are inadequate for your system. Usually it
45is because of some missing system header, incompatible typedef,
46or similar. Please send the details to the author.
47
48If you don't have a shell or make, manually edit the files nauty.h,
49naututil.h and gtools.h as distributed. The parts between the lines
50======= near the start are the main things to look at. After this
51manual editing, you can use makefile as a guide to compilation.
52
53Programs which use an older version of nauty need to be recompiled
54(** not just relinked **). Make sure they use the DEFAULTOPTIONS
55macro to define the fields of the options parameter.
56
57See below for compiling on a PC under DJGPP.
58
59------------------------------------------------------------
60
61TESTING.
62
63After compiling nauty successfully, it is recommended that you run
64the included test programs. The simplest way is
65 make checks
66
67------------------------------------------------------------
68
69MAILING LIST.
70
71There is a mailing list for announcements and discussion about
72nauty and related topics. You can subscribe at
73http://cs.anu.edu.au/mailman/listinfo/nauty-list .
74
75------------------------------------------------------------
76
77OTHER FILES IN THE PACKAGE.
78
79A few additional goodies are included.
80
81sumlines.c - This is a program designed to digest the outputs from
82 multiple runs of a program (such as a computation split into multiple
83 parts). Lines matching given patterns can be counted and checked,
84 and numbers appearing in them can be accumulated. Instructions appear
85 in the source file. See the option GMP near the head of the program
86 before trying to compile.
87
88naugroup.h, naugroup.c - These define procedures for exhaustively
89 listing a group found by nauty. This is done in a space-efficient way.
90 A sample program appears in nautyex3.c, but so far there is no
91 complete documentation.
92
93------------------------------------------------------------
94
95DJGPP.
96
97The Unix-like environment DJGPP can be used to run nauty and gtools on
98DOS/Win computers. DJGPP is available at http://www.delorie.com/djgpp .
99The program shortg does not work since DJGPP does not provide a working
100pipe() system call. Using the bash shell is recommended. In DOS,
101Windows NT and early Windows editions, you will need to convert all
102long file names to the 8+3 limits. Thanks to Guenter Sterntenbrink
103for helping with this.
104
105If configure gives an error message similar to this:
106 can not guess host type: you must specify one
107then try
108 ./configure --host=i686
109or use i586 for Pentium 2. If all of those fail, try
110 ./configure --host=unknown
111
112------------------------------------------------------------
113
114RECENT CHANGES.
115
116Here we list substantive changes made since the first 2.2 release.
117
118Nov 16, 2002: Replaced rng.c after communication with Don Knuth.
119 The previous version had a bug (mine!) when there was no explicit
120 initialization done by the user. It appears the error had no
121 impact on nauty (which only uses rng.c for the "s" command in
122 dreadnaut, and for genrang, but both always initialize).
123 No change to the nauty version number but beta=2.
124
125Nov 18, 2000: Adjusted the makefile and countg/testg to work in
126 the DOS/Win environment DJGPPP (see the previous section).
127
128May 1, 2003: Fixed PRUNE feature of genbg.
129
130May 3, 2003: Added utility directg for making all orientations of graphs.
131
132Oct 4, 2003: Added options -a, -Z, -d, -z to genbg. Also, the -l
133 (canonical label) option now preserves the colouring.
134
135Nov 17, 2003: Renamed INFINITY to NAUTY_INFINITY since many C header
136 libraries define INFINITY. If INFINITY is not defined by
137 the system, you can still use it.
138
13929-May-04 : - added definition of SETWORD_FORMAT used to write a setword
140 with printf( ) - see nauty.h
141
142Nov 19, 2003: Added program biplabg to relabel bipartite graphs with the
143 colour classes contiguous.
144
145Feb 13, 2004: Revised C options for solaris on pentium
146
147Mar 1, 2004: dretog knows !...\n type of comment
148
149May 7, 2004: geng can be called from another program (see instructions
150 in geng.c.
151
152Sep 11, 2004: Added utility multig for making multigraphs based on
153 provided simple graphs; similar to directg
154
155Oct 16, 2004: To avoid problems caused by system-dependent handling of
156 external declarations, nauty() no longer accepts NULL as
157 the value of options.dispatch. To get the previous
158 behaviour, use the value &graph_dispatch. This will be
159 handled automatically if programs calling nauty use
160 DEFAULTOPTIONS to declare options and are recompiled.
161 Even better is to use DEFAULTOPTIONS_GRAPH.
162
163May 5, 2005: A bug in the writing of sparse6 was found and fixed.
164 This is procedure ntos6() in gtools.c, which is invoked
165 by writes6(). The bug could only happen if all the
166 following are true:
167 1. n = 2, 4, 8 or 16 (for n=2, only if the graph has loops)
168 2. Vertex n-2 has non-zero degree, but vertex n-1 has
169 zero degree.
170 These conditions never happen for graphs generated by
171 geng or genbg, nor for regular graphs or connected graphs,
172 nor for graphs canonically labelled by nauty (except maybe
173 with some unusual vertex colouring or invariant).
174 If the conditions do happen, the buggy routine may
175 (with some probability) add a spurious loop to vertex n-1.
176
177 In the package is a utility checks6:
178
179 Usage: checks6 [-w] [infile [outfile]]
180 Check a file of graphs, optionally write corrected version
181 -w Write corrected graphs (default is not to write)
182