Some Stuff

 Just a trial to see if linking from here to my personal site here : https://gilleain-torrance.net/ affects how google search console indexes it. Nothing else to see here :)

Tailor (https://github.com/gilleain/tailor) is a project that grew out of my attempts to search for catmats   niches  with Prof. Milner-White. The goal of the project was to allow users to define protein structural patterns (called 'descriptions') along with a set of associated measures . More on measures later, but first what is a description? Here is a very simple example: The lines don't have arrowheads, but this is implicitly a tree/DAG rather than a graph. There is a root ProteinDescription  and the leaves are AtomDescriptions  - the DistanceCondition  is referencing the two atoms. Basically, this just defines a pattern of two amino acids (GLY, ALA) with a distance of less than 3Å between the N and O atoms. There are still a lot of details to be worked out here. Can the groups be separated along the chain? If they can, should that require the description to be explicit as to the relationship between sibling nodes? How do we define any number of mat...

Not chemistry, as it happens. I was searching for similar images to one of my line drawings (always fun) and came across these 'number bond things' : The one on the left - hilariously - is just "1 + 1 = 2". Ok, so that's a deliberately jokey example; real ones have larger numbers and one of the three numbers is for the student to fill in. On the right is a more complex example, drawn as a DAG  (directed acyclic graph) although at least one of the example I saw had a node at the bottom with three parents! In any case, what these things really are representing is partitions of numbers - which are usually drawn as Ferrer's diagrams (or Young tableaux) which I'll refer to as "Ferrer's-Young diagrams". These have a superior feature as shown here: So one FY-diagram can represent two  different number bonds. Note that I've made the crazy leap of making number bonds with more than two parts (or 'addends'). Clearly 1+1+3+4 = 9 = ...

The previous post mentioned the restricted weak composition (RWC), but didn't expand on it at all! Basically, I found this excellent paper : " Generalized Algorithm for Restricted Weak Composition Generation " by Daniel R. Page. It even gave some java code in an appendix - good stuff :) Anyway, a RWC is a composition (which is a partition where order matters) that is weak  - has zeros in it - and the parts are restricted . So [1, 0, 1, 1] is a weak composition of 3 into 4 parts and lets say we have restricted the parts to {0, 1, 2}. Here is an overview of the scheme: where we take a degree sequence, convert to a multiset and use a RWC to get a particular sub-multiset. This allows us to take some count of some subset of elements from the multiset. Doing this for all sub-multisets at each round should then allow us to list graphs - although not without redundant examples:  This shows all starting points for 3 -> [3, 2, 2, 1, 1] and ...

So in the last post about listing trees  I outlined a slightly cumbersome method to list trees from degree sequences. Thinking about it a bit more, it would probably be far easier to just list all trees on some number of vertices and filter out by degree sequence. I talked a little about the WROM algorithm in this old post  which is a constant time generator of 'free' (unlabelled) trees. Anyway, that's boring so I was trying out the more complicated approach. It looks like generating a single  tree from a degree sequence is as simple as the Havel-Hakimi method. Connect the largest degree (dn) to the dn next largest degrees.  Also maintain a list of vertices that have already been connected to, and then at the next step connect only to those not already connected to. So, for [3, 3, 2, 1, 1, 1, 1] we get: You might notice that trees a) and c) are isomorphic. Below the trees labelled by degree are the same trees labelled by DFS discovery order, and below that th...

Although stack overflow is generally just an endless source of questions on the lines of "HALP plz give CODES!? ... NOT homeWORK!! - don't close :(" occasionally you get more interesting ones. For example this one  that asks about degree-restricted trees. Also there's some stuff about vertex labelling, but I think I've slightly missed something there. In any case, lets look at the simpler problem : listing non-isomorphic trees with max degree 3. It's a nice small example of a general approach that I've been thinking about. The idea is to: Given N  vertices, partition 2(N - 1) into N parts of at most 3 -> D = {d0, d1, ... } For each d_i in D, connect the degrees in all possible ways that make trees. Filter out duplicates within each set generated by some d_i. Hmm. Sure would be nice to have maths formatting on blogger.... Anyway, look at this example for partitioning 12 into 7 parts: At the top are the partitions, in the middle the trees...

So the bug with C19H14 and C10H16 formulae seems to have been due to the partition refinement not correctly labelling structures with particular arrangements of multiple bonds. The underlying problem is in the equitable  partition refinement process. This is a short note about the problem. Equitable refinement of a partition for a graph is the formation of a vertex partition where each element of each block of the partition has an equal number of neighbours in the other blocks. This is a little difficult to imagine, but it is - roughly - a generalisation of the Morgan number algorithm which attempts to find labels for sets of vertices which are stable with respect to splitting them by the labels of the neighbours. For example: This image shows a cub-2-ene like molecule (or a cube graph with two of the edges colored). Clearly the orange and green vertices are in 'different' sets in some sense. Precisely, they are in different blocks of the equitable partition ([0,2,5,7|1...

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...

There is a whole area of study on visualisations called cartograms - most appealing are the ones that make countries look like inflated or deflated balloons . The rectangular versions of these are less pretty, but more interesting to me from a graph theory perspective. I came across this subject via an impressive masters thesis  by Vincent Kusters : ' Characterizing Graphs with a Sliceable Rectangular Dual' … which is a title that will take some explaining. Firstly, what is a 'rectangular dual' when it's at home? Well check this out: Clearly the thing on the left is a graph, and on the right is its rectangular dual - in fact, this is the smallest 'sliceable' dual. By sliceable, I mean that the white rectangles can be made by recursively slicing up a rectangle. For example, if a slice is like [{0, 3, 4, 5, 6}, {1, 2}] for making the first split into the areas of 1 and 2 on the right, and all the rest on the left. The next could be [{0}, {3, 4, 5, 6...

So I should correct something that I posted a while ago  about embedding 3-connected graphs. The most obvious examples of this class of graph are polyhedra  - tetrahedra, cubes, etc - and maybe it's obvious that there is only one  way to embed these in the plane. So in that sense, 'enumerating' the embeddings for these graphs is quite easy ... there's just one to count. Of course, this embedding can be drawn with any of its cycles as an outer face; this is what gave rise to the different looking drawings. I guess the way to think about it is that the embedding is on the surface of a sphere - where there is no 'privileged' face to call the outer  face - and that the drawing on the plane just picks one of the faces to 'squash flat' as I put it back in (wow) 2011. Anyway - on to Whitney flips! There are a class of graphs that can be embedded in the plane in different ways (that is, the combinatorial map is different for the same outer face). These ...

At the end of last year, I updated the metadata on some 175,000 or so items in the Cambridge DSpace repository . These were molecules that made up a copy of the ' WWMM ' (the  W orld W ide M olecular M atrix) and they had old 'IChI' identifiers rather than the newer InChI  and InChIKey identifiers. So now - after this update - you can use a search engine to google  … er, search for  compounds by their InChIKey. For example: YMSFBKYTOUKHOI-UHFFFAOYSA-N gives just two results, one of which is from PubChem , and the other is Cambridge Repository. Hilariously, the image from PubChem is this: when the formula is C32H60N4O4. I assume that the connectors in this cycle are just alkane chains, but the layout fails for this kind of 'cyclic lipid peptide' (or whatever it is called!).

So, a student asked me about a homework question that is a sub-problem of the structure generation problem . Basically, it was to count  the number of chemical structures with exactly one  cycle given the elemental formula. Of course, the best solution here is probably to use the Polyá Enumeration Theorem  since all that was asked for was a count (enumeration) of the structures. Naturally, I have a different way to do this - especially since I don't really understand the mathematics of PET enough to implement it. So: The image shows a rough overview of how I might list  all of the structures with a single cycle. It takes a number of necklaces (one shown), and a number of trees, and glues the one to the other in all possible ways. The word ' necklace ' here is specifically the combinatorial object; so  the cyclic sequence CNCNO is the same as CNOCN since you can rotate one to get the other. One tricky decision here is whether to add multiple bonds to the...

So recently I was asked about Király's method for generating all graphs from a degree sequence . While refactoring some of the code that I wrote to do this, I also made some tests. Specifically, coverage tests to check that the generation was actually exhaustive. I know it's redundant, but I have good tools to remove duplicate graphs - or I thought that I did… Here a rough flowchart of the procedure here, starting with a number ('n') that is passed to Dreadnaut (the interface to nAUTy ) to generate graphs: These graphs are grouped by degree sequence, and these degree sequences are fed into the KirályHHGenerator to reconstruct the set of graphs. I think that compare arrow is wrong, but never mind. The point is that the sets should be the same size. They are for n=5,6,7 but not for 8. Oddly enough, however, there are more  in the Király set than in the nAUTy set. The obvious conclusion would be that my duplicate detection is failing - in other words, I am failing...

EDIT : After some more tests, I now realise that this is not really as great a vertex label/descriptor as I thought it was. For example, see these four graphs on 7 vertices that fail to distinguish vertices properly: The first one should have a central vertex in a different class than the other blue vertices. The green class in the second graph should be split, and same for the third graph. And so on. So, in the last post I talked about the ideas of Randić et al for calculating the 'centrality' of vertices in a graph. Interestingly, the numbers calculated for each vertex act as a kind of equivalence class label or vertex invariant. This is similar in many ways to Morgan numbers  (sorry, Egon's post doesn't actually explain them, but they are the sum of degrees across extended neighbourhoods). For example, here is one of the examples from the previous post: With the centrality matrix in the middle, and the 'label' made by sorting the row eleme...