Some Stuff

So there was this guy called Euler, and he had a formula that goes something like F = E - V + 2. Well, actually it is χ = V - E + F, where χ is the Euler characteristic , and this is equal to 2 for polyhedra. Anyway, the point is that dodecahedrane has 12 faces (cycles). For the SSSRFinder, however, it has only 11; which is annoying. Moreover the ring equivalence class method only distinguishes based on the underlying simple graph - in other words it ignores bond order. In some applications this might be exactly what is needed, but I'm glad that my method gives a more detailed result: So, apart from being a ridiculously detailed image, the above shows the face (ring, cycle) equivalence classes for dodecahedrane with a particular double bond network . Clearly any face could be 'glued' to another along one of the edges, following the vertex classes. All possible combinations of faces are shown in the 'face quotient graph' at the bottom right.

With the canonical code in place (thanks to open source :) the structure generation goal is much nearer. The first thing to improve is the bond compatibility . This image shows cuneane ( again !) and the bond compatibility table. The table is tricky to calculate, but relatively easy to understand; there is only one bond between atoms of type A - so there is a one in the cell (A, A). Conversely, no atom of type C is connected to an atom of type A ( see this for more detail), so there is a O in both (C, A) and (A, C). Note that the table is not symmetric, as can be seen with (A, B) = 1 and (B, A) = 2. This makes sense, in that an atom of type A is connected to two of type B, and yet an atom of type B is only connected to one of type A.

While debugging the methods to make canonical signatures, I learned something about tree isomorphism from various sources, including Prof. Valiente 's excellent looking book on trees . One way of checking isomorphism is canonisation, since two trees are only isomorphic if they have the same canonical form. For simple labelled trees, it looks like there is an almost trivial way to get a canonical string representation. Say we have two trees: The are rooted, labelled trees. So the conversion to a canonised string proceeds as follows; for each node, lexicographically sort the string form of the labels of its children, and return the concatenated string. In python this looks like: which...is unreadable. hmmm. Wish there was a better way to get marked-up code into blog posts. Perhaps there is one, and I don't know of it. Anyway, the point is that it is very short. edit : the code is... def printSorted(node): if len(node.children) > 0: childStrings = [printSorted(child) for ch...

This is straying from the point; but if any graph can be described by canonized trees made from its subgraphs, then what are the properties of very large (regular) graphs? A grid, for example? Starting with a square, and fusing squares together results in this situation: two and three fused squares are similar, at the height-two tree level. With four rings, a new type c appears ( b becomes b' with three rings). Beyond this point, any number of rings fused in a row like this has the same structure. Moving to a second dimension of growth, a square grid (G nn ) has the following structure: On the left are 'snapshots' of the advancing wave of the tree. Looks a lot like a breadth-first search, I suppose. On the right are the trees for each snapshot, with increasing heights. Although this is not shown, 8 of the 20 leaves of the third tree are duplicates. This should be clear from the third snapshot, which has only 12 (filled) circles on the 'wavefront'. These trees can e...

This is a throwaway mathematical point, that I am not qualified to make, but it looks like three of the previous examples (diamantane, twistane, and cuneane) have a very abstract connection when colored by signature: what I mean by this diagram is that diamantane has atoms colored by (a) connected to both other (a) atoms, and to (b) atoms. Its (c) atoms are only connected to (b)s; the arrows could well be double-headed, by the way. The most complex situation is cuneane, where each 'type' of atom is connected to another in its type and to two in another type. Adamantane would just look like : (a)-(b). Interesting, but it doesn't get the signature canonization methods debugged any faster...

After cubane, the thought occurred to look at other regular hydrocarbons. If only there was some sort of classification of chemicals that I could use look up similar structures. Oh wate, there is . Anyway, adamantane is not as regular as cubane, but it is highly symmetrical, looking like three cyclohexanes fused together. The vertices fall into two different types when colored by signature: The carbons with three carbon neighbours (degree-3, in the simple graph) have signature (a) and the degree-2 carbons have signature (b). Atoms of one type are only connected to atoms of another - the graph is bipartite . Adamantane connects together to form diamondoids (or, rather, this class have adamantane as a repeating subunit). One such is diamantane , which is no longer bipartite when colored by signature: It has three classes of vertex in the simple graph (a and b), as the set with degree-3 has been split in two. The tree for signature (c) is not shown. The graph is still bipartite accordin...