如何表示分子并比较相等性

Question

我看到了有关分子在内存中的表示的问题，并且这对我来说很有意义（简而言之，将其表示为以原子为节点、化学键为边的图形）。但现在我的问题是：我们如何检查并确定两个分子是否相等？这可以概括为我们如何检查（无环）图形的相等性？暂时我们将忽略立体异构体和环状结构，例如第一个链接中给出的碳环。

这是我问题的更详细描述：对于我的Molecule类（目前而言），我打算拥有一个Atom数组和一个Bond数组。每个Bond将指向两端的两个Atom，并且会有一个权重（即该边中化学键的数量）。换句话说，这最接近于一个边缘列表图。我的第一个猜测是在一个分子中迭代Atom，并尝试基于包含该Atom的Bond找到另一个分子中相应的Atom，但这是一种相当幼稚的方法，复杂度似乎非常大（最好的猜测接近于O(n!)。天啊）。无论复杂度如何，这种方法似乎在大多数情况下都有效，但对于某些分子来说似乎不起作用。以这些为例（注意OH基团的不同位置）：

    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

如果我们检查这些分子，对于一个分子中的每个原子，在另一个分子中都有一个独特的同种元素原子具有相同数量和类型的键，但是这两个分子显然不同，也不是立体异构体（我现在没有考虑这个）。相反，它们是结构异构体。有没有一种方法可以检查这种相对结构？使用邻接列表而不是边缘列表会更容易吗？是否有任何图形等价算法需要研究（最好是Java）？我稍微了解了一下图形规范化，但这似乎可能是NP难问题。

编辑：查看图同构问题维基百科文章，似乎具有有界度数的图形对于该问题有多项式时间解决方案。此外，平面图也有多项式解决方案（即，边仅在其端点交汇）。对我来说，分子满足这两个条件，那么这个问题的多项式时间解决方案在哪里可以找到？我的Google搜索没有结果。

- wlyles

---

http://en.m.wikipedia.org/wiki/Graph_isomorphism_problem - n. m.

@n.m. 刚刚看了一下，似乎这个问题通常并不被认为是NP完全的。然而，有界度数和平面图被认为有多项式解决方案，而且在我看来，分子都是这样的。但是，除非购买其中一个参考教材，否则我似乎找不到这些解决方案，这似乎有点过分。 - wlyles

分子是有界度数的，但不一定是平面的（http://www.sciencedirect.com/science/article/pii/0040403981800779，尽管大多数“正常”的分子是平面的）。很抱歉我不知道有没有针对有界度数图的多项式算法可供免费使用。 - n. m.

你可能会在http://scicomp.stackexchange.com上获得（更好的）答案。 - High Performance Mark

@n.m.：我认为你太过专业化了。在Wikipedia的“图同构”页面中，按照引文和来源，我找到了这篇文章，虽然不确定它有多大用处，但PDF文件可供下载。http://www.sciencedirect.com/science/article/pii/0022000082900095 - Nuclearman

啊，刚注意到无环部分...为什么？许多分子并不完全是无环的。 - n. m.

Answer 1

如果图是无环的，则它是一个树同构问题，有一个非常直接的解决方案。

现在假设所有内部节点都是碳，并且所有边都相同（稍后会讲到如何放宽此限制）。

将叶节点表示为数字 - 例如它们的原子序数。将高度为1的树表示为其叶节点的排序列表，因此：

    H             Cl
    |             |
H - C - H  and Cl-C-Cl
    |             |
    H             H

[1, 1, ..., 1, 1] and [1, 17, ..., 17, 17] 分别表示两个分子。很明显只有当这两个排序后的列表相同时，两个分子才是同构的。

这可以推广到更高层次的树 - 把高度为 n 的树表示为其子树的表示的列表，并按字典序排序，则：

    Cl H            H   H
    |  |            |   |
H - C -C-Cl and Cl- C - C - Cl
    |  |            |   |
    Cl H            H  Cl

它们都是[[1,1,17],[1,17,17]]。当且仅当两个树的表示相同时，这两个树是同构的。

注意：通常树同构算法适用于有根树。在这里，我们只是从叶子节点递归地向图形中心前进，这有时会留下两个“根”。

    H   H   Cl  
    |   |   |   
H - C - C - C - H
    |   |   |   
    H   H   H   

这里，左侧的C是[1,1,1]，右侧的C是[1,1,17]。中间的C（作为根）有这两个列表和两个叶子。按字典序排序后是[1,1,[1,1,1],[1,1,17]]。

现在对于表示不是C的内部节点 - 你可以通过附加一个特殊数字的虚假叶子来模拟它们，因此

    H   
    |   
H - C - O - H 
    |   
    H  

可以编码为

    H   
    |   
H - C - C - H 
    |   |
    H   Fake

假设"Fake"的值为511，这样我们就能确定它不会与任何现有原子冲突。因此，整个分子将是[[1,1,1],[1,511]]。

所以算法如下：

1. 将两个分子转换为递归字典序排序的列表形式。
2. 检查表示是否相等。

- Rafał Dowgird

Answer 2

@Rafal讨论了树的情况。但是如果你没有树怎么办？这是我的两分钱：

Mathematica方法

Mathematica有一个内置谓词，用于检查两个图是否同构。如果您没有它，可以尝试30天。

检查nauty

nauty是一个求解器，您可以下载并测试同构。

提前检测真负面影响

您可以通过简单计算和比较一些数字/序列来提前检测真负面影响。这包括计算顶点和边集度数的度数序列。通过此方式通过的一对图形不一定意味着它们是同构的，但会减少您的空间（也许是极大的！）。

最重要的是，最近有进展表明，有界树宽的图形同构测试是多项式的。即使您的图形似乎很一般，它们也可能具有此属性（或者您可以在一般情况下假设它们具有此属性）。

- Xline