Enumeration of Polyhex Hydrocarbons to h = 21
Gilles Caporossi, Pierre Hansen · Journal of Chemical Information and Computer Sciences · 1998
An algorithm based on the boundary-edges code and the reverse search method is proposed for enumerating nonisomorphic planar simply connected polyhexes. These polyhexes are associated with vertices of a graph whose edges correspond to addition of a hexagon. A directed tree is defined on this graph. To this effect, a new father−son relationship is introduced: the father is the polyhex obtained when removing the hexagon associated with the first digit of the son's code. Then testing if a generated polyhex is a legitimate one in the enumeration can be done easily and efficiently. The resulting algorithm is used to enumerate polyhexes with h ≤ 21 hexagons, a set of over one trillion molecules, which is > 600 times larger than previously done.