[Nauty] Canonical forms of weighted k-cubes

[Brendan McKay]

Hi, I'm not sure exactly what you are doing so I'll give an example.

Say you have a 3-cube with colours (9, 15, 18, 18, 26, 9, 9, 15).

You would set up lab/ptn like this:

lab = 0 5 6 1 7 3 4 5
ptn = 1 1 0 1 0 1 0 0


Then make sure you use options.defaultptn = FALSE.

The canonical form you then compare is the pair
 (9,9,9,15,15,18,18,26),(canonical graph)

Note that for two graphs with the same number of appearances of each
colour, the list of colours must be the same.  A sorted list is the easiest.
Also, the order that colours appear in lab/ptn must match the list of colours.

Brendan.

On 14/4/19 8:07 pm, Jernej Azarija wrote:

Yeah, this was my first impression but perhaps I missed something.

I took the graph6 string of the canonical form of the respective colored
graph + the sorted tuple as a "canonical certificate" for a tuple. Somehow
this was not reducing tuples properly, though.

Am I missing something with the above or should I take a deeper look into
the code?

Best,

Jernej

On Sun, Apr 14, 2019, 11:10 Gordon Royle <gordon.royle at uwa.edu.au><mailto:gordon.royle at uwa.edu.au> wrote:



Are these actually fundamentally different than coloured graphs?

You may need to keep the actual weights as part of the canonical form to
distinguish between two graphs with the same weight partition but different
actual weights.

Sent from my iPad



On 14 Apr 2019, at 5:00 pm, Jernej Azarija <jernej.azarija at gmail.com><mailto:jernej.azarija at gmail.com>


wrote:



Hello,

I am wondering if the following problem can easily be solved by using


nauty.



For a fixed k, I am given a list of 2^k tuples (a_0,..., a_{2^k-1})
representing weights of the k-cube Q_k where a_i is the weight of the
vertex i of Q_k (we treat i as represented in binary form).

We say that two tuples are isomorphic if there is an isomorphism between
the respective weighted Q_k cubes. For example (10,12) and (12,10) are
isomorphic and so are (9, 15, 18, 18, 26, 9, 9, 15) and (26, 9, 9, 15, 9,
15, 18, 18). Both are not isomorphic to, (9, 18, 26, 9, 18, 15, 9, 15)
though.

I would like to compute canonical forms of such tuples, so that


isomorphic


tuples are assigned to the same tuple. While easy to solve if the tuples
are all distinct (take the permutation mapping the vertex with least


weight


to 0 and permute the vertices in descending order) I don't see a direct


way


to compute canonical labelings for the case of non-distinct labels.

As I'd like to minimize the code/bugs required for me to solve this I
wonder:  is there a clever way to model this problem directly with nauty?

Best,

Jernej
_______________________________________________
Nauty mailing list
Nauty at anu.edu.au<mailto:Nauty at anu.edu.au>
http://mailman.anu.edu.au/mailman/listinfo/nauty





_______________________________________________
Nauty mailing list
Nauty at anu.edu.au<mailto:Nauty at anu.edu.au>
http://mailman.anu.edu.au/mailman/listinfo/nauty