论文部分内容阅读
本文针对分子二维子结构检索问题,比较分析图同构算法中具有代表性的VF2法和GMA法。VF2法的数据结构精巧,能有效降低内存开销,但其在图匹配时没有保存提问结构的偏序,造成大量重复计算,影响匹配效率。GMA法则利用偏序的不变性,预先计算并保存偏序,进而指导图匹配过程。本文将GMA法的偏序行走策略应用于VF2法,保留VF2法的遍历规则和数据结构,用标准C++语言改进的结构检索算法能提供正确的检索结果,效率更高。本文还通过实例说明了VF2法和GMA法各自偏序的计算过程,指出2种算法的图遍历规则的差异。
In this paper, aiming at the problem of two-dimensional molecular substructure search, we compare the representative VF2 and GMA methods in graph isomorphism algorithm. The data structure of the VF2 method is compact, which can effectively reduce the memory overhead. However, the VF2 method does not save the partial ordering of the question structure when the graph is matched, resulting in a large amount of double counting and affecting the matching efficiency. The GMA law makes use of the invariance of partial order, precomputes and preserves the partial order, and then guides the map matching process. This paper applies partial order strategy of GMA method to VF2 method, preserves the traversal rules and data structure of VF2 method. The improved structure retrieval algorithm using standard C ++ language can provide the correct retrieval result with higher efficiency. This paper also illustrates the calculation process of partial order of VF2 method and GMA method by examples and points out the difference of the graph traversal rules of the two algorithms.