Information Technology Reference
In-Depth Information
nodes incident to the new edge is numbered. Note that this may already be the
case before the first edge in the volatile part is considered. In this case no edge
of the volatile part is processed in this step.
Finally we traverse the (remaining) volatile part edge by edge, each time
comparing the next edge to the new edge. If the new edge (w.r.t. source and -
possibly still to be assigned - destination index as well as edge attribute and
destination node attribute) is lexicographically smaller, it is inserted at the cur-
rent position in the volatile part and the rest of the volatile part is appended
(renumbering nodes as needed). Otherwise any unnumbered node incident to the
current volatile edge is numbered and the next volatile edge is considered. If all
volatile edges have been traversed and the new edge has not been inserted, it is
simply appended at the end of the code word.
To make the process clearer, we execute it step by step for the example shown
in Figure 11.8. The root node (here the sulfur atom) is, of course, always in
the fixed part. Hence it receives the initial node index, that is, 0. Since the
next edge is already in the volatile part, this finishes processing the fixed part.
Since by assigning the index 0 to the sulfur atom, one node incident to the new
edge (sulfur to oxygen) is already numbered, we have to start immediately to
compare edge descriptions. We compare two possibilities, namely appending the
description of the new edge, which assigns the node index 1 to the oxygen atom,
or appending the already present first perfect extension edge (sulfur to carbon),
which assigns the node index 1 to the carbon atom. This yields two possible
code word prefixes, namely S 0-O1 and S 0-C1 . Since the latter is smaller (as
C < O ), it is fixed (that is, the new edge is not yet inserted) and we move to
the next position. Here we compare the code word prefixes S 0-C1 0-O2 and
S 0-C1 1-N2 . Since the former is smaller (as O < N ), the position of the new
edge has been found and we fix the first prefix. In a final step, the remaining
perfect extension edge is appended, assigning the node index 3 to the nitrogen
atom. Note that the fixed part of the resulting code word now contains not only
the root atom, but two bonds: the first perfect extension bond, which is rendered
fixed by the fact that a non-perfect extension was inserted after it, and the new
bond, which is fixed, simply because it is not a perfect extension. The volatile
part contains only the second perfect extension (the bond from the carbon to
the nitrogen atom).
Note that generally, provided the new edge is not a perfect extension itself,
this edge is recorded for the restricted extensions as required by the “local” or
“simple” rules of maximum source extensions (that is, extensions preceding this
edge are ruled out). In other words, if the new edge is not a perfect extension, the
place at which it is inserted is the new end of the fixed part of the code word (as
described above). Note also that the resulting code word still has to be checked
for canonical form. Since the reorganization is strictly limited, the resulting code
word may not be canonical. For example, the new edge may actually have to be
inserted into the fixed part in order to make the code word canonical. In this case
the fragment must not be adapted, so that the code word becomes canonical,
but has to be pruned.
 
Search WWH ::




Custom Search