An Effective Topological Symmetry Perception and Unique Numbering Algorithm
详细信息 查看全文
- 作者：Zheng Ouyang ; Shengang Yuan ; Josef Brandt ; and Chongzhi Zheng
- 刊名：Journal of Chemical Information and Modeling
- 出版年：1999
- 出版时间：March 1999
- 年：1999
- 卷：39
- 期：2
- 页码：299 - 303
- 全文大小：104K
- 年卷期：v.39,no.2(March 1999)
- ISSN：1549-960X
文摘
Determination of equivalence classes of atoms in molecules and the unique numbering for the moleculargraphs are of major interest for many structure processing tasks and many programs have been reported forthis purpose. Most of them were based on the use of graph invariants, but such methods reportedly failedto give correct partitioning for certain structures and the only theoretically rigorous method is based onatom-by-atom matchings1 which was considered to be computationally impractical. In order to avoid thefailures of partitioning and the time-consuming atom-by-atom matching, on the basis of a profound analysison the mechanism of Morgan algorithm, this work proposed two improvements for the original Morganalgorithm. The first improvement is to avoid the oscillatory behavior of Morgan algorithm. The secondimprovement referred to as single-vertex Morgan algorithm, is to decompose the Morgan algorithm intosingle-vertex processing. By incorporating these improvements, an effective topological symmetry perceptionand unique numbering algorithms were devised. The high performance of these algorithms is demonstratedwith some graphs that are difficult to partition.