Some Stuff

So the previous post  pointed out the problem with a simple extension from a seed : you miss some. In detail, two of the problems are: Difficulties with growth from a seed Firstly, A shows the - slightly obvious - idea that for some (seed, leaf) pairs you can only get from one to the other by adding edges and not vertices. This problem is easy enough. As for B , I show here a detailed (if made up) example of the main problem : augmentation of a seed is not necessarily canonical. Or, to put it another way, the canonical deletion can lead to a sibling of the seed, rather than the seed itself. I think the way round this might be to restrict the candidate atoms (or bonds, even) for canonical deletion to those outside the original seed. In other words, canonically label the augmentation to give the ordering of atoms/bonds then choose the largest labelled one that is not in the seed.

With the recent revival of the moleculegen (AMG) project, I've started to properly think beyond just simple generation of spaces from a formula. For example, there are 4 trillion or so C30H62 structures - which might take ... a while. In any case, one useful feature would be to have good/bad lists of substructures (or 'nice' vs 'naughty' as I've been thinking of them. One simple approach I thought might work is to just start with the largest good substructure and generate from there. This can  work : C9H16 from 6-cycle (By-the-way : all images done with John May's new Depict utility! It's wonderful to use :) Which is great! Except that it doesn't always work. The problem is that leaves on the tree with a particular substructure might not have that substructure as a common parent in the tree. Consider these C6H8 structures generated from a 4-cycle: C6H10 from 4-cycle These are not all of them. Now we filter out using subgraph i...

Visualising canonical augmentation trees of molecules is not quite as good as I thought: Or perhaps I should use a different tree layout. Probably a circular one. Edit. Like this:

Very occasionally there is a question on math stack exchange that I can actually give some kind of useful answer to. This question  caught my eye; the questioner asks whether graphs with the same degree sequence have the same biconnectivity property. Or to put it another way, are there any pairs of graphs with the same degree sequence but one is biconnected and the other is not? I thought of an example of such a pair, and another user supplied a much simpler one, but here are both pairs: The vertices are coloured by degree (4 = orange, 3 = blue, 2 = green); the red arrows show a transformation of the top graph into its non-biconnected partner. Obviously there may be more than one, I've no idea how many members of a set of isodegree graph might be expected to be biconnected. For the record, here is the transformation of the bottom pair: The red lines bisecting edges indicate a kind of 'bond breaking' although it's not meant to represent an actual chemical r...

So another lesson reluctantly learned... It seems the naïve approach to augmenting molecules by sets of bonds (colored edges, strictly rather than multiple edges) did not work. For example this pair of C9H16 graphs: Thicker lines represent double bonds, and the thinner are singles. The parents of these are non-isomorphic - which is easy to see if you just remove the 6:8 edge from both. However, they cannot be distinguished as augmentations by my current method as the canonical labelling each one gives a graph where the last bond added is the 'natural' canonical choice. The alternative might be to use the canonical labelling method for multigraphs suggested by the  nasty  manual which involved transforming the multiedge graph into a layered simple graph. This is illustrated in this example: The transformation converts single edges into an edge in the first layer, and multiple edges into an edge in the second layer (and so on). Highlighted in purple is an example ...

My newest version of canonical path augmentation code for generating graphs has reached a new high point - generating 11,716,571 graphs on ten vertices. Of course, it also gets the number of nines (261,080) and the number of eights (11,117) correct as well ... which is great, but I'm cautious about declaring it 'correct'. Especially given the last version  did not get the sevens and eights right. See, for example these past failures: So how does it get the right answer? Well, it now properly uses the method mentioned in this post  to only pick canonical deletions that are not cut-vertices . That turns out only to be necessary for graphs on 8 vertices, but you still have to check this for all augmentations, which seems expensive. However, there was a more fundamental problem; consider the example below (basically nicked from Derick Stolee 's blog post): Obviously A and B are isomorphic, yet how do we properly distinguish them? Well, the key is the set of vert...

So, I admit that the original reason for looking at sliceable rectangles  was because of this gaming stackoverflow  question about generating dungeon maps. The approach described there uses something called a binary split partition tree ( BSP Tree ) that's usually used in the context of 3D - notably in the rendering engine of the game Doom . Here is a BSP tree, as an example: In the image, we have a sliced rectangle on the left, with the final rectangles labelled with letters (A-E) and the slices with numbers (1-4). The corresponding tree is on the right, with the slices as internal nodes labelled with 'h' for horizontal and 'v' for vertical. Naturally, only the leaves correspond to rectangles, and each internal node has two children - it's a binary tree. So what is the connection between such trees and the sliceable dual graphs? Well, the rectangles are related in exactly the expected way: Here, the same BSP tree is on the left (without some label...