Some Stuff

Disconnected graphs were mentioned in this post on OMG's algorithm. I also said that signatures could not handle such graphs, but this is not totally true. Here are a couple of approaches to handle them. Firstly, why is this a problem at all? Well, a signature of a graph is a bit like a spanning tree  - and the canonical signature is the maximal string form of the set of trees. However, for disconnected graphs you get a spanning forest  - which is just a set of spanning trees. The maximum tree from the forest will no longer span the whole graph. The image shows an example of this for a very simple graph. The upper panel shows a disconnected graph and its corresponding forest. The lower panel shows two different labelings of the same graph (A, B) and their canonical form. The algorithm for canonicalization simply has to 'paste' together canonical labels or signature strings, and has to make sure that a canonical signature is generated for each component. The compone...

While out looking for an algorithm to check for bridges in graphs , I found this paper  by Jens Schmidt . It's very simple, and claims to be as fast as Tarjan's classic algorithm. The basic idea is to make something he calls a 'chain decomposition' of the graph, where a 'chain' is either a cycle or a path. This is quite similar to the 'parts' of a graph I described here , except more formal than my slightly ad-hoc definitions. Bridges, then are just those edges that are not in a chain. For example, take the graph from the paper: Click for bigger, as always. First make a spanning tree from the graph, and store the back-edges (curved edges in the picture). Then go through the back-edges in order of the depth-first index, and make chains from them and the tree edges. A chain that ends up back at the start is a cycle, otherwise it is an edge. The chains A-E are shown in the middle, along with a bridge F. The author also claims that the chain de...

With the recent release of the Open Molecule Generator (OMG) I thought it would be nice to add to (or augment ) the description of the algorithm in the paper . The description here will be in terms of graphs, but the principle is largely the same. OMG's algorithm is a variant of McKay's canonical path augmentation algorithm , as mentioned before here . However, instead of augmenting by vertex it augments by edges. To illustrate this, consider a diagram for graphs with up to 4 vertices: The graphs are grouped by vertex count (boxes), and each box is sorted into columns. Along the top are the number of edges for graphs in that column, and along the bottom are number of vertices for graphs in the box. Two graphs are connected by an arrow if the larger can be made from the smaller by adding a single edge. A couple of important things to note about edge-addition are : 1) two paths can lead to the same graph, and 2) at least one of the graphs is disconnected. The first of th...

One of the most popular queries that lands people at this blog is about the isomers of C4H11N  - which I suspect may be some kind of organic chemistry question on student homework. In any case, this post will describe how to find all members of a small space like this by hand  rather than using software. Firstly, lets connect all the hydrogens to the heavy atoms (C and N, in this case). For example: Now eleven hydrogens can be distributed among these five heavy atoms in various ways. In fact this is the problem of partitioning a number into a list of other numbers which I've talked about before . These partitions and (possible) fragment lists are shown here: One thing to notice is that all partitions have to have 5 parts - even if one of those parts is 0. That's not strictly a partition anymore, but never mind. The other important point is that some of the partitions lead to multiple fragment lists - [3, 3, 2, 2, 1] could have a CH+NH2 or an NH+CH2. The final ...