Unique representation of a graph (graph automorphism) in python

Question

I'm trying to implement a boardgame in python, but I'm having quite a bit of trouble finding a clever way to solve the following graph problem. (Image to help visualize the game and pieces I'm talking about)

I have hexagonal pieces, and I wish to fixate these pieces in a unique way such that I can later determine whether another game has a similar configuration. I can think of two ways to go about this:

1. I describe each piece by its axial coordinates and somehow try to fixate the board based on 3 pieces (one for origo, one for rotation and one for mirroring). However, this is going to be a nightmare coding up, and will not be guaranteed to completely unique since multiple identical pieces exist in this board.
2. I create a graph automorphism of the game using the distance between all pieces.

Solution 2 sounds very tempting, but I have been playing around with pynauty and igraph for two days now and still haven't managed to make even a simple example that behaves like it is supposed to. Here is my attempt in igraph:

coordinates = [[0,0],[1,0],[2,0],[4,2]]
edge_distance = [1.0, 2.0, 4.472, 1.0, 3.606, 2.828]
nodes = 4
node_attributes = {0: '0', 1: '0', 2: '1', 3: '2'}
edge_attributes = {0: '1', 1: '2', 2: '5', 3: '1', 4: '4', 5: '3'}
edges = [[0, 1], [0, 2], [0, 3], [1, 2], [1, 3], [2, 3]]

g = ig.Graph(n=n, edges=edges,directed=False,vertex_attrs=node_attributes,edge_attrs=edge_attributes)
g.es['weight'] = edge_distances
print(g.get_automorphisms_vf2())

I need an automorphism python package that supports vertex coloring and edge coloring, and while igraph is supposed to have this from what I can read, I haven't managed to make it work. Are there any other alternatives to solving this problem?

Answer 1

Here is one possible strategy for giving each position a canonical encoding that is not influenced by symmetry.

First, here is an encoding mechanism that has some arbitrary choices in it.

1. Arbitrarily choose one of the pieces. Declare the coordinates of that piece to be $(0,0)$.
2. Arbitrarily choose one of the six directions from that piece to call the $(+1,+0)$ direction.
3. Arbitrarily choose one of the two adjacent directions to call the $(+0,+1)$ direction. Going around the hexagon, the next directions will be $(-1,+1)$, $(-1,+0)$, $(+0,-1)$, and $(+1,-1)$.
4. Now find the coordinates of all the pieces. Sort the pieces by their coordinates, in dictionary order (from least to greatest first coordinate, and within that from least to greatest second coordinate).

For example, in the configuration shown in the question, depending on the arbitrary choices we make, here are two possible outcomes:

• We could choose the bee to be at $(0,0)$, then decide that "right" is $(+1,+0)$ and "up and right" is $(+0,+1)$. Then the encoding we get is: Black Ant @ (-1,-1), Black Ant @ (-1,0), Black Ant @ (-1,1), White Bee @ (0,0).
• We could choose the bottom-most ant to be at $(0,0)$, then decide that "up and left" is $(+1,+0)$ and "up and right" is $(+0,+1)$. Then the encoding we get is: White Bee @ (-1,2), Black Ant @ (0,0), Black Ant @ (0,1), Black Ant @ (0,2).

This does not yet solve the problem. However, if two positions are identical up to symmetry, then every encoding of one position corresponds to some encoding of the other position. Therefore one way to make sure they get the same encoding is to finish up with the following step:

5. Do steps 1-4 for all possible arbitrary choices, then sort the resulting encodings and choose the first one. (For example, write the encodings as strings and choose the first string in dictionary order. Or apply a hash function to each encoding and choose the encoding with the lowest hash value.)

How hard is this? Well, at most $22$ pieces can be on the board at any time, so there's at most $22 \cdot 6 \cdot 2 = 254$ ways to make the arbitrary choices. This is not a lot for a computer.

We could even reduce this by saying "always pick a white piece to be $(0,0)$ if it is possible, and always pick the bee if it is possible". The bee has to be one of the first four pieces placed, so either the choice of $(0,0)$ is fixed or there are at most three options for $(0,0)$. Now we only have to compare at most $3 \cdot 6 \cdot 2 = 36$ encodings in step 5.