I originally asked this question at StackOverflow, and was suggested to bring it here.
I've seen this question about the representation of molecules in memory, and it makes sense to me (tl;dr represent it as a graph with atoms as nodes and bonds as edges). But now my question is this: how do we check and see if two molecules are equal? This could be generalized as how can we check equality of (acyclic) graphs? For now we'll ignore stereoisomers and cyclical structures, such as the carbon ring in the example given in the first link.
Here's a more detailed description of my problem: For my Molecule
class (as of now), I intend to have an array of Atom
s and an array of Bond
s. Each Bond
will point to the two Atom
s at either end, and will have a weight (i.e., the number of chemical bonds in that edge). In other words, this will most closely resemble an edge list graph. My first guess is to iterate over the Atom
s in one molecule and try to find corresponding Atom
s in the other molecule based on the Bond
s that contain that Atom
, but this is a rather naive approach, and the complexity seems pretty large (best guess is close to O(n!). Yikes.).
Regardless of complexity, this approach seems like it would work in most cases, however it seems to break down for some molecules. Take these for example (notice the different location of the OH group):
H H H OH H
| | | | |
H - C - C - C - C - C - H (2-Pentanol)
| | | | |
H H H H H
H H OH H H
| | | | |
H - C - C - C - C - C - H (3-Pentanol)
| | | | |
H H H H H
If we examine these molecules, for each atom in one molecule there is a unique same-element atom in the other molecule that has the same number and types of bonds, but these two molecules are clearly not the same, nor are they stereoisomers (which I'm not considering now). Instead they are structural isomers. Is there a way that we can check this relative structure as well? Would this be easier with an adjacency list instead of an edge list? Are there any graph equality algorithms out there that I should look into (ideally in Java)? I've looked a bit into graph canonization, but this seems like it could be NP-hard.
Looking at the Graph Isomorphism Problem Wikipedia Article, it seems as if graphs with bounded degree have polynomial time solutions to this problem. Furthermore, planar graphs also have polynomial solutions (i.e., the edges only intersect at their endpoints). It seems to me that (at least most) molecules satisfy both of these conditions, so what is this polynomial-time solution to this problem, or where can I find it? My Google searches are letting me down this time.