forked from lonnen/nauty
-
Notifications
You must be signed in to change notification settings - Fork 1
/
Copy pathchanges24-27.txt
316 lines (259 loc) · 13.2 KB
/
changes24-27.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
Changes from nauty 2.4 to nauty 2.5
-----------------------------------
* Add Traces. The main files are traces.h and traces.c, but
many changes were made to dreadnaut.c and nausparse.c also.
* Allow thread-safe storage if requested by configure --enable-tls
and available. This allows parallel running of nauty and Traces
in separate threads.
* The makefile now creates static libraries like nauty.a in
addition to object files like nauty.o.
* Remove all use of types permutation, nvector, np2vector, shortish.
These are now int.
* Add schreier.h, schreier.c and the optional use of the random
Schreier method in nauty. These are also used in Traces, but
are not optional there.
* Add large-file support to all programs, assuming it is available.
Now there is no longer a 4GB limit on files read or written on
32-bit systems.
* Use gcc extensions like __builtin_clz() if available and not
disabled by configure --disable-clz.
Use FIRSTBITNZ instead of FIRSTBIT if the argument is certain
to be nonzero.
* New macros defined in nauty.h:
COUNTER_FMT
PRINT_COUNTER
SETWORDSNEEDED
ADDONEARC
ADDONEEDGE
EMPTYGRAPH
* The options structure has a new boolean field schreier.
* New procedures:
densenauty() in naugraph.c - simplified dense graph interface
sparsenauty() in nausparse.c - simplified sparse graph interface
writegroupsize() in nautil.c - write two part group size
copy_sg() in nausparse.c - make a copy of a sparse graph
densenauty() and sparsenauty() are now the recommended ways to
call nauty from a program. See the sample programs in the package.
* Use quicksort in place of shell sort in many places. This is
implemented in the file sorttemplates.c that can be used in any
applications.
* Apply the const attribute more liberally across the code.
* The sparsegraph fields nde and *v changed type from int to size_t.
This is to allow more than 2^31 edges on 64-bit hardware.
* sparsegraph.h and sparsegraph.c:
Corrected definition of SG_DECL in sparsegraph.h. (The erroneous
definition would have worked but generated warnings.)
Added DEFAULTOPTIONS_SPARSEDIGRAPH.
Added comparelab_tr(), testcanlab_tr(), updatecan_tr() for Traces.
* gtools.h and gtools.c:
Now gtools.h is made from gtools-h.in by configure.
Updated G6LEN() to work for larger graphs.
Use large-file functions fseeko(), ftello() if possible.
* Most tools now use the random number generator in naurng.c rather
than that in rng.c.
* gutils.h, gutil1.c and gutil2.c:
New procedures maxcliques(), indpathcount1(), indcyclecount1(),
indcyclecount().
* Invariants:
Corrected getbigcells(), making a small change to invariants
celltrips, cellquins and refinvar.
* dreadnaut:
Sparse nauty and Traces now incorported.
New commands: A, G, F, FF, sr, O, OO, P, PP, S, V
w command is now in units of 2*m.
Command-line can run commands using -o.
M command is extended; now applies to i as well as x.
Implement ANSI controls if requested.
File names for > and < can be given in "..." to allow spaces.
* Updates to utilities:
listg: add -b (Bliss format), -G (GRAPE format) and
-y/-Y (dotty format), -H (HCP format)
labelg: add -t (Traces) and -i16 (refinvar)
countg/pickg: add -m (vertices of min degree),
-M (vertices of max degree), -H (induced cycles),
-K (number of maximal independent sets)
genrang: add -t (tree)
genbg: add -A (antichain)
The makefile can also make genbgL which makes larger sizes
directg: add PROCESS feature
shortg: -S (use sparse nauty), -t (use traces), i16 (refinvar)
* New utilities:
ranlabg: randomly relabel graphs
linegraphg: compute linegraphs
subdivideg: compute subdivision graphs
watercluster2: orient edges of graphs (by Gunnar Brinkmann)
* Version 25r2 fixed a rare bug in Traces
* Version 25r3 fixed some problems in the configure script (thanks to Daniel Grayson)
Changes from nauty 2.5 to nauty 2.6
-----------------------------------
Changes to dreadnaut:
* dreadnaut now catches control-C when nauty or Traces is running.
This uses the global variable nauty_kill_request.
* new command "vv" to display sorted degree sequence.
* new command "r&" to relabel according to the partition.
* new command "->>" to flush the output.
* new command "B" to turn on output flushing at the end of every
command. Command "-B" turns it off. Default off.
* Command with short arguments now have to be all on one line.
Most errors cause the rest of the input line to be skipped.
* The "R" command now preserves the colouring.
Changes to nauty:
* nauty has an extra hook usercanonproc().
* The maximum number of vertices is now 2 billion.
* Many modern processors have instructions POPCNT and CLZ* that can
help nauty. The configuration script now looks for them and
attempts to use them if possible.
New file formats (see formats.txt for definitions):
* sparse6 format is now extended with "incremental sparse6"
format. Graphs in incremental sparse6 format specify only the
differences from the previous graph.
As yet, incremental sparse6 is only supported by copyg (which
has new options -i/-I to write this format), listg, pickg and
countg. For listg, pickg and countg, the -p switch might not work
if the input is incremental.
* The new format digraph6 is for directed graphs. There are
procedures for reading and writing it in gtools.c.
The following programs can handle digraph6 so far:
labelg, shortg, ranlabg, directg, gentourng, amtog, complg,
copyg, dretog, catg, listg, showg, converse, converseg, delptg,
deledgeg, countg/pickg (partially), genrang (partially), genspecialg
New utilities:
* converseg : take converse of a digraph
* cubhamg : hamiltonian cycles in subcubic graphs
* hamheuristic : heuristic for hamiltonian cycles
* twohamg : partition quartic graphs into two hamiltonian cycles
* genspecialg : generate special graphs like paths and cycles
* gentreeg : generateg trees, based on a program of Li and Ruskey.
* genquarticg : generate quartic graphs, written with Narjess Afzaly.
* dretodot : reads one graph in dreadnaut format and writes a picture
of it in dot format. You can use tools in the graphviz library
to deal with it.
* vcolg : colours the vertices of graphs in all distinct ways.
If you choose the number of colours to be 2, this the same as
adding loops in all distinct ways.
* delptg : delete vertices.
As always, run the command with argument "-help" to get instructions.
Extra options in existing utilities:
* amtog now properly handles loops. (Recall that loops are ok
in sparse6 format but not in graph6 format.)
amtog has a switch -o that allows selecting one colour class of
a coloured graph, and -w to suppress the warning about loops.
* copyg has -z for writing digraph6 format. An undirected graph
can be written as a digraph, but not vice-versa.
* directg default output format is directg6.
directg has a new option -s for splitting into cases.
* dretog allows "d" command for digraph input.
* Option -B added to countg and pickg.
* complg has new option -R.
* genrang has new option -d that makes random regular graphs of
any degree but does not guarantee uniform distribution.
Also option -T for random tournaments.
Some options now work for bipartite graphs; specify the number
of vertices on each side like n1,n2.
* labelg has extra options -C and -W. These can help to determine
what is different between two different programs that generate
almost the same output.
* linegraphg has -t for making the total graph.
* Most utilities can take a single argument --version, which will
print a message stating which nauty&traces package they belong to.
Other changes:
* Traces has substantial improvements.
* Extra argument macros SWDOUBLE, SWREALRANGE, SWSEQUENCE in gtools.h.
* girth() in gutil1.c got the wrong answer for K2. Thanks to
Sean Irvine for reporting it.
* gtools.c defines checkgline() to check if a graph input
line looks ok.
* The procedures in gtnauty.c, used by labelg and other utilities,
had an old limit of 2^22 (4 million+) vertices. This limit is
now removed. Also a new procedure setlabptn() was added to set
lab/ptn according to an integer weight.
* planarg -p had a bug causing wrong output for n >= 65536. Fixed.
* The structured type bigint has disappeared in favour of integer type
nauty_counter, which is "unsigned long long" if that exists and
"unsigned long" is only 32 bits, or "unsigned long" otherwise.
This means that some plugins for geng/genbg/gentourng may need
to be revised.
Changes from nauty 2.6 to nauty 2.7
-----------------------------------
* -h and -k options for independent set size and clique size were added
to countg and pickg. For some graphs these use the program cliquer,
kindly provided by Sampo Nisjkanen and Patric Ostergard.
* Macros SWHIBIT, REMOVEHIBIT and ATMOSTONEBIT added to nauty.h.
* Added option -a to complg.
* Program copyg can now be used to make a simple filter. See the
instructions inside the source file and the example numleaves.c.
* Programs countg and pickg can now display some parameter values
as ranges instead of writing a separate line for each value. For
example, countg --ne:T will write a separate line for each number
of vertices and edges, with that line showing the range of the
number of triangles. Everything after the ':' is shown as a range.
There is also a switch -1 that causes output to be in a simple
numerical table easy to read from a program and a similar switch
-2 that omits counts.
* Program vcolg now handles digraphs and graphs with loops.
* genrang can now make random spanning trees of K(n1,n2)
* amtog has an "s" command for reading tournaments
* gentreeg made the same tree twice for n=2; thanks to Kevin Ryde
for reporting it.
* The configure script (compiled from configure.ac) was modified to
update some tests and remove some old code that is useless. The
time-critical parts of nauty are now compiled with
-march=native
if the compiler allows those switches. Since this may result in
a binary which does not run on older machines in the same family,
there is a configuration option --enable-generic to disable
these switches. To work around a bug with -march-native for
gcc version 7 on MacOSX computers (due to the linker not knowing
some of the instructions), the extra switch -mno-avx is also added
if it appears necessary.
* genspecialg can now make multiple special graphs at once.
The -b option has been extended to allow removing a matching from
a complete bipartite graph.
* watercluster2 has an option Z to write in digraph6 format.
* Problems for input of graphs with 0 vertices were fixed with help
from Kevin Ryde. However, note that many utilities in the package
will not work with such graphs. It is NOT TRUE that graphs of
order 0 are now supported. However, the primary function nauty()
(but not traces()) should work for both dense and sparse versions.
* Stronger measures are taken to ensure that the sort order used by
shortg is plain byte order. This corresponds to the C collation
order, also known as POSIX, but it may be different from the
collation order used by default on your command line. This means
that utilities like sort, uniq, comm and join might consider the
output of shortg to be out of order. To avoid this, define the
environment variable LC_ALL to equal the string "C".
bash: export LC_ALL=C
tcsh: setenv LC_ALL C
If LC_ALL is undefined, it will also be sufficient to define
LC_COLLATE to equal "C". The POSIX standard says that LC_ALL
takes precedence over LC_COLLATE if both are defined, but this
might not be true for older systems. If you really don't want
to change environment variables, you can compile shortg with
-DKEEP_SORT_LOCALE but beware that some collation orders are
are not even deterministic (i.e. different characters might
compare equal).
* The bipartite graph generator genbg now has a -Y switch to
specify the minimum number of common neighbours for two
vertices on the second side.
* A new version of Traces (including some bug fixes) is included.
See traces.c for more.
* New utilities: underlyingg takes the undirected graph underlying
a graph or digraph. assembleg combines a file of graphs (usually
connected graphs) as components to make disconnected graphs
of a specified size.
* geng has been modified to allow more than 32 vertices. The
makefile knows "geng" for up to 32 vertices, and "gengL" for
up to 64 vertices.
* pickg and countg now have -X to reverse the selection.
A change was made to allow these utilities to work on Windows
computers with sizeof(long) < sizeof(void*). Also, pickg
now writes a header if there is one in the input file.
* listg has -L that can be used in conjunction with -W or -M to
write the Laplacian matrix instead of the adjacency matrix.
* Fixed a possible bug in the combination "shortg -kt".
* You can change the archive manager (default "ar") by defining
the environment variable AR at configure time.
* Some portability issues in nautycliquer.c were fixed (thanks
to Isuru Fernando).
* More information is provided to PRUNE/PREPRUNE plugins of geng.
* -q suppresses the "c" lines in Bliss output of listg.