Structure generation involves not just graph theory, but group theory. Or, I should say, it does in some of the papers I have read. For example, in this paper by J.L.Faulon, there is the sentence:
which is a little more complex, but shows how 'flipping' each fragment separately combines to form four possible permutations. If this does not seem particularly tricky, consider what happens if you take the direct product of these two groups:
Assuming I have done it right, this should show most (all?) of the automorphisms of the fragment graph. It does look pretty cool, but I don't think that it gets me any closer to implementing the cursed algorithm :)
"The two main steps are to compute the orbits of the automorphism group of G and to saturate all the atoms of a chosen orbitwhich may well be incomprehensible to many readers, except if the reader is a mathematician.
I am no mathematician, but thanks to some books on groups, I now understand both what an automorphism group is and what an orbit is. On the other hand, I also believe that this definition of how the algorithm works is overly complex. A more simple term might just be "fragment sets" - as it is fairly clear, if not mathematically exact. So, for the fragment graph [CH3, CH3, CH2, CH2, CH, CH] the fragment set is [CH3, CH2, CH].
Anyway, here is a short analysis of the automorphism group of the fragment graph [CH2, CH2]. This first image shows the tiny group of permutations that swaps the two fragments:
The notation is taken from an excellent book called "Visual Group Theory" that is also associated with some software called group explorer on sourceforge. It might be quite general, I suppose (and I hope I'm using it right), but it shows the permutation that swaps the fragments as a circled s. This is an automorphism with respect to the edges - in other words, after the swap, there are still bonds between [1, 2], [2, 3], [4, 5], and [5-6].
Another part of the automorphism group is a 'flip' like:
which is a little more complex, but shows how 'flipping' each fragment separately combines to form four possible permutations. If this does not seem particularly tricky, consider what happens if you take the direct product of these two groups:
Assuming I have done it right, this should show most (all?) of the automorphisms of the fragment graph. It does look pretty cool, but I don't think that it gets me any closer to implementing the cursed algorithm :)
Comments