/
search_all.go
486 lines (420 loc) · 13.5 KB
/
search_all.go
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
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
package search
import (
"encoding/gob"
"io"
"math/bits"
"github.com/Tom-Johnston/mamba/comb"
"github.com/Tom-Johnston/mamba/disjoint"
"github.com/Tom-Johnston/mamba/graph"
"github.com/Tom-Johnston/mamba/ints"
"github.com/Tom-Johnston/mamba/itertools"
)
//GraphIterator is an iterator which iterates over all non-isomorphic graphs. It should be initialised with either All or WithPruning.
//The current state of the iterator can be saved with Save() and then this can be loaded again using Resume().
//A GraphIterator is not safe for concurrent use by multiple goroutines.
type GraphIterator struct {
n int
a int
m int
first bool
preprune func(g *graph.DenseGraph) bool
prune func(g *graph.DenseGraph) bool
splitLevel int
sg *searchGraph
//Storage etc. for the CanonicalIsomorphCustom
storage *graph.CanonicalStorage
op *graph.CanonicalOrderedPartition
options *graph.CanonicalOptions
ds disjoint.Set
//Options for the DFS
choices []uint
currentPath []int
//Storage for the DFS
v []int
}
//All with a = 0 and m = 1 returns a *GraphIterator which iterates over all graphs on n vertices. In general, the iterator uses a canonical deletion DFS to find all graphs on at most n vertices where the choice at level ceil(2n/3) - 1 is equal to a mod m. For small values of m this should produce a fairly even split and allow for some small parallelism.
func All(n int, a int, m int) *GraphIterator {
return WithPruning(n, a, m, func(g *graph.DenseGraph) bool { return false }, func(g *graph.DenseGraph) bool { return false })
}
//WithPruning with a = 0 and m = 1 returns a *GraphIterator which iterates over all non-isomorphic graphs on n vertices such that neither the graph itself nor any of its predecessors were pruned.
//The function preprune is called as soon as the augmentation is applied to the graph, and the function prune is called once the augmentation has been checked to be canonical.
//Note that the vertices are added in the order 0, 1, ..., n-1 and, when adding the kth vertex, the graph induced on {0, 1, \dots, k-2} has already been checked for pruning (and has not been pruned).
//Only the graphs generated by making a choice which is equal to a mod m at level ceil(2n/3) - 1 are checked. This allows for some small parallelism.
func WithPruning(n int, a int, m int, preprune, prune func(g *graph.DenseGraph) bool) *GraphIterator {
iter := new(GraphIterator)
iter.n = n
iter.a = a
iter.m = m
iter.preprune = preprune
iter.prune = prune
iter.first = true
//Intitialise a graph large enough to hold a graph on n vertices and then reset it to the empty graph.
g := graph.NewDense(n, nil)
g.NumberOfVertices = 0
g.DegreeSequence = g.DegreeSequence[:0]
g.Edges = g.Edges[:0]
//Initialise storage for the neighbours.
neighbours := make([][]int, n)
for i := range neighbours {
neighbours[i] = make([]int, 0, n)
}
iter.sg = &searchGraph{G: g, Neighbours: neighbours, Generators: nil, Orbits: nil}
//Initialise the storage etc. for CanonicalIsomorphCustom
storage := graph.NewStorage(n, (n*(n-1))/2)
op := graph.NewOrderedPartition(n, (n*(n-1))/2, nil)
options := new(graph.CanonicalOptions)
iter.storage = storage
iter.op = op
iter.options = options
//Initialise storage which will be used when checking what sets of neighbours we should try to add.
ds := make(disjoint.Set, comb.Coeff(n, n/2))
iter.ds = ds
//Initialise the options for the DFS
// iter.choices = make([]uint, 0)
iter.currentPath = make([]int, 0, n)
iter.v = make([]int, 0, n)
iter.splitLevel = 2*(n+1)/3 - 1
return iter
}
//Next attempts to move the iterator to the next graph, returning true if there is a next graph and false if it has iterated over all graphs.
func (iter *GraphIterator) Next() bool {
//Handle a couple of small cases so that we can start with a graph with 1 vertex and expand from there.
//We could embed the function Next as a variable instead and split the cases n == 0 and n == 1 into separate functions. This would save the check, but the speed difference is currently tiny and it is not as "nice".
if iter.n == 0 {
if iter.first && iter.a == 0 && !iter.preprune(iter.sg.G) && !iter.prune(iter.sg.G) {
iter.first = false
return true
}
return false
}
if iter.n == 1 {
iter.sg.G.NumberOfVertices = 1
iter.sg.G.DegreeSequence = iter.sg.G.DegreeSequence[:1]
if iter.first && iter.a == 0 && !iter.preprune(iter.sg.G) && !iter.prune(iter.sg.G) {
iter.first = false
return true
}
return false
}
cont := true
if iter.first {
iter.sg.G.NumberOfVertices = 1
iter.sg.G.DegreeSequence = iter.sg.G.DegreeSequence[:1]
iter.first = false
if iter.preprune(iter.sg.G) || iter.prune(iter.sg.G) {
return false
}
cont = false
}
stepForward := false
for true {
if !cont {
if iter.sg.G.NumberOfVertices == iter.n {
return true
} else {
//Prepare to go deeper.
numAugs := addAugmentations(iter.sg, &iter.choices, iter.ds, iter.op, iter.storage, iter.options)
iter.currentPath = append(iter.currentPath, numAugs)
stepForward = true
}
} else {
cont = false
}
//Step loop
stepLoop:
for true {
if len(iter.choices) == 0 {
return false
}
for i := iter.currentPath[len(iter.currentPath)-1] - 1; i >= 0; i-- {
//Splitting
level := len(iter.currentPath)
x := iter.choices[len(iter.choices)-1]
iter.choices = iter.choices[:len(iter.choices)-1]
if i%iter.m != iter.a && level == iter.splitLevel {
continue
}
iter.v = iter.v[:0]
for x != 0 {
//y isolates the least significant bit in x
y := x & -x
//The index is the number of trailing zeros.
iter.v = append(iter.v, bits.TrailingZeros(x))
//Unset the least significant bit
x ^= y
}
//Are we moving deeper or to the next child?
if !stepForward {
iter.sg.G.RemoveVertex(iter.sg.G.NumberOfVertices - 1)
clearAutomorphismGroup(iter.sg)
}
stepForward = false
//Take the step
iter.sg.G.AddVertex(iter.v)
clearAutomorphismGroup(iter.sg)
//Check if this should be prepruned.
if iter.preprune(iter.sg.G) {
continue
}
//Are we canonical and should we be pruned?
if isCanonical(iter.sg, iter.v, iter.op, iter.storage, iter.options) && !iter.prune(iter.sg.G) {
//This step is valid so we are done.
iter.currentPath[len(iter.currentPath)-1] = i
break stepLoop
}
}
//None of the options on this level worked so take a step back
if !stepForward {
iter.sg.G.RemoveVertex(iter.sg.G.NumberOfVertices - 1)
clearAutomorphismGroup(iter.sg)
}
stepForward = false
iter.currentPath = iter.currentPath[:len(iter.currentPath)-1]
}
}
return false
}
//Value returns the current value of the iterator. You must not modify the returned value.
func (iter *GraphIterator) Value() *graph.DenseGraph {
return iter.sg.G
}
//save stores the state of a GraphIterator needed to load the iterator later.
type save struct {
N int
A int
M int
First bool
G *graph.DenseGraph
Choices []uint
CurrentPath []int
}
//Save writes the current state of the iterator to w so that it can be loaded using Load. This doesn't save the functions preprune and prune which will need to be supplied to Load on loading.
//This cannot be called concurrently with Next and can only be called between graphs.
func (iter *GraphIterator) Save(w io.Writer) {
//Create and fill a save struct.
s := new(save)
s.N = iter.n
s.A = iter.a
s.M = iter.m
s.First = iter.first
s.G = iter.sg.G
s.Choices = iter.choices
s.CurrentPath = iter.currentPath
//Encode the save struct using gob.
enc := gob.NewEncoder(w)
err := enc.Encode(s)
if err != nil {
panic(err)
}
}
//Load creates a new *GraphIterator from the saved information in r.
func Load(r io.Reader, preprune, prune func(g *graph.DenseGraph) bool) *GraphIterator {
//Decode the saved state into s.
s := new(save)
dec := gob.NewDecoder(r)
err := dec.Decode(s)
if err != nil {
panic(err)
}
//Create a new iterator in the starting state.
iter := WithPruning(s.N, s.A, s.M, preprune, prune)
//Overwrite the relevant parts of the starting state.
iter.first = s.First
iter.choices = s.Choices
iter.currentPath = s.CurrentPath
//Note that the graph s.G might not be correctly sized so we will copy into the allocation.
iter.sg.G.NumberOfVertices = s.G.NumberOfVertices
iter.sg.G.NumberOfEdges = s.G.NumberOfEdges
iter.sg.G.DegreeSequence = iter.sg.G.DegreeSequence[:s.G.NumberOfVertices]
copy(iter.sg.G.DegreeSequence, s.G.DegreeSequence)
iter.sg.G.Edges = iter.sg.G.Edges[:len(s.G.Edges)]
copy(iter.sg.G.Edges, s.G.Edges)
return iter
}
//searchGraph holds a graph and the information from the canonical isomorph.
//Note that Perm, Generators and Orbits are not necessarily deep copies of the relevant part of storage.
type searchGraph struct {
G *graph.DenseGraph
Neighbours [][]int //We don't keep this up to date yet.
Perm []int
Generators [][]int
Orbits disjoint.Set
}
func updateNeighbours(sg *searchGraph) {
sg.Neighbours = sg.Neighbours[:sg.G.NumberOfVertices]
for v := 0; v < sg.G.NumberOfVertices; v++ {
r := sg.Neighbours[v][:0]
tmp := (v * (v - 1)) / 2
for i := 0; i < v; i++ {
index := tmp + i
if sg.G.Edges[index] > 0 {
r = append(r, i)
}
}
for i := v + 1; i < sg.G.NumberOfVertices; i++ {
index := (i*(i-1))/2 + v
if sg.G.Edges[index] > 0 {
r = append(r, i)
}
}
sg.Neighbours[v] = r
}
}
func getAutomorphismGroup(sg *searchGraph, op *graph.CanonicalOrderedPartition, storage *graph.CanonicalStorage, options *graph.CanonicalOptions) {
op.Reset(sg.G.NumberOfVertices, sg.G.NumberOfEdges, nil)
updateNeighbours(sg)
perm, orbits, generators := graph.CanonicalIsomorphAllocated(sg.G.NumberOfVertices, sg.G.NumberOfEdges, sg.Neighbours, op, storage, options)
sg.Perm = perm
sg.Generators = generators
sg.Orbits = orbits
}
func clearAutomorphismGroup(sg *searchGraph) {
sg.Perm = nil
sg.Generators = nil
sg.Orbits = nil
}
func addAugmentations(sg *searchGraph, choices *[]uint, ds disjoint.Set, op *graph.CanonicalOrderedPartition, storage *graph.CanonicalStorage, options *graph.CanonicalOptions) int {
n := sg.G.NumberOfVertices
minDegree := ints.Min(sg.G.DegreeSequence)
maxSize := minDegree + 1
numFound := 0
//TODO Reuse some preallocated space in augs?
//TODO Do we want to be blocking obviously non-canonical sets?
//No point checking a set of of minDegree + 1 if we aren't adjacent to a vertex of min degree for example.
//Handle k == 0 separately
numFound++
*choices = append(*choices, 0)
//For all the other large sets we will want the generators
if sg.Perm == nil {
options.CheckViability = false
getAutomorphismGroup(sg, op, storage, options)
}
//Handle k == 1 separately
for i, v := range sg.Orbits {
if v < 0 {
*choices = append(*choices, (1 << uint(i)))
numFound++
}
}
//We are just going to be dumb here.
//This really needs improving.
//TODO IMPORTANT This is basically the slowest bit
for k := 2; k <= maxSize; k++ {
ds = ds[:comb.Coeff(n, k)]
for i := range ds {
ds[i] = -1
}
//TODO Should these be passed in.
buf := make([]int, n)
iter := itertools.CombinationsColex(n, k)
c2 := make([]int, k)
for i := 0; i < len(ds); i++ {
iter.Next()
c := iter.Value()
for _, g := range sg.Generators {
for j := 0; j < k; j++ {
c2[j] = g[c[j]]
}
ints.Sort(c2)
ds.UnionBuffered(i, comb.Rank(c2), buf)
}
}
iter = itertools.CombinationsColex(n, k)
for i := 0; i < len(ds); i++ {
iter.Next()
if ds[i] < 0 {
x := 0
for _, v := range iter.Value() {
x |= (1 << uint(v))
}
*choices = append(*choices, uint(x))
numFound++
}
}
}
return numFound
}
func isCanonical(sg *searchGraph, aug []int, op *graph.CanonicalOrderedPartition, storage *graph.CanonicalStorage, options *graph.CanonicalOptions) bool {
n := sg.G.NumberOfVertices
viableBits := uint(0)
degrees := sg.G.DegreeSequence
//Check the degree
degree := degrees[n-1]
for i := 0; i < n-1; i++ {
if degrees[i] < degree {
return false
} else if degrees[i] == degree {
viableBits |= (1 << uint(i))
}
}
if viableBits == 0 {
return true
}
//Sums and squares of degrees
sum := 0
square := 0
for _, v := range aug {
sum += degrees[v]
square += degrees[v] * degrees[v]
}
sumV := 0
squareV := 0
x := uint(viableBits)
for x != 0 {
//y isolates the least significant bit in x
y := x & -x
//The index is the number of trailing zeros.
v := bits.TrailingZeros(x)
//Unset the least significant bit
x ^= y
sumV = 0
squareV = 0
for j := 0; j < n; j++ {
if v > j {
if sg.G.Edges[(v*(v-1))/2+j] == 1 {
sumV += degrees[j]
squareV += degrees[j] * degrees[j]
}
} else if v < j {
if sg.G.Edges[(j*(j-1))/2+v] == 1 {
sumV += degrees[j]
squareV += degrees[j] * degrees[j]
}
}
}
if sumV > sum {
return false
} else if sumV < sum {
viableBits ^= (1 << uint(v))
} else if squareV > square {
return false
} else if squareV < square {
viableBits ^= (1 << uint(v))
}
}
if viableBits == 0 {
return true
}
//TODO Lexicographic degrees?
//We must now check the canonical isomorph
if sg.Perm == nil {
//Set the options for checking viability since it will sometimes let us return early.
options.CheckViability = true
options.ViableBits = viableBits
getAutomorphismGroup(sg, op, storage, options)
}
if sg.Perm == nil {
//Still nil means that we returned early.
return false
}
correctAnswer := sg.Orbits.Find(n - 1)
for _, u := range sg.Perm {
if u == n-1 {
return true
}
if viableBits>>uint(u)&1 == 1 {
return correctAnswer == sg.Orbits.Find(u)
}
}
return true
}