<p>@Rafal discussed the case of trees.  But what if you do not have trees? here is my two cents:</p>

<p><strong>Mathematica approach</strong> </p>

<p>Mathematica has a built-in predicate to check whether two graphs are isomorphic. You can try it for 30 days if you do not have it. </p>

<p><strong>Check nauty</strong> </p>

<p><a href="http://cs.anu.edu.au/~bdm/nauty/" rel="nofollow">nauty</a> is a solver where you can download it and test isomorphic.</p>

<p><strong>Detect true negatives in advance</strong></p>

<p>You can detect true negatives in advance by simply computing and comparing some numbers/sequences. This includes computing the degree sequence the vertex and edge set degrees. A pair of graphs passing this does not necessarily mean they are isomorphic but will reduce your space (maybe drastically !). </p>

<p>Most importantly, there is a <a href="http://arxiv.org/abs/1404.0818" rel="nofollow">recent</a> advancement of the problem stating that isomorphic tests are polynomial for graphs of bounded treewidth. Even if your graphs seems general, they may exhibit this property (or you can simply assume it in general). </p>
How to represent molecules and compare equality
<p>I've seen <a href="https://stackoverflow.com/questions/3550114/how-to-store-molecules-in-memory">this question about the representation of molecules in memory</a>, 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 <strong>how can we check equality of (acyclic) graphs?</strong> For now we'll ignore <a href="http://en.wikipedia.org/wiki/Stereoisomerism" rel="nofollow noreferrer">stereoisomers</a> and cyclical structures, such as the carbon ring in the example given in the first link.</p>

<p>Here's a more detailed description of my problem: For my <code>Molecule</code> class (as of now), I intend to have an array of <code>Atom</code>s and an array of <code>Bond</code>s. Each <code>Bond</code> will point to the two <code>Atom</code>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 <code>Atom</code>s in one molecule and try to find corresponding <code>Atom</code>s in the other molecule based on the <code>Bond</code>s that contain that <code>Atom</code>, but this is a rather naive approach, and the complexity seems pretty large (best guess is close to <em>O(n!)</em>. Yikes.). </p>

<p>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):</p>

<pre><code>    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
</code></pre>

<p>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 <a href="http://en.wikipedia.org/wiki/Structural_isomer" rel="nofollow noreferrer">structural isomers</a>. 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 <a href="http://en.wikipedia.org/wiki/Graph_canonization" rel="nofollow noreferrer">graph canonization</a>, but this seems like it could be NP-hard.</p>

<p><strong>Edit:</strong> Looking at the <a href="http://en.wikipedia.org/wiki/Graph_isomorphism" rel="nofollow noreferrer">Graph Isomorphism Problem Wikipedia Article</a>, 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 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.</p>