Some Stuff

The simplest-yet-most-complex example I could find is this one from another previous post (I like to recycle :) I should mention again that I don't know if this is an actual chemical. I call it 'bowtieane', but maybe it has a proper name. In any case, it makes a nice small test case. The ring equivalence classes shown (A, B, C) are defined by the signatures as usual. What's really strange though is SSSRFinder's partition of the rings. It divides the two A-rings into separate classes. This seems like the opposite behaviour to the fullerene-26 case where there were fewer equivalence classes than for the signature method. I really, really should read the papers referenced in the code.

There is an example graph that makes for a better comparison between my code and the SSSRFinder. It is the 'fullerene-26' molecule that I used in a previous post . Unfortunately the diagram is wrong in that post; the one below has the correct vertex equivalence classes (colors): The difference is just a pair of yellows that should have been pink (and v.v.) in the topmost C ring. Anyway, the graph is complex enough that there are different vertex symmetry classes without multiple bonds. Dodecahedrane, on the other hand, is so symmetric that without double bonds all vertices are the same. So how does the SSSRfinder do? Well it considers all the rings to be different apart from two of the B rings. It is not reporting the final B ring, which could be considered as the bounding face of the map. In short, there are two equivalence classes (5-ring and 6-ring) which makes some kind of sense but isn't terribly informative.

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 hubris and arrogance, I implemented my own ring equivalence class finder. With humility and grace, the SSSRFinder method getRingEquivalenceClasses does better for at least one case: This is the test case used in SimpleCycleBasisTest, and probably in the paper on the subject. I guess I should read that instead of other papers on cycle bases. I do get the same answer for cuneane as when I do it by hand . That is to say, 3 equivalence classes with [1, 2, 2] elements. For the 'Bauer' graph above (as I am currently calling it - Ulrich Bauer is the author of the SSSRFinder) the signature method puts almost every vertex in its own equivalence class. Now my method makes equivalence classes from cycles with the vertices in the same vertex equivalence class. Naturally enough, this makes a lot of ring equivalence classes. The graph on the left has vertices colored by degree, to show how dissimilar the rings are. Is the SSSRFinder really getting the right answer?

Another example from a paper that I have mentioned before . This time the Herschel graph which is another of these crazy graphs thought up to prove or disprove some conjecture. The spring-layout paper gives two different layouts: These really are the same graph :) One way to see this is to look at the vertex colors that I have applied. Each face is given a label (A or B) based on the key shown below the two graphs. The 'A' face is {Black, White, Grey, White} for example. The left-hand embedding (or layout) has such an A-face for its border, while the right-hand one has a B-face for a border. Presumably, it is possible to convert a vertex partition (into equivalence classes) into a partition of faces. It seems easy for examples - like this - that have a planar embedding. More difficult for graphs that don't have one. On the other hand, not all planar layouts look very informative: This is twistane (again) but not looking as symmetric as it can. However, the faces show the r...

Although many ring systems in molecules are quite easy to layout as 2D diagrams, there are some that are inherently 3D. Bridged rings are usually in this class; consider my favourite example molecule, cuneane: Each of (A, B, C) is a particular layout of the same molecule, but with a different boundary (hexagon, pentagon, er...kind of fused squares). It would be nice to have a layout method that picked the same choice each time - regardless of the permutation of atoms and bonds. Even better if it could allow enumeration of the alternative possibilities. As another example, consider a series based on twistane (which is a molecule) to two other graphs that may well not be actual molecules: Twistane itself is in the middle, surrounded by five- and seven- ring equivalents. The upper layouts emphasise one ring in the graph while the lower ones emphasise the dual rings in each.

It is difficult to publish negative results in a journal, but a blog post seems like a good place to record the experience. Especially situations like this, where it probably should have been obvious not to try in the first place... So; what is modular decomposition ? Briefly, a module is a little like a connected component in a graph - indeed, a connected component is made up from one or more modules, but modules can overlap. Decomposition of a graph into its modules is, therefore, like finding the connected components of the graph. An example is shown here: Two modules in the graph are circled, there may be others. The definition is a set of vertices that have the same neighbours outside the set. So, there was no need for me to make them complete graphs, but it looked nicer. Anyway, already looking at this example it is clear that these are not very 'chemical' graphs. They look more like networks (for example, see : [1]). Indeed, I tried out some code made by the authors of a...