(a) Non-isomorphic canonical tree generation:
Beyer and Hedetniemi [16] have proposed an iterative algorithm to reverse lexicographically generate non-isomorphic canonical trees for a given number of vertices. The algorithm achieves this transformation through a successor function
defined below.
Let L T
ð Þ ¼ l 1 l 2 . . .l n
½
be a level sequence containing an element greater than 2.
Let p be the rightmost position of such an element, i.e. p ¼ maxfi : l i [ 2g. Let
q be defined as the rightmost position preceding p such that l q ¼ l p À 1, i.e.
q ¼ maxfi : i\p; l i ¼ l p À 1g. Hence, the vertex corresponding to position q is the
parent of vertex corresponding to position p. Then the successor of L T
ð Þ, i.e.
succ L T
ð Þ
ð
Þ¼ s 1 s 2 . . .s n
½
is defined such that:
(i) s i ¼ l i for 1 i\p
(ii) s i ¼ s iÀ pÀq
ð
Þ for p i n:
The algorithm can be used successively generating all the non-isomorphic
canonical level representation of trees from a provided starting level sequence to the
last possible reverse lexicographic sequence, i.e. 1; 2; 2. . .2
|fflfflffl ffl{zfflfflffl ffl}
nÀ1 times
2
4
3
5 . If no starting level
sequence can be provided, the algorithm can start with the lexicographically largest
sequence 1; 2; 3. . .n
½
.
The trees generated by the aforementioned algorithm can in general have any
number of children for any parent vertex. In context of chemical structures of
carbon atoms, only those trees are being filtered and kept where the root has at most
four children and the rest of the vertices have at most three children. This restriction
can later be further refined for hetero-atoms in accordance with their valency.
(b) Cycle introduction by addition of edges:
The generated rooted trees are graphical models of acyclic compound structures.
Cycles can be introduced by adding edges between any two vertices, say i and j,
such that:
parent i
½ 6 ¼ j and parent j
½ 6 ¼ i
The size or the number of sides in the cycle so introduced can be obtained by the
following relation:
num cycle sides ¼ level i
½ þ level j
½
À 2 Ã level lowest common anscester i; j
ð Þ
½
þ 1
In general, cycles of size 3 onwards will be possible. For more than one cycles to be
introduced, a combination of these identified edge introductions can be simultaneously carried out.
82
Md.I. H. Rizvi et al.
Beyer and Hedetniemi [16] have proposed an iterative algorithm to reverse lexicographically generate non-isomorphic canonical trees for a given number of vertices. The algorithm achieves this transformation through a successor function
defined below.
Let L T
ð Þ ¼ l 1 l 2 . . .l n
½
be a level sequence containing an element greater than 2.
Let p be the rightmost position of such an element, i.e. p ¼ maxfi : l i [ 2g. Let
q be defined as the rightmost position preceding p such that l q ¼ l p À 1, i.e.
q ¼ maxfi : i\p; l i ¼ l p À 1g. Hence, the vertex corresponding to position q is the
parent of vertex corresponding to position p. Then the successor of L T
ð Þ, i.e.
succ L T
ð Þ
ð
Þ¼ s 1 s 2 . . .s n
½
is defined such that:
(i) s i ¼ l i for 1 i\p
(ii) s i ¼ s iÀ pÀq
ð
Þ for p i n:
The algorithm can be used successively generating all the non-isomorphic
canonical level representation of trees from a provided starting level sequence to the
last possible reverse lexicographic sequence, i.e. 1; 2; 2. . .2
|fflfflffl ffl{zfflfflffl ffl}
nÀ1 times
2
4
3
5 . If no starting level
sequence can be provided, the algorithm can start with the lexicographically largest
sequence 1; 2; 3. . .n
½
.
The trees generated by the aforementioned algorithm can in general have any
number of children for any parent vertex. In context of chemical structures of
carbon atoms, only those trees are being filtered and kept where the root has at most
four children and the rest of the vertices have at most three children. This restriction
can later be further refined for hetero-atoms in accordance with their valency.
(b) Cycle introduction by addition of edges:
The generated rooted trees are graphical models of acyclic compound structures.
Cycles can be introduced by adding edges between any two vertices, say i and j,
such that:
parent i
½ 6 ¼ j and parent j
½ 6 ¼ i
The size or the number of sides in the cycle so introduced can be obtained by the
following relation:
num cycle sides ¼ level i
½ þ level j
½
À 2 Ã level lowest common anscester i; j
ð Þ
½
þ 1
In general, cycles of size 3 onwards will be possible. For more than one cycles to be
introduced, a combination of these identified edge introductions can be simultaneously carried out.
82
Md.I. H. Rizvi et al.