[Nauty-list] Detecting isomorphic collections in the Boolean lattice

Gordon Royle gordon at csse.uwa.edu.au
Tue Nov 28 15:23:07 EST 2006


You appear to be using lab and ptn in a funny way, although I cannot  
tell from your post exactly what they contained...


First, let's fix a numbering on the vertex set so we know exactly  
which vertex is which

0 = emptyset
1 = 1
2 = 2
3 = 3
4 = 4
5 = 5
6 = 12
7 = 13
8 = 14
9 = 15
10 = 23
11 = 24
12 = 25
13 = 34
14 = 35
15 = 45
16 = 123
17 = 124
18 = 125
19 = 134
20 = 135
21 = 145
22 = 234
23 = 235
24 = 245
25 = 345
26 = 1234
27 = 1235
28 = 1245
29 = 1345
30 = 2345
31 = 12345


Now the array "lab" should contain a permutation of the vertex  
numbers with each cell forming a contiguous part of the array. So if  
you want to put the two vertices 16 and 17 in one cell, and  
everything else in another cell, then lab should contain

{16, 17, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 18,  
19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31}

(ie lab[0] = 16, lab[1] = 17 and so on)

The array "ptn" should tell us the boundaries of the cells, so ptn  
should contain

{1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,  
1, 1, 1, 1, 1, 1, 1, 1, 1, 0}

and then nauty should be told NOT to use the default partition  
(everything in one cell)

options.defaultptn = FALSE;


The canonically labelled graph now contains the canonical labelling  
of that PARTITIONED graph, so if you do the same with the other set,  
then you will get the same canonical labelling.


Notice that this process will assign {123, 124} and {45, 35} the same  
canonical labelling, because they ARE isomorphic subsets of the n-cube.


On output lab and ptn will be altered and can be interpreted sensibly  
if you need ...


Gordon





More information about the Nauty mailing list