Well, if I'm recalling correctly, a highly symmetric structure like buckminsterfullerene takes a long time to canonicalize.
I don't know what the formal definition of a planar graph is, but I would guess it's not what chemists mean when they say a molecule is planar. -P. On Thu, Jun 15, 2023 at 2:51 PM S Joshua Swamidass <swamid...@gmail.com> wrote: > Incidentally, > > I came across this O(log N) canonization algorithm for planar graphs: > https://arxiv.org/pdf/0809.2319.pdf > > I wonder if this algorithm can be adapted for chemistry? Molecules are > usually planar, but I believe they occasionally are "nearly" planar, by > which I mean planar graphs plus a few edges that break the planarity. > > And what (generally speaking) is the algorithm used by rdkit? Do we know > it's complexity? > > > > > On Thu, Jun 15, 2023 at 1:38 PM S Joshua Swamidass <swamid...@gmail.com> > wrote: > >> Andrew, >> >> Thanks! According to wikipedia (and my recollections of algorithms >> class)... >> "The problem is not known to be solvable in polynomial time >> <https://en.wikipedia.org/wiki/Polynomial_time> nor to be NP-complete >> <https://en.wikipedia.org/wiki/NP-complete>, and therefore may be in the >> computational complexity class >> <https://en.wikipedia.org/wiki/Complexity_class> NP-intermediate >> <https://en.wikipedia.org/wiki/NP-intermediate>." >> https://en.wikipedia.org/wiki/Graph_isomorphism_problem >> >> Your reference though is really helpful. The key phrase seems to be >> "bounded valence" which is certainly true of molecular graphs. Each atom >> can only bound some fairly low number of other atoms, i.e. bounded valence. >> That's probably the reason why we do have a polynomial time algorithm... >> >> Thank you! >> >> Joshua >> >> On Thu, Jun 15, 2023 at 1:21 PM Andrew Dalke <da...@dalkescientific.com> >> wrote: >> >>> On Jun 15, 2023, at 18:20, S Joshua Swamidass <swamid...@gmail.com> >>> wrote: >>> > It's well known that the graph-isomorphism problem is NP >>> >>> While P is contained in NP, I don't think that's the NP you mean. >>> >>> I suspect you may be thinking of subgraph isomorphism, which is NP-hard. >>> Graph isomorphism may be quasi-polynomial time, if Babai's (unpublished) >>> claim is correct. >>> >>> Also, "Isomorphism of graphs of bounded valence can be tested in >>> polynomial time" - >>> https://www.sciencedirect.com/science/article/pii/0022000082900095 . >>> >>> >>> > So here is my question. What are the cases that are very difficult to >>> canonize a graph? >>> >>> As I recall, handling chirality and other non-local properties is >>> difficult. I have not worked on this problem. >>> >>> Cheers, >>> >>> Andrew >>> da...@dalkescientific.com >>> >>> >>> _______________________________________________ > Rdkit-discuss mailing list > Rdkit-discuss@lists.sourceforge.net > https://lists.sourceforge.net/lists/listinfo/rdkit-discuss >
_______________________________________________ Rdkit-discuss mailing list Rdkit-discuss@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/rdkit-discuss
