I am trying to construct a hash of some not-quite polyomino lattice (more bond animal like (see comment at the end) embedded graphs (examples below), but have been running into some problems.
For standard polyominos, we have lattice-embedded graphs that look something like this (think tetris):
X X
| |
X-X-X or X-X-X or X-X-X-X
And for something like these I would just reference the work from Algorithm to identify a unique free polyomino (or polyomino hash)
However, in my case I have the following:
X Y X
| | |
X-Y-X or X-Y-X-X or X-X-X-Y or X X X or Y-X-X
X
|
or Y-X
|
X
Where - and | indicate "bonded" neighbors
Now I in my case I consider any rotation (such as the first and last) to be the same structure, while the second and fifth would be the same and third and fourth would also be the same structures. Also "flips" are also equal so:
X-X-X-Y = Y-X-X-X and X-Y-X-X = X-X-Y-X
Now the code that I have that produces these "structures" reports them as:
0 Y 0 0 0
1 X 1 0 0
2 X 0 1 0
3 X 0 0 1
Bonds
0 1
0 2
0 3
Which (when projected to 2D) would represent the
X
|
Y-X
|
X
Structure
Currently I parse this structure as a the following string: YXXXb0B1 Where b"num" indicates a "branch" point, while the B"num" indicates the number of branches. Now the B"num" is trivial for low n (like 4 nodes), but for something like n=7 we could have something like:
X X X X
| | | |
X-Y-Y-X-X or Y-X-Y-X
|
X
So for a case of n=4, I expect if I have 1 Y's and 3 X's, I should have 3 unique structures:
X
|
X-Y-X-X and Y-X-X-X and X-Y-X
With my current labeling/hashing I get 6 "unique structures", but I think with string manipulation I can eliminate 2 of cases (swapping the first and last characters, and then swapping the two middle characters), but this likely won't eliminate the duplicate branch point models (b1, or b0, could both be branch points and are just separated by a "rotation").
As a simplification, I am currently just interested in labeled lattices that have the additional restrictions that only Y's can "branch" ( have more than 2 "bonded" neighbors) and that they have the restriction of having at most bonded 3 neighbors (so not all of the typical polyominos are going to be included). Indeed they are a odd cross of polyominos like "structures" and bond-lattice animals, similar to lattice-trees (no loops/cylcles) (see link: http://www.ms.unimelb.edu.au/~andrewr/research/intro_html/node8.html ).
EDIT:
As a follow up I thought I had solved it by using the following rules to describe any one of these structures: (+ = concatenate)
num. of Branches + branch-ID(randomly assigned)+sequence in that branch+next branch id+sequence .... and so on. But this still doesn't quite work.
But I am still not sure if this is sufficient. I know in the case of Y having more than 3 bonded neighbors, it doesn't work, but for my limited case of Y's bonded neighbors<=3 it seems to work.
