1README file for nauty 2.7
2
3Brendan McKay, bdm@cs.anu.edu.au
4Adolfo Piperno, piperno@di.uniroma1.it
5
6------------------------------------------------------------
7
8The most recent distribution of nauty and Traces can be found at
9http://cs.anu.edu.au/~bdm/nauty and http://pallini.di.uniroma1.it .
10
11The manual nug27.pdf is available at that site and is also included
12in the distribution package.
13
14Note that nauty and Traces are copyright but free to use for most
15purposes. The details are in the file COPYRIGHT.
16
17------------------------------------------------------------
18
19INSTALLATION.
20
21See the manual for more information.
22
23If you have a working shell, and "make", you can run
24 ./configure
25followed by
26 make
27to compile nauty and Traces for your system.
28
29If that succeeds without problem, you will have have the
30program dreadnaut ready to run.
31
32There are some options that can be specified at the ./configure
33step; see the manual.
34
35If you don't have a shell or make, manually edit the files nauty.h,
36naututil.h and gtools.h as distributed. The parts between the lines
37======= near the start are the main things to look at. After this
38manual editing, you can use makefile.basic as a guide to compilation.
39
40Programs which use an older version of nauty need to be
41recompiled (** not just relinked **). Make sure they define
42the options structure using one of
43DEFAULTOPTIONS_GRAPH
44DEFAULTOPTIONS_SPARSEGRAPH
45DEFAULTOPTIONS_DIGRAPH
46DEFAULTOPTIONS_SPARSEDIGRAPH
47DEFAULTOPTIONS_TRACES
48
49------------------------------------------------------------
50
51TESTING.
52
53After compiling nauty successfully, it is recommended that you run
54the included test programs. The simplest way is
55 make checks
56
57------------------------------------------------------------
58
59MAILING LIST.
60
61There is a mailing list for announcements and discussion about
62nauty and related topics. You can subscribe at
63http://mailman.anu.edu.au/mailman/listinfo/nauty
64
65------------------------------------------------------------
66
67OTHER FILES IN THE PACKAGE.
68
69Also in the package (documentation at the start of each source file).
70
71sumlines.c - This is a program designed to digest the outputs from
72 multiple runs of a program (such as a computation split into multiple
73 parts). Lines matching given patterns can be counted and checked,
74 and numbers appearing in them can be accumulated. Instructions appear
75 in the source file. See the option GMP near the head of the program
76 before trying to compile.
77
78sorttemplates.c - Some carefully tuned generic quicksort procedures.
79
80bliss2dre.c - A program which reads one file in Bliss format and writes
81 it in dreadnaut format.
82
83blisstog.c - A program which reads one or more files in Bliss format
84 and writes all the graphs in sparse6 format.
85
86poptest.c - A program for testing the POPCOUNT macro.
87
88dretodot.c - A program that reads files in dreadaut format and writes
89 dot files suitable for drawing with graphviz.
90
91------------------------------------------------------------
92
93Windows.
94
95For running nauty in Windows, Cygwin is recommended.
96
97If configure gives an error message similar to this:
98 can not guess host type: you must specify one
99then try
100 ./configure --build=unknown
101
102------------------------------------------------------------
103
104Making 32-bit executables on 64-bit Linux systems.
105
106(In bash or sh:)
107CFLAGS=-m32 CXXFLAGS=-m32 LDFLAGS=-m32 ./configure
108make clean; make
109
110This requires 32-bit libraries to be available. On Ubuntu
111they are called ia32-libs and libc6-dev-i386.
112
113------------------------------------------------------------
114
115RECENT CHANGES.
116
117See the file changes24-27.txt for a longer list.
118See the file README_24 for a list of older changes.
119
1
2README file for nauty 2.4
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
17The code in the file planarity.c (used by the planarg program)
18is copyright to the Magma project.
19
20------------------------------------------------------------
21
22INSTALLATION.
23
24The first step is to unpack the archive. On Unix-ish systems
25you can use one of these commands:
26
27 tar xzf nauty24.tar.gz
28or
29 gunzip -c nauty24.tar.gz | tar xf -
30
31This will write all the files into the subdirectory nauty24.
32Go to that directory.
33
34If you have a working shell, and make, you can run
35 ./configure
36followed by
37 make all
38to compile nauty for your system.
39
40If that succeeds without problem, you will have have the
41program dreadnaut ready to run.
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
54recompiled (** not just relinked **). Make sure they use the
55DEFAULTOPTIONS_GRAPH or DEFAULTOPTIONS_SPARSEGRAPH macro to define
56the fields of the options parameter.
57
58See below for compiling on a PC under DJGPP.
59
60If you are using Windows in an environment that needs Windows line
61endings (which is a configuration option in Cygwin, for example),
62then you might prefer to use nauty24.zip rather than
63nauty24.tar.gz.
64
65------------------------------------------------------------
66
67TESTING.
68
69After compiling nauty successfully, it is recommended that you run
70the included test programs. The simplest way is
71 make checks
72
73------------------------------------------------------------
74
75MAILING LIST.
76
77There is a mailing list for announcements and discussion about
78nauty and related topics. You can subscribe at
79http://dcsmail.anu.edu.au/cgi-bin/mailman/listinfo/nauty-list
80
81------------------------------------------------------------
82
83OTHER FILES IN THE PACKAGE.
84
85A few additional goodies are included.
86
87sumlines.c - This is a program designed to digest the outputs from
88 multiple runs of a program (such as a computation split into multiple
89 parts). Lines matching given patterns can be counted and checked,
90 and numbers appearing in them can be accumulated. Instructions appear
91 in the source file. See the option GMP near the head of the program
92 before trying to compile.
93
94naugroup.h, naugroup.c - These define procedures for exhaustively
95 listing a group found by nauty. This is done in a space-efficient way.
96 A sample program appears in nautyex3.c, but so far there is no
97 complete documentation.
98
99------------------------------------------------------------
100
101DJGPP.
102
103The Unix-like environment DJGPP can be used to run nauty and gtools on
104DOS/Win computers. DJGPP is available at http://www.delorie.com/djgpp .
105The program shortg does not work since DJGPP does not provide a working
106pipe() system call. Using the bash shell is recommended. In DOS,
107Windows NT and early Windows editions, you will need to convert all
108long file names to the 8+3 limits. Thanks to Guenter Sterntenbrink
109for helping with this.
110
111If configure gives an error message similar to this:
112 can not guess host type: you must specify one
113then try
114 ./configure --host=i686
115or use i586 for Pentium 2. If all of those fail, try
116 ./configure --host=unknown
117
118------------------------------------------------------------
119
120Making 32-bit executables on 64-bit Linux systems.
121
122(In bash or sh:)
123CFLAGS=-m32 CXXFLAGS=-m32 LDFLAGS=-m32 ./configure
124make clean; make
125
126This requires the libraries ia32-libs and libc6-dev-i386.
127
128------------------------------------------------------------
129
130RECENT CHANGES.
131
132Here we list substantive changes made since the first 2.2 release.
133
134Nov 16, 2002: Replaced rng.c after communication with Don Knuth.
135 The previous version had a bug (mine!) when there was no explicit
136 initialization done by the user. It appears the error had no
137 impact on nauty (which only uses rng.c for the "s" command in
138 dreadnaut, and for genrang, but both always initialize).
139 No change to the nauty version number but beta=2.
140
141Nov 18, 2000: Adjusted the makefile and countg/testg to work in
142 the DOS/Win environment DJGPPP (see the previous section).
143
144May 1, 2003: Fixed PRUNE feature of genbg.
145
146May 3, 2003: Added utility directg for making all orientations of graphs.
147
148Oct 4, 2003: Added options -a, -Z, -d, -z to genbg. Also, the -l
149 (canonical label) option now preserves the colouring.
150
151Nov 17, 2003: Renamed INFINITY to NAUTY_INFINITY since many C header
152 libraries define INFINITY. If INFINITY is not defined by
153 the system, you can still use it.
154
155Nov 19, 2003: Added program biplabg to relabel bipartite graphs with the
156 colour classes contiguous.
157
158Feb 13, 2004: Revised C options for solaris on pentium
159
160Mar 1, 2004: dretog knows !...\n type of comment
161
162May 7, 2004: geng can be called from another program (see instructions
163 in geng.c.)
164
165May 29, 2004: added definition of SETWORD_FORMAT used to write a setword
166 with printf( ) - see nauty.h
167
168Sep 11, 2004: Added utility multig for making multigraphs based on
169 provided simple graphs; similar to directg
170
171Oct 16, 2004: To avoid problems caused by system-dependent handling of
172 external declarations, nauty() no longer accepts NULL as
173 the value of options.dispatch. To get the previous
174 behaviour, use the value &graph_dispatch. This will be
175 handled automatically if programs calling nauty use
176 DEFAULTOPTIONS to declare options and are recompiled.
177 Even better is to use DEFAULTOPTIONS_GRAPH.
178
179May 5, 2005: A bug in the writing of sparse6 was found and fixed.
180 This is procedure ntos6() in gtools.c, which is invoked
181 by writes6(). The bug could only happen if all the
182 following are true:
183 1. n = 2, 4, 8 or 16 (for n=2, only if the graph has loops)
184 2. Vertex n-2 has non-zero degree, but vertex n-1 has
185 zero degree.
186 These conditions never happen for graphs generated by
187 geng or genbg, nor for regular graphs or connected graphs,
188 nor for graphs canonically labelled by nauty (except maybe
189 with some unusual vertex colouring or invariant).
190 If the conditions do happen, the buggy routine may
191 (with some probability) add a spurious loop to vertex n-1.
192
193 In the package is a utility checks6:
194
195 Usage: checks6 [-w] [infile [outfile]]
196 Check a file of graphs, optionally write corrected version
197 -w Write corrected graphs (default is not to write)
198
199------now we start version 2.3 (not released) and 2.4------
200
201Nov 10, 2004: Use faster routine getc_unlocked() for reading graphs if
202 available. It can make a surprising difference.
203
204Nov 17, 2004: If putenv() or setenv() are available, we set LC_COLLATE to
205 "C" before executing "sort" in shortg. This should alleviate
206 collation issues with sort. However, note that many
207 utilities use the locale these days so you are advised to
208 have LC_COLLATE defined to be "C" always when you are dealing
209 with files of graphs.
210
211 Six counters in statsblk became "unsigned long" instead of
212 "long". nauty doesn't actually use these, but we might as
213 well give them twice as long before they overflow.
214
215Nov 24, 2004: Made geng faster for generating trees. The output labelling
216 may be different from before. A very much faster tree
217 generator is in the works.
218
219Jan 17, 2005: Added two items to dispatch vectors:
220 init : used for initialising something at the start
221 cleanup : used for doing something at the end, such as
222 freeing space allocated by init()
223 See the manual for calling sequences.
224
225May 20, 2005: Update graph6 and sparse6 formats to allow much large sizes.
226 The limit is now 68719476735 vertices (best of luck getting
227 close to that!).
228
229Nov 12, 2005: Changed NAUTY_INFINITY to 2^30+2 in BIGNAUTY case
230
2312006 various: Procedures for sparse graphs implemented.
232
233 New program planarg to test for planarity and find
234 planar embeddings: planarg -help for details.
235 The planarity code was written by Paulette Lieby for the
236 Magma project and used with permission.
237
238 labelg got -S to use sparse graphs.
239 genbg -N changed to genbg -n (only Gordon uses this).
240 genrang gained -R switch for regular graphs in text format.
241 gtools.c has code for reading and writing planarcode.
242 listg got a compile time option to select "Matrix" or
243 "array" for Maple output.
244 pickg/countg got -T for counting triangles
245
246 Better configuration for MacOSX.
247
248Nov 22, 2006: Removed usertcellproc from options. Greater functionality
249 is now available using the new targetcell field in the
250 dispatch vector. The u8 command has gone from dreadnaut.
251
252 Changed bestcell to targetcell in dispatch vector.
253
254Nov 29, 2006: Added extraoptions field (currently unused) to optionblk
255
256Dec 9, 2006: Added an invariant adjacencies_sg(), recommended for digraphs
257 when using sparse representation.
258
259Dec 10, 2006: Remove BIGNAUTY, whose usefulness has passed. Now the types
260 shortish and permutation are synonymous with int always.
261 The limit on the number of vertices is 2^30 unless int
262 has only 16 bits (still any of them around?) in which
263 case it is 2^15-3. Programs previously linked with
264 files like nautyB.o can now be linked with nauty.o.
265 Alternatively, "make bigs" will create files like
266 nautyB.o by copying.
267
268June 26, 2007: Fixed an error in listg -s reported by Evan Heidtmann.
269
270July 12, 2007: Added -f option to directg.
271
272Aug 14, 2007: Added -i,-I,-K options to shortg, parallel to labelg.
273 Since -k is used in labelg in place of -I, changed labelg
274 to use -I also, with -k remaining as an undocumented
275 compatibility feature.
276
277Aug-Sep 2007: Minor things:
278 * naututil-h.in now defines CPUTIME=0.0 as a last resort
279 * gtools.c now implements EDGECODE (not used anywhere yet)
280 * fixed definition of SG_FREE in nausparse.h (not used)
281 * geng favours space over time for n > 28
282
283Oct 14, 2007: Added -T switch to shortg to specify scratch directory.
284
285Mar 3, 2008: Fixed makefile for compilation in a 64-bit environment.
286
287Oct 11, 2008: Added -l and -m to genrang
288
289Nov 29, 2008: Slightly improved -c for geng and genbg
290 Added tournament generator gentourng.
291
292Mar 3, 2009: Added -V to directg.
293