Menu ▾ ▴

#550 kekulize runs "forever" for fullerenes

open
Craig
Library Functions (223)
9
2012-10-23
2009-09-19
Craig
No

The new kekulize algorithm uses a depth-first search that takes "forever" (> 6 hours) to finish for large aromatic systems such as fullerenes.

I will be redesigning this as a breadth-first search rather than depth-first, which should make it converge much more rapidly. The problem with depth first is that it wanders all over the molecule trying to assign thousands and millions of combinations of single/double, when it might be that the very first bond it laid down was wrong. By using breadth-first, the algorithm will ensure that all the bonds in a local region make sense before spreading out to the next layer of atoms. For fullerenes, this should make it converge almost immediately on a solution.

Discussion

  • Nobody/Anonymous

    Nobody/Anonymous - 2009-09-19

    Duplicate of 2841031.

     

  • Geoff Hutchison

    Geoff Hutchison - 2009-09-19

    If you're doing this, you may want to remove the FindSSSR() calls in the aromaticity detection -- it needs the same breadth-first analysis.

    That's PR#1663779 - Carbon fragments (nanotubes, diamondoid) convert VERY slowly

     

  • Geoff Hutchison

    Geoff Hutchison - 2009-09-19

    One more comment -- discussion with friends suggested ~ 14 carbons at the max for aromatic detection. Any longer than that and it's not aromatic, even with the 4n+2 electron rule.