How to represent molecules and compare equality

Question

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 Atoms and an array of Bonds. Each Bond will point to the two Atoms 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 Atoms in one molecule and try to find corresponding Atoms in the other molecule based on the Bonds 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.

Answer 1

I had to work on graph isomorphisms at one point for a parallel computing project involving a computational chemistry package, and from what I remember, I basically just used off-the-shelf software. What you're looking for is a graph isomorphism package that respects node/vertex labeling (i.e., nodes are labeled as types of atoms, e.g., carbon, hydrogen, oxygen) and edge/arc labeling (i.e., edges are labeled as a type of bond, e.g., single, double, triple). I forget exactly which software package I used, but I think nauty was one of the packages I looked at, and there are a couple others out there.

Answer 2

There are some links related to the bounded-degree graph isomorphism algorithm in the thread "Gentle introduction to graph isomorphism for bounded valance graphs" on the cstheory site. There, Joshua Grochow points out that the algorithm is closely tied to permutation groups and can be hard to understand if one doesn't have a strong background in group theory.

However, since you're willing to ignore graphs with cycles, then you're just working with (unrooted) trees, and testing for isomorphism between those should be much easier. Wikipedia cites P. J. Kelly's "A congruence theorem for trees" (1957), which I don't understand, and another algorithm is given in Marthe Bonamy's "A small report on graph and tree isomorphism" (2010).