algorithm - 如何表示分子和比较相等性

Question

我看过 this question about the representation of molecules in memory ，这对我来说很有意义(tl;dr 将其表示为以原子为节点，以键为边的图)。但现在我的问题是:我们如何检查两个分子是否相等？这可以概括为我们如何检查(非循环)图的相等性？现在我们将忽略 stereoisomers和循环结构，例如第一个链接中给出的示例中的碳环。

下面是我的问题的更详细描述:对于我的 Molecule类(截至目前)，我打算有一个 Atom 的数组s 和一组 Bond秒。每个Bond将指向两个 Atom s 在两端，并且将具有权重(即该边缘的化学键数)。换句话说，这将最类似于边列表图。我的第一个猜测是迭代 Atom s 在一个分子中并尝试找到相应的 Atom s 在基于 Bond 的其他分子中包含 Atom 的 s ，但这是一种相当幼稚的方法，而且复杂性似乎相当大(最佳猜测接近 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

如果我们检查这些分子，对于一个分子中的每个原子，另一个分子中有一个独特的同元素原子，它具有相同数量和类型的键，但这两个分子显然不相同，它们也不相同立体异构体(我现在不考虑)。相反，它们是 structural isomers .有没有办法我们也可以检查这个相对结构？使用邻接列表而不是边缘列表会更容易吗？是否有任何我应该研究的图形相等算法(最好是在 Java 中)？我调查了一下 graph canonization ，但这似乎是 NP 难的。

编辑查看Graph Isomorphism Problem Wikipedia Article , 似乎有界度的图有这个问题的多项式时间解。此外，平面图也有多项式解(即边仅在端点处相交)。在我看来，分子同时满足这两个条件，那么这个问题的多项式时间解是什么，或者我在哪里可以找到它？这次我的 Google 搜索让我失望了。

Answer 1

如果图是无环的，那么它就是一个树同构问题，它有一个非常简单的解决方案。

现在让我们假设所有内部节点都是碳节点并且所有边都相同(稍后介绍如何放宽此限制。)

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

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

分别是[1,1,1,1]和[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

“假”可以是 511，这样我们就知道它不会与任何现有原子冲突。因此，整个分子将是 [[1,1,1],[1,511]]。

所以算法是:

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