-
Notifications
You must be signed in to change notification settings - Fork 4
Site based Description
In this description, we only care about placing vertices on the graph. We assume that if it is possible to place an edge of length 1 between vertices, then it is placed. If we place 4 vertices to form a square, then the bonds between them will form a square as well - no "u" or "c" shapes are allowed. Essentially all we are interested in is the relative positions of vertices, not which ones are connected to which.
This discussion assumes we're working with a square lattice, but should be easily modifiable to other lattices. A single site has four possible nearest-neighbours. Starting with a graph of order n, we pick a site and try adding another site to it in a nearest-neighbour position. If this is doable, that graph is stored and we delete the site we just added, then try to add another site in the next nearest-neighbour position, as shown below.
We proceed through all the sites which have degree (number of nearest neighbours) less than four. With this method, we can generate all graphs embeddable on the square lattice of order n + 1. However, some graphs are actually duplicates of other graphs. We consider graphs which are isomorphic to each other under the dihedral group of order 8 "duplicates". What this means is that if you can get from one graph to the other using the operations in D8, those graphs will give the same answer out at the end. We'd like to avoid processing them more than once and generating loads of duplicate graphs isn't very efficient. We need a scheme to eliminate duplicates early on so we don't have to waste a lot of time generating useless graphs and eliminating them.
One way to pick which graph to keep is to come up with a canonical labelling scheme. This assigns some weight to each lattice coordinate. In a group of duplicate graphs, we seek to either maximise or minimise the sum of the weights. There can be only one graph that satisfies either case, so we choose that one and throw away all the others. It's not possible to generate a canonical graph from a noncanonical one, so this is safe. It also drastically reduces the number of graphs we'll make the next round, speeding up the calculation.