On Nov 2, 2018, at 01:33, Xianghai Sheng <xsh...@ucmerced.edu> wrote: > I am trying to figure out the time complexity (Big O) of converting from > OBMol to canonical smiles.
I don't think that's a useful way to think about your problem. Graph canonicalization is "at least as computationally hard as the graph isomorphism problem." https://en.wikipedia.org/wiki/Graph_canonization , and graph isomorphism is believed to be quasi-polynomial. That said, I believe the actual algorithm Open Babel uses may have exponential time for some graphs. However, most molecular graphs don't reach the worst-time behavior. Furthermore, time complexity is mostly useful when thinking about large N. Molecules typically have small N, and there may be lower-order terms which dominate the times for small N. If you are interested in the topic of graph canonicalization algorithms in general, you might start with the nauty papers; see http://pallini.di.uniroma1.it/ > I want to know this because getting canonical smiles takes up half of the > running time of my reaction path searching program. How would knowing the time complexity help you? While this may be obvious, if canonicalization takes 1/2 the time, then you'll only get 2x speedup even if that time goes to 0. How much work are you willing to do for a 2x speedup? Might it be possible to do about the same amount of work to parallelize your algorithm? For example, if your reaction path search generates a set of nodes which must all be canonicalized in order to evaluate them, then you can do all of those canonicalizations in parallel. Cheers, Andrew da...@dalkescientific.com _______________________________________________ OpenBabel-discuss mailing list OpenBabel-discuss@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/openbabel-discuss
