Some Stuff

There is an interesting book by W. T. Tutte  called ' Graph Theory as I have known it ' which is a cross between a normal mathematical text and a biography. So it's a description of the areas he was interested in, and his theorems. One thing that interested me was the use of a 'twist' operation on cubic graphs like so: Where for the edge between vertices x and y labelled 'A' we reconnect the surrounding edges to form the arrangement on the right hand side. So detach edge D from y and connect it to x, and vice versa with edge C. The lower part of the picture shows what happens for a loop-edge - it transforms to a multi-edge. This operation is used on a family of 'base' graphs looking like this: with the first in the list is a vertexless loop graph - that is, it has no vertices and a single edge. From these base graphs, the twist operation can form any cubic graph. Note that all of U n are cubic with 2n vertices. For example, from U 3 we ...

A bug in the CDK implementation of my signature library  turned out to be due to the fact that the bond colors were hard coded to just recognise the labels {"-", "=", "#" }. The relevant code section even had an XXX above it ! Poor show, but it's finally fixed now. So that means I can handle user-defined edge colors/labels - consider the complete graph (K5) below: So the red/blue colors here are simply those of a chessboard imposed on top of the adjacency matrix - shown here on the right. You might expect there to be at least two vertex signature classes here : {0, 2, 4} and {1, 3} where the first class has vertices with two blue and two red edges, and the second has three blue and two red. Indeed, here's what happens for K4 to K7: Clearly even-numbered complete graphs have just one vertex class, while odd-numbered ones have two (at least?). There is a similar situation for complete bipartite graphs: Although I haven't explored...

As promised (in the previous post ) I've now made Jmol scripts to show the atom/ring equivalence classes. I still think that the ring ones are more clear, but I suppose it depends on what aspect of the symmetry of the structure is needed. As an example:  Shown here is a C70 structure, with coloured circular plates at the centre of each face. It should be clear that there is an axis of symmetry running through the middle, from one blue plate to the other. Around the blue is a ring of green, and 5 rings in between. The slight difficulty in all this was working out the ring equivalence classes. There is an existing CDK method to do this - in the SSSR ring finder - but it seems to give too many classes. The way I did it was to first find atom equivalence classes (or 'orbits') using signatures. Then each ring is a circular list of the orbit indices : which I'm going to call a 'ring code'. See this image for illustration: These two rings (A and B) have the s...

The concentric face layout code is working well enough now to handle the larger fullerenes - such as that old favourite , C60. Since coloring the vertices by equivalence class is not always terribly informative, here is a view of the ring equivalence classes : Where C60 is on the left, and a more colourful C70-D5h is on the right. One difficulty, however, is to understand the symmetries of these structures when they are distorted like this. The further away from the center of the layout, the more stretched the rings become. So, an obvious next step was to 'blow up' these 2D layouts into 3D. It turns out that is possible, with a combination of inverse stereographic projection  and Jmol 's minimize command. The first step is necessary since minimizing the 2D coordinates (with a z-coord of zero) just shrinks the diagram down in the plane. Here are before and after shots of these steps: Clearly the inverse-projection does not give very good 3D positions for the...

Having tried (and failed) to layout fullerene structures using various optimisation methods, I thought I would try direct positioning of the atoms. In other words, 'logical' placement rather than 'physics' based layout. For example: These are two regular fullerenes that work very well. The algorithm is simple in principle: 1) Given a planar embedding G , calculate the inner dual   id(G) and the 'face layers'. 2) The innermost layer is the 'core' which is one of: a single vertex, a connected pair, or a cycle. 3) Layout the core, and then each layer outwards, by spoke and arch. So, to explain some of this; a 'face layer' is a set of faces all at the same distance from the outer cycle, measured by graph distance on id(G) . So the faces adjacent to the outer cycle are the first layer, and the second layer is adjacent to that, and so on. This is roughly illustrated here: The concentric circles represent the layers of faces, with th...

A  comment  on my previous post reminded me of the "EquivalentClassPartitioner" already in the CDK, written back in 2003 by Junfeng Hao and based on this article  by Chang-Yu Hu and Lu Xu. After some testing, it seems they give the same results on various molecules - although, if you only want the equivalence classes  the Hu/Xu method is much, much faster. Like 10-100 times faster. The test molecules I used for comparing speeds are a library of fullerenes  that range in size from 20 carbons up to 720. Naturally, I started with the smaller ones, but even there the difference was clear. For instance, here is a table of numbers from the C40 run: The left-hand column is just the name of the cc1 file, the next two columns are the times for the AtomPartitionRefiner and EquivalentClassPartitioner, and the last two are the order of the automorphism group and the number of equivalence classes. Times are in milliseconds, so clearly the HuXu method is far fast...

There is a new module and package for the CDK that is currently under review. This is a short guide to how to use it - to help both reviewers and users. The basic idea is that molecules can be considered as a kind of graph , and that one useful thing to calculate about such graphs is the  automorphism group  that preserves element labels and/or bond labels. To put it another way, calculating the symmetries  of the molecule - although I should point out that it's not quite the same as the crystallographic symmetry groups. As a simple example, consider these two molecules (1,4-cylohexadiene and 4h-pyran) : They are numbered from 0-5 for programming convenience; on the right each molecule has a table of automorphisms written as permutations in cycle notation. It should be fairly obvious that - for example - the H-Flip sends atom 0 to atom 4, 1 to 3, and fixes 2 and 5. Only the H-Flip is an automorphism for 4h-pyran, due to the oxygen atom. The code to do this i...