sage/graphs/graph_isom.pyx
| changeset 5445: |
98a2995b04f3 |
| parent: | 8e18a36e53cf |
| child: | 27959f5bf7f8 |
| author: |
Robert L Miller <rlm@robertlmiller.com> |
| date: |
Mon Jul 23 00:17:29 2007 -0700 (13 months ago) |
| permissions: |
-rw-r--r-- |
| description: |
fixed doctests after merge |
1"""
2N.I.C.E. - Nice (as in open source) Isomorphism Check Engine
3
4Automorphism group computation and isomorphism checking for graphs.
5
6This is an open source implementation of Brendan McKay's algorithm for graph
7automorphism and isomorphism. McKay released a C version of his algorithm,
8named nauty (No AUTomorphisms, Yes?) under a license that is not GPL
9compatible. Although the program is open source, reading the source disallows
10anyone from recreating anything similar and releasing it under the GPL. Also,
11many people have complained that the code is difficult to understand. The
12first main goal of NICE was to produce a genuinely open graph isomorphism
13program, which has been accomplished. The second goal is for this code to be
14understandable, so that computed results can be trusted and further derived
15work will be possible.
16
17To determine the isomorphism type of a graph, it is convenient to define a
18canonical label for each isomorphism class- essentially an equivalence class
19representative. Loosely (albeit incorrectly), the canonical label is defined
20by enumerating all labeled graphs, then picking the maximal one in each
21isomorphism class. The NICE algorithm is essentially a backtrack search. It
22searches through the rooted tree of partition nests (where each partition is
23equitable) for implicit and explicit automorphisms, and uses this information
24to eliminate large parts of the tree from further searching. Since the leaves
25of the search tree are all discrete ordered partitions, each one of these
26corresponds to an ordering of the vertices of the graph, i.e. another member
27of the isomorphism class. Once the algorithm has finished searching the tree,
28it will know which leaf corresponds to the canonical label. In the process,
29generators for the automorphism group are also produced.
30
31AUTHORS:
32 Robert L. Miller -- (2007-03-20) initial version
33 Tom Boothby -- (2007-03-20) help with indicator function
34 Robert L. Miller -- (2007-04-07--30) optimizations
35 (2007-07-07--14) PartitionStack and OrbitPartition
36 Tom Boothby -- (2007-07-14) datastructure advice
37 Robert L. Miller -- (2007-07-16--20) bug fixes
38
39REFERENCE:
40 [1] McKay, Brendan D. Practical Graph Isomorphism. Congressus Numerantium,
41 Vol. 30 (1981), pp. 45-87.
42
43NOTE:
44 Often we assume that G is a graph on vertices {0,1,...,n-1}.
45"""
46
47#*****************************************************************************
48# Copyright (C) 2006 - 2007 Robert L. Miller <rlmillster@gmail.com>
49#
50# Distributed under the terms of the GNU General Public License (GPL)
51# http://www.gnu.org/licenses/
52#*****************************************************************************
53
54include '../ext/cdefs.pxi'
55include '../ext/python_mem.pxi'
56include '../ext/stdsage.pxi'
57
58from sage.graphs.graph import Graph, DiGraph
59from sage.misc.misc import cputime
60from sage.rings.integer import Integer
61
62cdef class OrbitPartition:
63 """
64 TODO: documentation
65
66 EXAMPLES:
67 sage: from sage.graphs.graph_isom import OrbitPartition
68 sage: K = OrbitPartition(20)
69 sage: K.find(7)
70 7
71 sage: K.union_find(7, 12)
72 sage: K.find(12)
73 7
74 sage: J = OrbitPartition(20)
75 sage: J.is_finer_than(K, 20)
76 True
77 sage: K.is_finer_than(J, 20)
78 False
79
80 sage: from sage.graphs.graph_isom import OrbitPartition
81 sage: Theta1 = OrbitPartition(10)
82 sage: Theta2 = OrbitPartition(10)
83 sage: Theta1.union_find(0,1)
84 sage: Theta1.union_find(2,3)
85 sage: Theta1.union_find(3,4)
86 sage: Theta1.union_find(5,6)
87 sage: Theta1.union_find(8,9)
88 sage: Theta2.vee_with(Theta1, 10)
89 sage: for i in range(10):
90 ... print i, Theta2.find(i)
91 0 0
92 1 0
93 2 2
94 3 2
95 4 2
96 5 5
97 6 5
98 7 7
99 8 8
100 9 8
101
102 """
103
104 def __new__(self, int n):
105 cdef int k
106 self.elements = <int *> sage_malloc( n * sizeof(int) )
107 if not self.elements:
108 raise MemoryError("Error allocating memory.")
109 self.sizes = <int *> sage_malloc( n * sizeof(int) )
110 if not self.sizes:
111 sage_free(self.elements)
112 raise MemoryError("Error allocating memory.")
113 for k from 0 <= k < n:
114 self.elements[k] = -1
115 self.sizes[k] = 1
116
117 def __dealloc__(self):
118 sage_free(self.elements)
119 sage_free(self.sizes)
120
121 def find(self, x):
122 return self._find(x)
123
124 cdef int _find(self, int x):
125 if self.elements[x] == -1:
126 return x
127 self.elements[x] = self._find(self.elements[x])
128 return self.elements[x]
129
130 def union_find(self, a, b):
131 self._union_find(a, b)
132
133 cdef void _union_find(self, int a, int b):
134 cdef int aRoot, bRoot
135 aRoot = self._find(a)
136 bRoot = self._find(b)
137 self._union_roots(aRoot, bRoot)
138
139 def union_roots(self, a, b):
140 self._union_roots(a, b)
141
142 cdef void _union_roots(self, int a, int b):
143 if a < b:
144 self.elements[b] = a
145 self.sizes[b] += self.sizes[a]
146 elif a > b:
147 self.elements[a] = b
148 self.sizes[a] += self.sizes[b]
149
150 def is_finer_than(self, other, n):
151 return self._is_finer_than(other, n) == 1
152
153 cdef int _is_finer_than(self, OrbitPartition other, int n):
154 cdef int i
155 for i from 0 <= i < n:
156 if self.elements[i] != -1 and other.find(self.find(i)) != other.find(i):
157 return 0
158 return 1
159
160 def vee_with(self, other, n):
161 self._vee_with(other, n)
162
163 cdef void _vee_with(self, OrbitPartition other, int n):
164 cdef int i
165 for i from 0 <= i < n:
166 if self.elements[i] == -1:
167 self._union_roots(i, self.find(other.find(i)))
168
169 cdef int _is_min_cell_rep(self, int i):
170 if self.elements[i] == -1:
171 return 1
172 return 0
173
174 cdef int _is_fixed(self, int i):
175 if self.elements[i] == -1 and self.sizes[i] == 1:
176 return 1
177 return 0
178
179cdef OrbitPartition _orbit_partition_from_list_perm(int *gamma, int n):
180 cdef int i
181 cdef OrbitPartition O
182 O = OrbitPartition(n)
183 for i from 0 <= i < n:
184 if i != gamma[i]:
185 O._union_find(i, gamma[i])
186 return O
187
188cdef class PartitionStack:
189 """
190 TODO: documentation
191
192 EXAMPLES:
193
194 sage: from sage.graphs.graph_isom import PartitionStack
195 sage: P = PartitionStack([range(9, -1, -1)])
196 sage: P.sort_by_function(0, [2,1,2,1,2,1,3,4,2,1], 1, 10)
197 0
198 sage: P.sort_by_function(0, [2,1,2,1], 2, 10)
199 0
200 sage: P.sort_by_function(4, [2,1,2,1], 3, 10)
201 4
202 sage: P.sort_by_function(0, [0,1], 4, 10)
203 0
204 sage: P.sort_by_function(2, [1,0], 5, 10)
205 2
206 sage: P.sort_by_function(4, [1,0], 6, 10)
207 4
208 sage: P.sort_by_function(6, [1,0], 7, 10)
209 6
210 sage: P
211 ({5,9,7,1,6,2,8,0,4,3})
212 ({5,9,7,1},{6,2,8,0},{4},{3})
213 ({5,9},{7,1},{6,2,8,0},{4},{3})
214 ({5,9},{7,1},{6,2},{8,0},{4},{3})
215 ({5},{9},{7,1},{6,2},{8,0},{4},{3})
216 ({5},{9},{7},{1},{6,2},{8,0},{4},{3})
217 ({5},{9},{7},{1},{6},{2},{8,0},{4},{3})
218 ({5},{9},{7},{1},{6},{2},{8},{0},{4},{3})
219 ({5},{9},{7},{1},{6},{2},{8},{0},{4},{3})
220 ({5},{9},{7},{1},{6},{2},{8},{0},{4},{3})
221 sage: P.is_discrete(7)
222 1
223 sage: P.is_discrete(6)
224 0
225
226 sage: M = graphs.PetersenGraph().am()
227 sage: MM = []
228 sage: for i in range(10):
229 ... MM.append([])
230 ... for j in range(10):
231 ... MM[i].append(M[i][j])
232 sage: P = PartitionStack(10)
233 sage: P.split_vertex(0, 1)
234 sage: P.refine_by_square_matrix(MM, 1, [0], 10, 0)
235 sage: P
236 ({0,2,3,6,7,8,9,1,4,5})
237 ({0},{2,3,6,7,8,9},{1,4,5})
238 ({0},{2,3,6,7,8,9},{1,4,5})
239 ({0},{2,3,6,7,8,9},{1,4,5})
240 ({0},{2,3,6,7,8,9},{1,4,5})
241 ({0},{2,3,6,7,8,9},{1,4,5})
242 ({0},{2,3,6,7,8,9},{1,4,5})
243 ({0},{2,3,6,7,8,9},{1,4,5})
244 ({0},{2,3,6,7,8,9},{1,4,5})
245 ({0},{2,3,6,7,8,9},{1,4,5})
246 sage: P.split_vertex(1, 2)
247 sage: P.refine_by_square_matrix(MM, 2, [7], 10, 0)
248 sage: P
249 ({0,3,7,8,9,2,6,1,4,5})
250 ({0},{3,7,8,9,2,6},{1,4,5})
251 ({0},{3,7,8,9},{2,6},{1},{4,5})
252 ({0},{3,7,8,9},{2,6},{1},{4,5})
253 ({0},{3,7,8,9},{2,6},{1},{4,5})
254 ({0},{3,7,8,9},{2,6},{1},{4,5})
255 ({0},{3,7,8,9},{2,6},{1},{4,5})
256 ({0},{3,7,8,9},{2,6},{1},{4,5})
257 ({0},{3,7,8,9},{2,6},{1},{4,5})
258 ({0},{3,7,8,9},{2,6},{1},{4,5})
259
260
261 """
262 def __new__(self, data):
263 cdef int j, k, n
264 cdef PartitionStack _data
265 try:
266 n = int(data)
267 self.entries = <int *> sage_malloc( n * sizeof(int) )
268 if not self.entries:
269 raise MemoryError("Error allocating memory.")
270 self.levels = <int *> sage_malloc( n * sizeof(int) )
271 if not self.levels:
272 sage_free(self.entries)
273 raise MemoryError("Error allocating memory.")
274 for k from 0 <= k < n-1:
275 self.entries[k] = k
276 self.levels[k] = n
277 self.entries[n-1] = n-1
278 self.levels[n-1] = -1
279 except:
280 if isinstance(data, list):
281 n = sum([len(datum) for datum in data])
282 self.entries = <int *> sage_malloc( n * sizeof(int) )
283 if not self.entries:
284 raise MemoryError("Error allocating memory.")
285 self.levels = <int *> sage_malloc( n * sizeof(int) )
286 if not self.levels:
287 sage_free(self.entries)
288 raise MemoryError("Error allocating memory.")
289 j = 0
290 k = 0
291 for cell in data:
292 for entry in cell:
293 self.entries[j] = entry
294 self.levels[j] = n
295 j += 1
296 self.levels[j-1] = 0
297 self._percolate(k, j-1)
298 k = j
299 self.levels[j-1] = -1
300 elif isinstance(data, PartitionStack):
301 _data = data
302 j = 0
303 while _data.levels[j] != -1: j += 1
304 n = j + 1
305 self.entries = <int *> sage_malloc( n * sizeof(int) )
306 if not self.entries:
307 raise MemoryError("Error allocating memory.")
308 self.levels = <int *> sage_malloc( n * sizeof(int) )
309 if not self.levels:
310 sage_free(self.entries)
311 raise MemoryError("Error allocating memory.")
312 for k from 0 <= k < n:
313 self.entries[k] = _data.entries[k]
314 self.levels[k] = _data.levels[k]
315 else:
316 raise ValueError("Input must be an int, a list of lists, or a PartitionStack.")
317
318 def __dealloc__(self):
319 sage_free(self.entries)
320 sage_free(self.levels)
321
322 def __repr__(self):
323 k = 0
324 s = ''
325 while k == 0 or self.levels[k-1] != -1:
326 s += '({'
327 i = 0
328 while i == 0 or self.levels[i-1] != -1:
329 s += str(self.entries[i])
330 if self.levels[i] <= k:
331 s += '},{'
332 else:
333 s += ','
334 i += 1
335 s = s[:-2] + ')\n'
336 k += 1
337 return s
338
339 def is_discrete(self, k):
340 return self._is_discrete(k)
341
342 cdef int _is_discrete(self, int k):
343 cdef int i = 0
344 while True:
345 if self.levels[i] > k:
346 return 0
347 if self.levels[i] == -1: break
348 i += 1
349 return 1
350
351 def num_cells(self, k):
352 return self._num_cells(k)
353
354 cdef int _num_cells(self, int k):
355 cdef int i = 0, j = 1
356 while self.levels[i] != -1:
357 #for i from 0 <= i < n-1:
358 if self.levels[i] <= k:
359 j += 1
360 i += 1
361 return j
362
363 def sat_225(self, k, n):
364 return self._sat_225(k, n) == 1
365
366 cdef int _sat_225(self, int k, int n):
367 cdef int i, in_cell = 0
368 cdef int nontrivial_cells = 0
369 cdef int total_cells = self._num_cells(k)
370 if n <= total_cells + 4:
371 return 1
372 for i from 0 <= i < n-1:
373 if self.levels[i] <= k:
374 if in_cell:
375 nontrivial_cells += 1
376 in_cell = 0
377 else:
378 in_cell = 1
379 if in_cell:
380 nontrivial_cells += 1
381 if n == total_cells + nontrivial_cells:
382 return 1
383 if n == total_cells + nontrivial_cells + 1:
384 return 1
385 return 0
386
387 cdef int _is_min_cell_rep(self, int i, int k):
388 return i == 0 or self.levels[i-1] <= k
389
390 cdef int _is_fixed(self, int i, int k):
391 """
392 Assuming you already know it is a minimum cell representative.
393 """
394 return self.levels[i] <= k
395
396 def split_vertex(self, v, k):
397 """
398 Splits the cell in self(k) containing v, putting new cells in place
399 in self(k).
400 """
401 self._split_vertex(v, k)
402
403 cdef int _split_vertex(self, int v, int k):
404 cdef int i = 0, j
405 while self.entries[i] != v:
406 i += 1
407 j = i
408 while self.levels[i] > k:
409 i += 1
410 if j == 0 or self.levels[j-1] <= k:
411 self._percolate(j+1, i)
412 else:
413 while j != 0 and self.levels[j-1] > k:
414 self.entries[j] = self.entries[j-1]
415 j -= 1
416 self.entries[j] = v
417 self.levels[j] = k
418 return j
419
420 def percolate(self, start, end):
421 self._percolate(start, end)
422
423 cdef void _percolate(self, int start, int end):
424 cdef int i, temp
425 for i from end >= i > start:
426 if self.entries[i] < self.entries[i-1]:
427 temp = self.entries[i]
428 self.entries[i] = self.entries[i-1]
429 self.entries[i-1] = temp
430
431 def sort_by_function(self, start, degrees, k, n):
432 cdef int i
433 cdef int *degs = <int *> sage_malloc( 3 * n * sizeof(int) )
434 if not degs:
435 raise MemoryError("Couldn't allocate...")
436 for i from 0 <= i < len(degrees):
437 degs[i] = degrees[i]
438 return self._sort_by_function(start, degs, k, n)
439 sage_free(degs)
440
441 cdef int _sort_by_function(self, int start, int *degrees, int k, int n):
442 cdef int i, j, m = 2*n, max, max_location
443 cdef int *counts = degrees + n, *output = degrees + 2*n
444# print '|'.join(['%02d'%self.entries[iii] for iii in range(n)])
445# print '|'.join(['%02d'%self.levels[iii] for iii in range(n)])
446# print '|'.join(['%02d'%degrees[iii] for iii in range(n)])
447# print '|'.join(['%02d'%counts[iii] for iii in range(n)])
448# print '|'.join(['%02d'%output[iii] for iii in range(n)])
449
450 for i from 0 <= i < n:
451 counts[i] = 0
452 i = 0
453 while self.levels[i+start] > k:
454 counts[degrees[i]] += 1
455 i += 1
456 counts[degrees[i]] += 1
457
458 # i+start is the right endpoint of the cell now
459 max = counts[0]
460 max_location = 0
461 for j from 0 < j < n:
462 if counts[j] > max:
463 max = counts[j]
464 max_location = j
465 counts[j] += counts[j - 1]
466
467 for j from i >= j >= 0:
468 counts[degrees[j]] -= 1
469 output[counts[degrees[j]]] = self.entries[start+j]
470
471 max_location = counts[max_location]+start
472
473 for j from 0 <= j <= i:
474 self.entries[start+j] = output[j]
475
476 j = 1
477 while j < n and counts[j] <= i:
478 if counts[j] > 0:
479 self.levels[start + counts[j] - 1] = k
480 self._percolate(start + counts[j-1], start + counts[j] - 1)
481 j += 1
482
483 return max_location
484
485 def clear(self, k):
486 self._clear(k)
487
488 cdef void _clear(self, int k):
489 cdef int i = 0, j = 0
490 while self.levels[i] != -1:
491 if self.levels[i] >= k:
492 self.levels[i] += 1
493 if self.levels[i] < k:
494 self._percolate(j, i)
495 j = i + 1
496 i+=1
497
498 def refine_by_square_matrix(self, G_matrix, k, alpha, n, dig):
499 cdef int *_alpha, i, j
500 cdef int **G
501 _alpha = <int *> sage_malloc( 4 * n * sizeof(int) )
502 if not _alpha:
503 raise MemoryError("Memory!")
504 G = <int **> sage_malloc( n * sizeof(int*) )
505 if not G:
506 sage_free(_alpha)
507 raise MemoryError("Memory!")
508 for i from 0 <= i < n:
509 G[i] = <int *> sage_malloc( n * sizeof(int) )
510 if not G[i]:
511 for j from 0 <= j < i:
512 sage_free(G[j])
513 sage_free(G)
514 sage_free(_alpha)
515 raise MemoryError("Memory!")
516 for i from 0 <= i < n:
517 for j from 0 <= j < n:
518 G[i][j] = G_matrix[i][j]
519 for i from 0 <= i < len(alpha):
520 _alpha[i] = alpha[i]
521 _alpha[len(alpha)] = -1
522 self._refine_by_square_matrix(k, _alpha, n, G, dig)
523 sage_free(_alpha)
524 for i from 0 <= i < n:
525 sage_free(G[i])
526 sage_free(G)
527
528 cdef int _refine_by_square_matrix(self, int k, int *alpha, int n, int **G, int dig):
529 cdef int m = 0, j # - m iterates through alpha, the indicator cells
530 # - j iterates through the cells of the partition
531 cdef int i, t, s, r # local variables:
532 # - s plays a double role: outer role indicates whether
533 # splitting the cell is necessary, inner role is as an index
534 # for augmenting _alpha
535 # - i, r iterators
536 # - t: holds the first largest subcell from sort function
537 cdef int invariant = 1
538 # as described in [1], an indicator function Lambda(G, Pi, nu) is
539 # needed to differentiate nonisomorphic branches on the search
540 # tree. The condition is simply that this invariant not depend
541 # on a simultaneous relabeling of the graph G, the root partition
542 # Pi, and the partition nest nu. Since the function will execute
543 # exactly the same way regardless of the labelling, anything that
544 # does not depend on self.entries goes... at least, anything cheap
545 cdef int *degrees = alpha + n # alpha assumed to be length 4*n for
546 # extra scratch space
547 while not self._is_discrete(k) and alpha[m] != -1:
548 invariant += 1
549 j = 0
550 while j < n: # j still points at a valid cell
551 invariant += 50
552# print ' '
553# print '|'.join(['%02d'%self.entries[iii] for iii in range(n)])
554# print '|'.join(['%02d'%self.levels[iii] for iii in range(n)])
555# print '|'.join(['%02d'%alpha[iii] for iii in range(n)])
556# print '|'.join(['%02d'%degrees[iii] for iii in range(n)])
557# print 'j =', j
558# print 'm =', m
559 i = j; s = 0
560 while True:
561 degrees[i-j] = self._degree_square_matrix(G, i, alpha[m], k)
562 if degrees[i-j] != degrees[0]: s = 1
563 i += 1
564 if self.levels[i-1] <= k: break
565# print '|'.join(['%02d'%degrees[iii] for iii in range(n)])
566 # now: j points to this cell,
567 # i points to the next cell (before refinement)
568 if s:
569 invariant += 10
570 t = self._sort_by_function(j, degrees, k, n)
571 # t now points to the first largest subcell
572 invariant += t + degrees[i - j - 1]
573 s = m
574 while alpha[s] != -1:
575 if alpha[s] == j: alpha[s] = t
576 s += 1
577 r = j
578 while True:
579 if r == 0 or self.levels[r-1] == k:
580 if r != t:
581 alpha[s] = r
582 s += 1
583 r += 1
584 if r >= i: break
585 alpha[s] = -1
586 while self.levels[j] > k:
587 j += 1
588 j += 1
589 invariant += (i - j)
590 else: j = i
591 if not dig: m += 1; continue
592 # if we are looking at a digraph, also compute
593 # the reverse degrees and sort by them
594 j = 0
595 while j < n: # j still points at a valid cell
596 invariant += 20
597# print ' '
598# print '|'.join(['%02d'%self.entries[iii] for iii in range(n)])
599# print '|'.join(['%02d'%self.levels[iii] for iii in range(n)])
600# print '|'.join(['%02d'%alpha[iii] for iii in range(n)])
601# print '|'.join(['%02d'%degrees[iii] for iii in range(n)])
602# print 'j =', j
603# print 'm =', m
604 i = j; s = 0
605 while True:
606 degrees[i-j] = self._degree_inv_square_matrix(G, i, alpha[m], k)
607 if degrees[i-j] != degrees[0]: s = 1
608 i += 1
609 if self.levels[i-1] <= k: break
610 # now: j points to this cell,
611 # i points to the next cell (before refinement)
612 if s:
613 invariant += 7
614 t = self._sort_by_function(j, degrees, k, n)
615 # t now points to the first largest subcell
616 invariant += t + degrees[i - j - 1]
617 s = m
618 while alpha[s] != -1:
619 if alpha[s] == j: alpha[s] = t
620 s += 1
621 r = j
622 while True:
623 if r == 0 or self.levels[r-1] == k:
624 if r != t:
625 alpha[s] = r
626 s += 1
627 r += 1
628 if r >= i: break
629 alpha[s] = -1
630 while self.levels[j] > k:
631 j += 1
632 j += 1
633 invariant += (i - j)
634 else: j = i
635 m += 1
636 return invariant
637
638 def degree_square_matrix(self, G, v, W, k):
639 cdef int i, j, n = len(G)
640 cdef int **GG = <int **> sage_malloc( n * sizeof(int*) )
641 if not GG:
642 raise MemoryError("Memory!")
643 for i from 0 <= i < n:
644 GG[i] = <int *> sage_malloc( n * sizeof(int) )
645 if not GG[i]:
646 for j from 0 <= j < i:
647 sage_free(GG[j])
648 sage_free(GG)
649 raise MemoryError("Memory!")
650 for i from 0 <= i < n:
651 for j from 0 <= j < n:
652 GG[i][j] = G[i][j]
653 j = self._degree_square_matrix(GG, v, W, k)
654 for i from 0 <= i < n:
655 sage_free(GG[i])
656 sage_free(GG)
657 return j
658
659 cdef int _degree_square_matrix(self, int** G, int v, int W, int k):
660 """
661 G is a square matrix, and W points to the beginning of a cell in the
662 k-th part of the stack.
663 """
664 cdef int i = 0
665 v = self.entries[v]
666 while True:
667 if G[self.entries[W]][v]:
668 i += 1
669 if self.levels[W] > k: W += 1
670 else: break
671 return i
672
673 cdef int _degree_inv_square_matrix(self, int** G, int v, int W, int k):
674 """
675 G is a square matrix, and W points to the beginning of a cell in the
676 k-th part of the stack.
677 """
678 cdef int i = 0
679 v = self.entries[v]
680 while True:
681 if G[v][self.entries[W]]:
682 i += 1
683 if self.levels[W] > k: W += 1
684 else: break
685 return i
686
687 cdef int _first_smallest_nontrivial(self, int *W, int k, int n):
688 cdef int i = 0, j = 0, location = 0, min = n
689 while True:
690 W[i] = 0
691 if self.levels[i] <= k:
692 if i != j and n > i - j + 1:
693 n = i - j + 1
694 location = j
695 j = i + 1
696 if self.levels[i] == -1: break
697 i += 1
698 # location now points to the beginning of the first, smallest,
699 # nontrivial cell
700 while True:
701 if min > self.entries[location]:
702 min = self.entries[location]
703 W[self.entries[location]] = 1
704 if self.levels[location] <= k: break
705 location += 1
706 return min
707
708 cdef void _get_permutation_from(self, PartitionStack zeta, int *gamma):
709 cdef int i = 0
710
711 while True:
712 gamma[zeta.entries[i]] = self.entries[i]
713 i += 1
714 if self.levels[i-1] == -1: break
715
716# (TODO)
717# Important note: the enumeration should be kept abstract, and only comparison
718# functions should be written. This takes up too much memory and time. Simply
719# iterate starting with the most significant digit in the matrix, and return
720# as soon a contradiction is encountered.
721
722 cdef _enumerate_graph_from_discrete(self, int **G, int n):
723 cdef int i, j
724 enumeration = Integer(0)
725 for i from 0 <= i < n:
726 for j from 0 <= j < n:
727 if G[i][j]:
728 enumeration += Integer(2)**((n-(self.entries[i]+1))*n + n-(self.entries[j]+1))
729 return enumeration
730
731cdef _enumerate_graph_with_permutation(int **G, int n, int *gamma):
732 cdef int i, j
733 enumeration = Integer(0)
734 for i from 0 <= i < n:
735 for j from 0 <= j < n:
736 if G[i][j]:
737 enumeration += Integer(2)**((n-(gamma[i]+1))*n + n-(gamma[j]+1))
738 return enumeration
739
740cdef _enumerate_graph(int **G, int n):
741 cdef int i, j # enumeration = 0
742 enumeration = Integer(0)
743 for i from 0 <= i < n:
744 for j from 0 <= j < n:
745 if G[i][j]:
746 enumeration += Integer(2)**((n-(i+1))*n + n-(j+1))
747 return enumeration
748
749def _term_pnest_graph(G, PartitionStack nu):
750 """
751 BDM's G(nu): returns the graph G, relabeled in the order found in
752 nu[m], where m is the first index corresponding to a discrete partition.
753 Assumes nu is a terminal partition nest in T(G, Pi).
754 """
755 cdef int i, n
756 n = G.order()
757 d = {}
758 for i from 0 <= i < n:
759 d[nu.entries[i]] = i
760 H = G.copy()
761 H.relabel(d)
762 return H
763
764def search_tree(G, Pi, lab=True, dig=False, dict=False, proof=False, verbosity=0):
765 """
766 Assumes that the vertex set of G is {0,1,...,n-1} for some n.
767
768 Note that this conflicts with the SymmetricGroup we are using to represent
769 automorphisms. The solution is to let the group act on the set
770 {1,2,...,n}, under the assumption n = 0.
771
772 INPUT:
773 lab-- if True, return the canonical label in addition to the auto-
774 morphism group.
775 dig-- if True, does not use Lemma 2.25 in [1], and the algorithm is
776 valid for digraphs and graphs with loops.
777 dict-- if True, explain which vertices are which elements of the set
778 {1,2,...,n} in the representation of the automorphism group.
779 proof-- if True, return the automorphism between G and its canonical
780 label. Forces lab=True.
781 verbosity-- 0 - print nothing
782 1 - display state trace
783 2 - with timings
784 3 - display partition nests
785 4 - display orbit partition
786
787 STATE DIAGRAM:
788 sage: SD = DiGraph( { 1:[18,2], 2:[5,3], 3:[4,6], 4:[7,2], 5:[4], 6:[13,12], 7:[18,8,10], 8:[6,9,10], 9:[6], 10:[11,13], 11:[12], 12:[13], 13:[17,14], 14:[16,15], 15:[2], 16:[13], 17:[15,13], 18:[13] } )
789 sage: SD.set_arc_label(1, 18, 'discrete')
790 sage: SD.set_arc_label(4, 7, 'discrete')
791 sage: SD.set_arc_label(2, 5, 'h = 0')
792 sage: SD.set_arc_label(7, 18, 'h = 0')
793 sage: SD.set_arc_label(7, 10, 'aut')
794 sage: SD.set_arc_label(8, 10, 'aut')
795 sage: SD.set_arc_label(8, 9, 'label')
796 sage: SD.set_arc_label(8, 6, 'no label')
797 sage: SD.set_arc_label(13, 17, 'k > h')
798 sage: SD.set_arc_label(13, 14, 'k = h')
799 sage: SD.set_arc_label(17, 15, 'v_k finite')
800 sage: SD.set_arc_label(14, 15, 'v_k m.c.r.')
801 sage: posn = {1:[ 3,-3], 2:[0,2], 3:[0, 13], 4:[3,9], 5:[3,3], 6:[16, 13], 7:[6,1], 8:[6,6], 9:[6,11], 10:[9,1], 11:[10,6], 12:[13,6], 13:[16,2], 14:[10,-6], 15:[0,-10], 16:[14,-6], 17:[16,-10], 18:[6,-4]}
802 sage: SD.plot(pos=posn, vertex_size=400, vertex_colors={'#FFFFFF':range(1,19)}, edge_labels=True).save('search_tree.png')
803
804 EXAMPLES:
805 sage: import sage.graphs.graph_isom
806 sage: from sage.graphs.graph_isom import search_tree
807 sage: from sage.graphs.graph import enum
808 sage: from sage.groups.perm_gps.permgroup import PermutationGroup # long time
809 sage: from sage.graphs.graph_isom import perm_group_elt # long time
810
811 sage: G = graphs.DodecahedralGraph()
812 sage: Pi=[range(20)]
813 sage: a,b = search_tree(G, Pi)
814 sage: print a, enum(b)
815 [[0, 19, 3, 2, 6, 5, 4, 17, 18, 11, 10, 9, 13, 12, 16, 15, 14, 7, 8, 1], [0, 1, 8, 9, 13, 14, 7, 6, 2, 3, 19, 18, 17, 4, 5, 15, 16, 12, 11, 10], [1, 8, 9, 10, 11, 12, 13, 14, 7, 6, 2, 3, 4, 5, 15, 16, 17, 18, 19, 0], [2, 1, 0, 19, 18, 11, 10, 9, 8, 7, 6, 5, 15, 14, 13, 12, 16, 17, 4, 3]] 17318942212009113839976787462421724338461987195898671092180383421848885858584973127639899792828728124797968735273000
816 sage: c = search_tree(G, Pi, lab=False)
817 sage: print c
818 [[0, 19, 3, 2, 6, 5, 4, 17, 18, 11, 10, 9, 13, 12, 16, 15, 14, 7, 8, 1], [0, 1, 8, 9, 13, 14, 7, 6, 2, 3, 19, 18, 17, 4, 5, 15, 16, 12, 11, 10], [1, 8, 9, 10, 11, 12, 13, 14, 7, 6, 2, 3, 4, 5, 15, 16, 17, 18, 19, 0], [2, 1, 0, 19, 18, 11, 10, 9, 8, 7, 6, 5, 15, 14, 13, 12, 16, 17, 4, 3]]
819 sage: DodecAut = PermutationGroup([perm_group_elt(aa) for aa in a]) # long time
820 sage: DodecAut.character_table() # long time
821 [ 1 1 1 1 1 1 1 1 1 1]
822 [ 1 -1 1 1 -1 1 -1 1 -1 -1]
823 [ 3 -1 0 -1 zeta5^3 + zeta5^2 + 1 -zeta5^3 - zeta5^2 0 zeta5^3 + zeta5^2 + 1 -zeta5^3 - zeta5^2 3]
824 [ 3 -1 0 -1 -zeta5^3 - zeta5^2 zeta5^3 + zeta5^2 + 1 0 -zeta5^3 - zeta5^2 zeta5^3 + zeta5^2 + 1 3]
825 [ 3 1 0 -1 -zeta5^3 - zeta5^2 - 1 -zeta5^3 - zeta5^2 0 zeta5^3 + zeta5^2 + 1 zeta5^3 + zeta5^2 -3]
826 [ 3 1 0 -1 zeta5^3 + zeta5^2 zeta5^3 + zeta5^2 + 1 0 -zeta5^3 - zeta5^2 -zeta5^3 - zeta5^2 - 1 -3]
827 [ 4 0 1 0 -1 -1 1 -1 -1 4]
828 [ 4 0 1 0 1 -1 -1 -1 1 -4]
829 [ 5 1 -1 1 0 0 -1 0 0 5]
830 [ 5 -1 -1 1 0 0 1 0 0 -5]
831 sage: DodecAut2 = PermutationGroup([perm_group_elt(cc) for cc in c]) # long time
832 sage: DodecAut2.character_table() # long time
833 [ 1 1 1 1 1 1 1 1 1 1]
834 [ 1 -1 1 1 -1 1 -1 1 -1 -1]
835 [ 3 -1 0 -1 zeta5^3 + zeta5^2 + 1 -zeta5^3 - zeta5^2 0 zeta5^3 + zeta5^2 + 1 -zeta5^3 - zeta5^2 3]
836 [ 3 -1 0 -1 -zeta5^3 - zeta5^2 zeta5^3 + zeta5^2 + 1 0 -zeta5^3 - zeta5^2 zeta5^3 + zeta5^2 + 1 3]
837 [ 3 1 0 -1 -zeta5^3 - zeta5^2 - 1 -zeta5^3 - zeta5^2 0 zeta5^3 + zeta5^2 + 1 zeta5^3 + zeta5^2 -3]
838 [ 3 1 0 -1 zeta5^3 + zeta5^2 zeta5^3 + zeta5^2 + 1 0 -zeta5^3 - zeta5^2 -zeta5^3 - zeta5^2 - 1 -3]
839 [ 4 0 1 0 -1 -1 1 -1 -1 4]
840 [ 4 0 1 0 1 -1 -1 -1 1 -4]
841 [ 5 1 -1 1 0 0 -1 0 0 5]
842 [ 5 -1 -1 1 0 0 1 0 0 -5]
843
844 sage: G = graphs.PetersenGraph()
845 sage: Pi=[range(10)]
846 sage: a,b = search_tree(G, Pi)
847 sage: print a, enum(b)
848 [[0, 1, 2, 7, 5, 4, 6, 3, 9, 8], [0, 1, 6, 8, 5, 4, 2, 9, 3, 7], [0, 4, 3, 8, 5, 1, 9, 2, 6, 7], [1, 0, 4, 9, 6, 2, 5, 3, 7, 8], [2, 1, 0, 5, 7, 3, 6, 4, 8, 9]] 8715233764864019919698297664
849 sage: c = search_tree(G, Pi, lab=False)
850 sage: PAut = PermutationGroup([perm_group_elt(aa) for aa in a]) # long time
851 sage: PAut.character_table() # long time
852 [ 1 1 1 1 1 1 1]
853 [ 1 -1 1 -1 1 -1 1]
854 [ 4 -2 0 1 1 0 -1]
855 [ 4 2 0 -1 1 0 -1]
856 [ 5 1 1 1 -1 -1 0]
857 [ 5 -1 1 -1 -1 1 0]
858 [ 6 0 -2 0 0 0 1]
859 sage: PAut = PermutationGroup([perm_group_elt(cc) for cc in c]) # long time
860 sage: PAut.character_table() # long time
861 [ 1 1 1 1 1 1 1]
862 [ 1 -1 1 -1 1 -1 1]
863 [ 4 -2 0 1 1 0 -1]
864 [ 4 2 0 -1 1 0 -1]
865 [ 5 1 1 1 -1 -1 0]
866 [ 5 -1 1 -1 -1 1 0]
867 [ 6 0 -2 0 0 0 1]
868
869 sage: G = graphs.CubeGraph(3)
870 sage: Pi = []
871 sage: for i in range(8):
872 ... b = Integer(i).binary()
873 ... Pi.append(b.zfill(3))
874 ...
875 sage: Pi = [Pi]
876 sage: a,b = search_tree(G, Pi)
877 sage: print a, enum(b)
878 [[0, 2, 1, 3, 4, 6, 5, 7], [0, 1, 4, 5, 2, 3, 6, 7], [1, 0, 3, 2, 5, 4, 7, 6]] 520239721777506480
879 sage: c = search_tree(G, Pi, lab=False)
880
881 sage: PermutationGroup([perm_group_elt(aa) for aa in a]).order() # long time
882 48
883 sage: PermutationGroup([perm_group_elt(cc) for cc in c]).order() # long time
884 48
885 sage: DodecAut.order() # long time
886 120
887 sage: PAut.order() # long time
888 120
889
890 sage: D = graphs.DodecahedralGraph()
891 sage: a,b,c = search_tree(D, [range(20)], proof=True)
892 sage: from sage.plot.plot import GraphicsArray # long time
893 sage: import networkx # long time
894 sage: position_D = networkx.spring_layout(D._nxg) # long time
895 sage: position_b = {} # long time
896 sage: for vert in position_D: # long time
897 ... position_b[c[vert]] = position_D[vert]
898 sage: GraphicsArray([D.plot(pos=position_D), b.plot(pos=position_b)]).save('sage.png') # long time
899 sage: c
900 {0: 0, 1: 19, 2: 16, 3: 15, 4: 9, 5: 1, 6: 10, 7: 8, 8: 14, 9: 12, 10: 17, 11: 11, 12: 5, 13: 6, 14: 2, 15: 4, 16: 3, 17: 7, 18: 13, 19: 18}
901
902 BENCHMARKS:
903 The following examples are given to check modifications to the algorithm
904 for optimization.
905
906 sage: G = Graph({0:[]})
907 sage: Pi = [[0]]
908 sage: a,b = search_tree(G, Pi)
909 sage: print a, enum(b)
910 [] 0
911 sage: a,b = search_tree(G, Pi, dig=True)
912 sage: print a, enum(b)
913 [] 0
914 sage: search_tree(G, Pi, lab=False)
915 []
916
917 sage: from sage.graphs.graph_isom import all_labeled_graphs, all_ordered_partitions
918
919 sage: graph2 = all_labeled_graphs(2)
920 sage: part2 = all_ordered_partitions(range(2))
921 sage: for G in graph2:
922 ... for Pi in part2:
923 ... a,b = search_tree(G, Pi)
924 ... c,d = search_tree(G, Pi, dig=True)
925 ... e = search_tree(G, Pi, lab=False)
926 ... a = str(a); b = str(enum(b)); c = str(c); d = str(enum(d)); e = str(e)
927 ... print a.ljust(15), b.ljust(5), c.ljust(15), d.ljust(5), e.ljust(15)
928 [] 0 [] 0 []
929 [] 0 [] 0 []
930 [[1, 0]] 0 [[1, 0]] 0 [[1, 0]]
931 [[1, 0]] 0 [[1, 0]] 0 [[1, 0]]
932 [] 6 [] 6 []
933 [] 6 [] 6 []
934 [[1, 0]] 6 [[1, 0]] 6 [[1, 0]]
935 [[1, 0]] 6 [[1, 0]] 6 [[1, 0]]
936
937 sage: graph3 = all_labeled_graphs(3)
938 sage: part3 = all_ordered_partitions(range(3))
939 sage: for G in graph3:
940 ... for Pi in part3:
941 ... a,b = search_tree(G, Pi)
942 ... c,d = search_tree(G, Pi, dig=True)
943 ... e = search_tree(G, Pi, lab=False)
944 ... a = str(a); b = str(enum(b)); c = str(c); d = str(enum(d)); e = str(e)
945 ... print a.ljust(15), b.ljust(5), c.ljust(15), d.ljust(5), e.ljust(15)
946 [] 0 [] 0 []
947 [] 0 [] 0 []
948 [[0, 2, 1]] 0 [[0, 2, 1]] 0 [[0, 2, 1]]
949 [[0, 2, 1]] 0 [[0, 2, 1]] 0 [[0, 2, 1]]
950 [] 0 [] 0 []
951 [] 0 [] 0 []
952 [[2, 1, 0]] 0 [[2, 1, 0]] 0 [[2, 1, 0]]
953 [[2, 1, 0]] 0 [[2, 1, 0]] 0 [[2, 1, 0]]
954 [] 0 [] 0 []
955 [] 0 [] 0 []
956 [[1, 0, 2]] 0 [[1, 0, 2]] 0 [[1, 0, 2]]
957 [[1, 0, 2]] 0 [[1, 0, 2]] 0 [[1, 0, 2]]
958 [[1, 0, 2]] 0 [[1, 0, 2]] 0 [[1, 0, 2]]
959 [[2, 1, 0]] 0 [[2, 1, 0]] 0 [[2, 1, 0]]
960 [[1, 0, 2]] 0 [[1, 0, 2]] 0 [[1, 0, 2]]
961 [[0, 2, 1]] 0 [[0, 2, 1]] 0 [[0, 2, 1]]
962 [[2, 1, 0]] 0 [[2, 1, 0]] 0 [[2, 1, 0]]
963 [[0, 2, 1]] 0 [[0, 2, 1]] 0 [[0, 2, 1]]
964 [[0, 2, 1], [1, 0, 2]] 0 [[0, 2, 1], [1, 0, 2]] 0 [[0, 2, 1], [1, 0, 2]]
965 [[0, 2, 1], [1, 0, 2]] 0 [[0, 2, 1], [1, 0, 2]] 0 [[0, 2, 1], [1, 0, 2]]
966 [[0, 2, 1], [1, 0, 2]] 0 [[0, 2, 1], [1, 0, 2]] 0 [[0, 2, 1], [1, 0, 2]]
967 [[0, 2, 1], [1, 0, 2]] 0 [[0, 2, 1], [1, 0, 2]] 0 [[0, 2, 1], [1, 0, 2]]
968 [[0, 2, 1], [1, 0, 2]] 0 [[0, 2, 1], [1, 0, 2]] 0 [[0, 2, 1], [1, 0, 2]]
969 [[0, 2, 1], [1, 0, 2]] 0 [[0, 2, 1], [1, 0, 2]] 0 [[0, 2, 1], [1, 0, 2]]
970 [] 10 [] 10 []
971 [] 10 [] 10 []
972 [[0, 2, 1]] 10 [[0, 2, 1]] 10 [[0, 2, 1]]
973 [[0, 2, 1]] 10 [[0, 2, 1]] 10 [[0, 2, 1]]
974 [] 68 [] 68 []
975 [] 160 [] 160 []
976 [] 68 [] 68 []
977 [] 68 [] 68 []
978 [] 68 [] 68 []
979 [] 160 [] 160 []
980 [] 68 [] 68 []
981 [] 68 [] 68 []
982 [] 10 [] 10 []
983 [] 10 [] 10 []
984 [] 10 [] 10 []
985 [[0, 2, 1]] 160 [[0, 2, 1]] 160 [[0, 2, 1]]
986 [] 10 [] 10 []
987 [[0, 2, 1]] 160 [[0, 2, 1]] 160 [[0, 2, 1]]
988 [[0, 2, 1]] 10 [[0, 2, 1]] 10 [[0, 2, 1]]
989 [[0, 2, 1]] 10 [[0, 2, 1]] 10 [[0, 2, 1]]
990 [[0, 2, 1]] 10 [[0, 2, 1]] 10 [[0, 2, 1]]
991 [[0, 2, 1]] 10 [[0, 2, 1]] 10 [[0, 2, 1]]
992 [[0, 2, 1]] 10 [[0, 2, 1]] 10 [[0, 2, 1]]
993 [[0, 2, 1]] 10 [[0, 2, 1]] 10 [[0, 2, 1]]
994 [] 68 [] 68 []
995 [] 160 [] 160 []
996 [] 68 [] 68 []
997 [] 68 [] 68 []
998 [] 10 [] 10 []
999 [] 10 [] 10 []
1000 [[2, 1, 0]] 10 [[2, 1, 0]] 10 [[2, 1, 0]]
1001 [[2, 1, 0]] 10 [[2, 1, 0]] 10 [[2, 1, 0]]
1002 [] 160 [] 160 []
1003 [] 68 [] 68 []
1004 [] 68 [] 68 []
1005 [] 68 [] 68 []
1006 [] 10 [] 10 []
1007 [[2, 1, 0]] 160 [[2, 1, 0]] 160 [[2, 1, 0]]
1008 [] 10 [] 10 []
1009 [] 10 [] 10 []
1010 [[2, 1, 0]] 160 [[2, 1, 0]] 160 [[2, 1, 0]]
1011 [] 10 [] 10 []
1012 [[2, 1, 0]] 10 [[2, 1, 0]] 10 [[2, 1, 0]]
1013 [[2, 1, 0]] 10 [[2, 1, 0]] 10 [[2, 1, 0]]
1014 [[2, 1, 0]] 10 [[2, 1, 0]] 10 [[2, 1, 0]]
1015 [[2, 1, 0]] 10 [[2, 1, 0]] 10 [[2, 1, 0]]
1016 [[2, 1, 0]] 10 [[2, 1, 0]] 10 [[2, 1, 0]]
1017 [[2, 1, 0]] 10 [[2, 1, 0]] 10 [[2, 1, 0]]
1018 [] 78 [] 78 []
1019 [] 170 [] 170 []
1020 [] 78 [] 78 []
1021 [] 78 [] 78 []
1022 [] 78 [] 78 []
1023 [] 170 [] 170 []
1024 [] 78 [] 78 []
1025 [] 78 [] 78 []
1026 [] 228 [] 228 []
1027 [] 228 [] 228 []
1028 [[1, 0, 2]] 228 [[1, 0, 2]] 228 [[1, 0, 2]]
1029 [[1, 0, 2]] 228 [[1, 0, 2]] 228 [[1, 0, 2]]
1030 [[1, 0, 2]] 78 [[1, 0, 2]] 78 [[1, 0, 2]]
1031 [] 170 [] 170 []
1032 [[1, 0, 2]] 78 [[1, 0, 2]] 78 [[1, 0, 2]]
1033 [] 170 [] 170 []
1034 [] 170 [] 170 []
1035 [] 170 [] 170 []
1036 [[1, 0, 2]] 78 [[1, 0, 2]] 78 [[1, 0, 2]]
1037 [[1, 0, 2]] 78 [[1, 0, 2]] 78 [[1, 0, 2]]
1038 [[1, 0, 2]] 78 [[1, 0, 2]] 78 [[1, 0, 2]]
1039 [[1, 0, 2]] 78 [[1, 0, 2]] 78 [[1, 0, 2]]
1040 [[1, 0, 2]] 78 [[1, 0, 2]] 78 [[1, 0, 2]]
1041 [[1, 0, 2]] 78 [[1, 0, 2]] 78 [[1, 0, 2]]
1042 [] 160 [] 160 []
1043 [] 68 [] 68 []
1044 [] 68 [] 68 []
1045 [] 68 [] 68 []
1046 [] 160 [] 160 []
1047 [] 68 [] 68 []
1048 [] 68 [] 68 []
1049 [] 68 [] 68 []
1050 [] 10 [] 10 []
1051 [] 10 [] 10 []
1052 [[1, 0, 2]] 10 [[1, 0, 2]] 10 [[1, 0, 2]]
1053 [[1, 0, 2]] 10 [[1, 0, 2]] 10 [[1, 0, 2]]
1054 [[1, 0, 2]] 160 [[1, 0, 2]] 160 [[1, 0, 2]]
1055 [] 10 [] 10 []
1056 [[1, 0, 2]] 160 [[1, 0, 2]] 160 [[1, 0, 2]]
1057 [] 10 [] 10 []
1058 [] 10 [] 10 []
1059 [] 10 [] 10 []
1060 [[1, 0, 2]] 10 [[1, 0, 2]] 10 [[1, 0, 2]]
1061 [[1, 0, 2]] 10 [[1, 0, 2]] 10 [[1, 0, 2]]
1062 [[1, 0, 2]] 10 [[1, 0, 2]] 10 [[1, 0, 2]]
1063 [[1, 0, 2]] 10 [[1, 0, 2]] 10 [[1, 0, 2]]
1064 [[1, 0, 2]] 10 [[1, 0, 2]] 10 [[1, 0, 2]]
1065 [[1, 0, 2]] 10 [[1, 0, 2]] 10 [[1, 0, 2]]
1066 [] 170 [] 170 []
1067 [] 78 [] 78 []
1068 [] 78 [] 78 []
1069 [] 78 [] 78 []
1070 [] 228 [] 228 []
1071 [] 228 [] 228 []
1072 [[2, 1, 0]] 228 [[2, 1, 0]] 228 [[2, 1, 0]]
1073 [[2, 1, 0]] 228 [[2, 1, 0]] 228 [[2, 1, 0]]
1074 [] 78 [] 78 []
1075 [] 170 [] 170 []
1076 [] 78 [] 78 []
1077 [] 78 [] 78 []
1078 [] 170 [] 170 []
1079 [[2, 1, 0]] 78 [[2, 1, 0]] 78 [[2, 1, 0]]
1080 [] 170 [] 170 []
1081 [] 170 [] 170 []
1082 [[2, 1, 0]] 78 [[2, 1, 0]] 78 [[2, 1, 0]]
1083 [] 170 [] 170 []
1084 [[2, 1, 0]] 78 [[2, 1, 0]] 78 [[2, 1, 0]]
1085 [[2, 1, 0]] 78 [[2, 1, 0]] 78 [[2, 1, 0]]
1086 [[2, 1, 0]] 78 [[2, 1, 0]] 78 [[2, 1, 0]]
1087 [[2, 1, 0]] 78 [[2, 1, 0]] 78 [[2, 1, 0]]
1088 [[2, 1, 0]] 78 [[2, 1, 0]] 78 [[2, 1, 0]]
1089 [[2, 1, 0]] 78 [[2, 1, 0]] 78 [[2, 1, 0]]
1090 [] 228 [] 228 []
1091 [] 228 [] 228 []
1092 [[0, 2, 1]] 228 [[0, 2, 1]] 228 [[0, 2, 1]]
1093 [[0, 2, 1]] 228 [[0, 2, 1]] 228 [[0, 2, 1]]
1094 [] 170 [] 170 []
1095 [] 78 [] 78 []
1096 [] 78 [] 78 []
1097 [] 78 [] 78 []
1098 [] 170 [] 170 []
1099 [] 78 [] 78 []
1100 [] 78 [] 78 []
1101 [] 78 [] 78 []
1102 [] 170 [] 170 []
1103 [] 170 [] 170 []
1104 [] 170 [] 170 []
1105 [[0, 2, 1]] 78 [[0, 2, 1]] 78 [[0, 2, 1]]
1106 [] 170 [] 170 []
1107 [[0, 2, 1]] 78 [[0, 2, 1]] 78 [[0, 2, 1]]
1108 [[0, 2, 1]] 78 [[0, 2, 1]] 78 [[0, 2, 1]]
1109 [[0, 2, 1]] 78 [[0, 2, 1]] 78 [[0, 2, 1]]
1110 [[0, 2, 1]] 78 [[0, 2, 1]] 78 [[0, 2, 1]]
1111 [[0, 2, 1]] 78 [[0, 2, 1]] 78 [[0, 2, 1]]
1112 [[0, 2, 1]] 78 [[0, 2, 1]] 78 [[0, 2, 1]]
1113 [[0, 2, 1]] 78 [[0, 2, 1]] 78 [[0, 2, 1]]
1114 [] 238 [] 238 []
1115 [] 238 [] 238 []
1116 [[0, 2, 1]] 238 [[0, 2, 1]] 238 [[0, 2, 1]]
1117 [[0, 2, 1]] 238 [[0, 2, 1]] 238 [[0, 2, 1]]
1118 [] 238 [] 238 []
1119 [] 238 [] 238 []
1120 [[2, 1, 0]] 238 [[2, 1, 0]] 238 [[2, 1, 0]]
1121 [[2, 1, 0]] 238 [[2, 1, 0]] 238 [[2, 1, 0]]
1122 [] 238 [] 238 []
1123 [] 238 [] 238 []
1124 [[1, 0, 2]] 238 [[1, 0, 2]] 238 [[1, 0, 2]]
1125 [[1, 0, 2]] 238 [[1, 0, 2]] 238 [[1, 0, 2]]
1126 [[1, 0, 2]] 238 [[1, 0, 2]] 238 [[1, 0, 2]]
1127 [[2, 1, 0]] 238 [[2, 1, 0]] 238 [[2, 1, 0]]
1128 [[1, 0, 2]] 238 [[1, 0, 2]] 238 [[1, 0, 2]]
1129 [[0, 2, 1]] 238 [[0, 2, 1]] 238 [[0, 2, 1]]
1130 [[2, 1, 0]] 238 [[2, 1, 0]] 238 [[2, 1, 0]]
1131 [[0, 2, 1]] 238 [[0, 2, 1]] 238 [[0, 2, 1]]
1132 [[0, 2, 1], [1, 0, 2]] 238 [[0, 2, 1], [1, 0, 2]] 238 [[0, 2, 1], [1, 0, 2]]
1133 [[0, 2, 1], [1, 0, 2]] 238 [[0, 2, 1], [1, 0, 2]] 238 [[0, 2, 1], [1, 0, 2]]
1134 [[0, 2, 1], [1, 0, 2]] 238 [[0, 2, 1], [1, 0, 2]] 238 [[0, 2, 1], [1, 0, 2]]
1135 [[0, 2, 1], [1, 0, 2]] 238 [[0, 2, 1], [1, 0, 2]] 238 [[0, 2, 1], [1, 0, 2]]
1136 [[0, 2, 1], [1, 0, 2]] 238 [[0, 2, 1], [1, 0, 2]] 238 [[0, 2, 1], [1, 0, 2]]
1137 [[0, 2, 1], [1, 0, 2]] 238 [[0, 2, 1], [1, 0, 2]] 238 [[0, 2, 1], [1, 0, 2]]
1138
1139 sage: C = graphs.CubeGraph(1)
1140 sage: gens = search_tree(C, [C.vertices()], lab=False)
1141 sage: PermutationGroup([perm_group_elt(aa) for aa in gens]).order() # long time
1142 2
1143 sage: C = graphs.CubeGraph(2)
1144 sage: gens = search_tree(C, [C.vertices()], lab=False)
1145 sage: PermutationGroup([perm_group_elt(aa) for aa in gens]).order() # long time
1146 8
1147 sage: C = graphs.CubeGraph(3)
1148 sage: gens = search_tree(C, [C.vertices()], lab=False)
1149 sage: PermutationGroup([perm_group_elt(aa) for aa in gens]).order() # long time
1150 48
1151 sage: C = graphs.CubeGraph(4)
1152 sage: gens = search_tree(C, [C.vertices()], lab=False)
1153 sage: PermutationGroup([perm_group_elt(aa) for aa in gens]).order() # long time
1154 384
1155 sage: C = graphs.CubeGraph(5)
1156 sage: gens = search_tree(C, [C.vertices()], lab=False)
1157 sage: PermutationGroup([perm_group_elt(aa) for aa in gens]).order() # long time
1158 3840
1159 sage: C = graphs.CubeGraph(6)
1160 sage: gens = search_tree(C, [C.vertices()], lab=False)
1161 sage: PermutationGroup([perm_group_elt(aa) for aa in gens]).order() # long time
1162 46080
1163 """
1164 cdef int i, j, # local variables
1165
1166 cdef OrbitPartition Theta, OP
1167 cdef int index = 0, size = 1 # see Theorem 2.33 in [1]
1168
1169 cdef int L = 100 # memory limit for storing values from fix and mc