Multigraph Misery

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 augmentation of one single edge and one multiple edge. This augmentation is transformed in the process of making the simple graph, then ordered. Finally, the augmentation in the canonically labelled, layer transformed graph has to be checked to see if it is the chosen augmentation.

Phew! All that remains is implementing it properly...

Comments