Debian Codegraph @

README_24

raw
1 README file for nauty 2.4
2 This file is only of historical interest as this version is very old.
3
4 Brendan McKay, [email protected]
5
6 ------------------------------------------------------------
7
8 The most recent distribution of nauty can be found at
9 http://cs.anu.edu.au/~bdm/nauty .
10
11 The manual nug.pdf is available at that site and is also included
12 in the distribution package.
13
14 Note that nauty is copyright but free to use for most purposes.
15 The details are in the file nauty.h.
16
17 The code in the file planarity.c (used by the planarg program)
18 is copyright to the Magma project.
19
20 ------------------------------------------------------------
21
22 INSTALLATION.
23
24 The first step is to unpack the archive. On Unix-ish systems
25 you can use one of these commands:
26
27 tar xzf nauty24.tar.gz
28 or
29 gunzip -c nauty24.tar.gz | tar xf -
30
31 This will write all the files into the subdirectory nauty24.
32 Go to that directory.
33
34 If you have a working shell, and make, you can run
35 ./configure
36 followed by
37 make all
38 to compile nauty for your system.
39
40 If that succeeds without problem, you will have have the
41 program dreadnaut ready to run.
42
43 If you have problems during compilation, it may be that the
44 configuration scripts are inadequate for your system. Usually it
45 is because of some missing system header, incompatible typedef,
46 or similar. Please send the details to the author.
47
48 If you don't have a shell or make, manually edit the files nauty.h,
49 naututil.h and gtools.h as distributed. The parts between the lines
50 ======= near the start are the main things to look at. After this
51 manual editing, you can use makefile as a guide to compilation.
52
53 Programs which use an older version of nauty need to be
54 recompiled (** not just relinked **). Make sure they use the
55 DEFAULTOPTIONS_GRAPH or DEFAULTOPTIONS_SPARSEGRAPH macro to define
56 the fields of the options parameter.
57
58 See below for compiling on a PC under DJGPP.
59
60 If you are using Windows in an environment that needs Windows line
61 endings (which is a configuration option in Cygwin, for example),
62 then you might prefer to use nauty24.zip rather than
63 nauty24.tar.gz.
64
65 ------------------------------------------------------------
66
67 TESTING.
68
69 After compiling nauty successfully, it is recommended that you run
70 the included test programs. The simplest way is
71 make checks
72
73 ------------------------------------------------------------
74
75 MAILING LIST.
76
77 There is a mailing list for announcements and discussion about
78 nauty and related topics. You can subscribe at
79 http://dcsmail.anu.edu.au/cgi-bin/mailman/listinfo/nauty-list
80
81 ------------------------------------------------------------
82
83 OTHER FILES IN THE PACKAGE.
84
85 A few additional goodies are included.
86
87 sumlines.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
94 naugroup.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
101 DJGPP.
102
103 The Unix-like environment DJGPP can be used to run nauty and gtools on
104 DOS/Win computers. DJGPP is available at http://www.delorie.com/djgpp .
105 The program shortg does not work since DJGPP does not provide a working
106 pipe() system call. Using the bash shell is recommended. In DOS,
107 Windows NT and early Windows editions, you will need to convert all
108 long file names to the 8+3 limits. Thanks to Guenter Sterntenbrink
109 for helping with this.
110
111 If configure gives an error message similar to this:
112 can not guess host type: you must specify one
113 then try
114 ./configure --host=i686
115 or use i586 for Pentium 2. If all of those fail, try
116 ./configure --host=unknown
117
118 ------------------------------------------------------------
119
120 Making 32-bit executables on 64-bit Linux systems.
121
122 (In bash or sh:)
123 CFLAGS=-m32 CXXFLAGS=-m32 LDFLAGS=-m32 ./configure
124 make clean; make
125
126 This requires the libraries ia32-libs and libc6-dev-i386.
127
128 ------------------------------------------------------------
129
130 RECENT CHANGES.
131
132 Here we list substantive changes made since the first 2.2 release.
133
134 Nov 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
141 Nov 18, 2000: Adjusted the makefile and countg/testg to work in
142 the DOS/Win environment DJGPPP (see the previous section).
143
144 May 1, 2003: Fixed PRUNE feature of genbg.
145
146 May 3, 2003: Added utility directg for making all orientations of graphs.
147
148 Oct 4, 2003: Added options -a, -Z, -d, -z to genbg. Also, the -l
149 (canonical label) option now preserves the colouring.
150
151 Nov 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
155 Nov 19, 2003: Added program biplabg to relabel bipartite graphs with the
156 colour classes contiguous.
157
158 Feb 13, 2004: Revised C options for solaris on pentium
159
160 Mar 1, 2004: dretog knows !...\n type of comment
161
162 May 7, 2004: geng can be called from another program (see instructions
163 in geng.c.)
164
165 May 29, 2004: added definition of SETWORD_FORMAT used to write a setword
166 with printf( ) - see nauty.h
167
168 Sep 11, 2004: Added utility multig for making multigraphs based on
169 provided simple graphs; similar to directg
170
171 Oct 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
179 May 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
201 Nov 10, 2004: Use faster routine getc_unlocked() for reading graphs if
202 available. It can make a surprising difference.
203
204 Nov 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
215 Nov 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
219 Jan 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
225 May 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
229 Nov 12, 2005: Changed NAUTY_INFINITY to 2^30+2 in BIGNAUTY case
230
231 2006 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
248 Nov 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
254 Nov 29, 2006: Added extraoptions field (currently unused) to optionblk
255
256 Dec 9, 2006: Added an invariant adjacencies_sg(), recommended for digraphs
257 when using sparse representation.
258
259 Dec 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
268 June 26, 2007: Fixed an error in listg -s reported by Evan Heidtmann.
269
270 July 12, 2007: Added -f option to directg.
271
272 Aug 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
277 Aug-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
283 Oct 14, 2007: Added -T switch to shortg to specify scratch directory.
284
285 Mar 3, 2008: Fixed makefile for compilation in a 64-bit environment.
286
287 Oct 11, 2008: Added -l and -m to genrang
288
289 Nov 29, 2008: Slightly improved -c for geng and genbg
290 Added tournament generator gentourng.
291
292 Mar 3, 2009: Added -V to directg.