Some Stuff

An essential tool for graph generation is surely the ability to draw graphs. There are, of course, many methods for doing so along with many implementations of them. This post describes one more (or perhaps an existing method - I haven't checked). Firstly, lets divide a graph up into two parts; a) the blocks, also known as ' biconnected components ', and b) trees connecting those blocks. This is illustrated in the following set of examples on 6 vertices: Trees are circled in green, and blocks in red; the vertices in the overlap between two circles are articulation points. Since all trees are planar, a graph need only have planar blocks to be planar overall. The layout then just needs to do a tree layout  on the tree bits and some other layout on the embedding of the blocks. One slight wrinkle is shown by the last example in the image above. There are three parts - two blocks and a tree - just like the one to its left, but sharing a single articulation point. I had...

Fairly simple post here : radial tree layout of trees. Here is an image for trees on 8 vertices: The center vertices are colored red, similar to the top-down image in this post . Oh, and degree-2 vertices are arranged as if they were degree-3, which looks nicer I think (similar to chemical layouts).

There is an effort going on to improve the double bond assignment machinery in the CDK, which is great. Of interest to me, however, is how many possible arrangements of double bonds can you have in fused ring systems. This was mentioned in at least one previous post  - or perhaps two . However, lets get a very rough upper bound; how many ways are there to color the N edges of a graph with two colors? This is 2 to the power N, or the set of all subsets of the edges. Of course, many of these are chemically meaningless, where atoms have too high a valence. So filter out those where adjacent edges have the same color - or more exactly, where adjacent edges are colored with the 'double bond' color (let's call it '2'). The image shows a sketch of the simple procedure (above) and a slightly better approach (below). The better way of doing things is similar to the k-independent chessboard  solution (sorry to link to my own pages so much - but it is relevant!). The ...

As the title states - this is a computationally expensive way to get all rings in a graph, but it's fairly simple, and illustrates some nice principles. For a better way to do things, perhaps Rich Apodaca's description of the Hanser, Jauffret, and Kaufmann algorithm would suit. Anyway, back to the expensive way. The set of cycles in a graph form what is called a 'cycle space'  - which I didn't understand at all for a while, but is not actually that hard. For example, here is a basis set for the cycle space on a 3x3 hexagonal lattice: Looks like a bunch of cycles, really. The important thing is that it is possible to combine any subset of these cycles to get another cycle (or one of the other cycles in the basis). By 'combine' we mean XOR or the symmetric difference  of the edge vectors. This sounds more complicated than necessary, so it's useful to consider a simple example. Well, the example is simple - the picture is not: On the left here...

So, first a small correction to the last post  : a 'honeycomb' layout is a cycle on a hexagonal lattice, while the other layouts there are not on-lattice. I've renamed them 'flower' layouts, as I'm not sure if they have a name - they're not at all new, I just haven't looked! To be clear: these are two different layouts of the same 12-cycle. As it happens, the honeycomb layout is also a [5, 5, 5]-flower layout with straight edges on the first edge of the outer cycle. However, not every honeycomb is a flower. There might be many ways to do it, but one way to make honeycomb layouts is to find cycles on a hexagonal lattice. Assuming, of course, that you have such a lattice already - it's not terribly hard to make one, but connecting it up properly is a bit fiddly. Luckily, it turned out that making the dual  of a triangular lattice is slightly easier. To see how this works, consider the three possible (regular) planar lattices: The grey dots ar...