Reinis Danne <rei4...@gmail.com> wrote:
> > I think it was the thread where I mentioned I'm working on
> > kekulization algorithm using graph theory (maximum matching). It
> > has been quite some time when I last looked at that code and it
> > is not yet usable.
>
>
I don't know if this overlaps with your work, but I spent a fair amount of
time on the aromaticity-detection algorithm and improved it by orders of
magnitude. See the comment in kekulize.cpp around line 887 -- copied below.
Craig
NEW ANALYSIS methods: rely on LSSR methods to only target one ring. Works
much faster on fullerens, graphene, etc.
Recursive function to find a sensible kekule assignment of single and
double bonds for an aromatic ring system.
Very large aromatic ring systems can be very computationally difficult. In
theory, there are 2^N ways to try assigning single/double to assign bonds
(where N is the number of bonds in the aromatic system). For large
molecules such as fullerenes, this number (e.g. 2^60) exceeds all computing
power in the world.
To avoid this, three strategies are used.
1. The algorithm proceeds by assigning bonds to each complete ring
from the LSSR, rather than treating the whole aromatic system.
That reduces the complexity to roughly O(2^R) where R is the number
of rings in the LSSR.
2. Each time a ring is completed (a trial assignment of
single/double), the whole tentative assignment is checked for
sensibility. If any atom has all of its bonds assigned, but
still has a leftover electron, then the assignment fails before a
lot more work is invested. (Atoms connected to bonds that haven't
been examined yet are ignored during this test.)
3. When one ring is finished, the next ring is selected by finding the
one "most connected" to previously-considered rings. Say, for
example, we're working on a fullerene and have just finished one
ring. The second ring will be one that's adjacent to the first
ring (one of its bonds is already assigned). Now for the third
ring, we can pick one that's in a "corner" of the first two, that
is, a ring that has TWO bonds already assigned.
Strategy #3 means that the completed area of the ring system (the bonds
we've already assigned) will tend to have a "minimal perimeter", and any
atom that has one bond assigned will quickly have all of its bonds
assigned. That means that strategy #2 can be used as early as possible to
detect bond assignments that can never work, long before the entire
aromatic system has been examined. Strategy #1 means that we can typically
assign alternating single/double bonds correctly to any particular ring on
the first try.
Together, these three strategies together mean that even very large
aromatic systems are typically solved in milliseconds.
------------------------------------------------------------------------------
Own the Future-Intel® Level Up Game Demo Contest 2013
Rise to greatness in Intel's independent game demo contest.
Compete for recognition, cash, and the chance to get your game
on Steam. $5K grand prize plus 10 genre and skill prizes.
Submit your demo by 6/6/13. http://p.sf.net/sfu/intel_levelupd2d
_______________________________________________
OpenBabel-Devel mailing list
OpenBabel-Devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/openbabel-devel
