In this section, I will present algorithms for finding subsymbols, for testing whether two Delaney symbols are isomorphic and for determining the minimal image of a Delaney symbol. Instead of pseudocode, I will use the programming language Python created by G. van Rossum (c.f. [Pyt00,Bea99]). This has the advantage that the code shown can actually be run, although it looks almost like pseudocode. I will explain the few pecularities of the language along the way.

The dimensions of Delaney symbols of interest are usually small, so we may treat the dimension as constant.

A natural way to represent a Delaney symbol would be two
two-dimensional
arrays, one for the functions *s*_{i} and one for the
functions *m*_{i}. In the
code presented, I use dictionaries, or associative arrays, for three
reasons: first, Python does not have built-in multi-dimensional arrays,
but
dictionaries indexed by pairs can be used to emulate those. Second, and
more important, using dictionaries would be more space-efficient for
small
subsymbols of large symbols. Third, we can use letters as names for the
elements, which is convenient for presenting small examples. In actual
code, either two-dimensional arrays or arrays of arrays would be used,
so
we will assume constant access time.

A Delaney symbol will be represented by four entities: its
dimension, a
list of elements and two dictionaries `s` and `m`. As
an example,
the Delaney symbol for the rectangle tiling shown in
Figure 8 would be
created as follows:

dimension = 2

elements = [ 'A', 'B' ]

s = {} # this creates an empty dictionary

s[0, 'A'] = 'A'; s[0, 'B'] = 'B'

s[1, 'A'] = 'B'; s[1, 'B'] = 'A'

s[2, 'A'] = 'A'; s[2, 'B'] = 'B'

m = {}

m[0, 'A'] = m[0, 'B'] = 4

m[1, 'A'] = m[1, 'B'] = 4

Please note that additional information as, for example, vertex coordinates, can be added easily. I will elaborate on extensions of Delaney symbols to present actual, i.e., geometrically realized, tilings in a forthcoming paper.

The following function checks conditions (DS1) through (DS4) as of
Definition 2 in order,
raising an exception if a condition
is violated.
^{2}

def check_integrity(dimension, elements, s, m):

for i in range(dimension+1):

for C in elements:

if s[i,s[i,C]] != C:

raise DSymbolError("condition (DS1) violated")

for i in range(dimension-1):

for j in range(i+2, dimension+1):

for C in elements:

if s[i,s[j,C]] != s[j,s[i,C]]:

raise DSymbolError("condition (DS2) violated")

for i in range(dimension):

for C in elements:

if not (m[i,C] == m[i,s[i,C]] == m[i,s[i+1,C]]):

raise DSymbolError("condition (DS3) violated")

for i in range(dimension):

for C in elements:

T = C

for k in range(m[i,C]):

T = s[i, s[i+1, T]]

if T != C:

raise DSymbolError("condition (DS4) violated")

To check for condition (DS0), any method to explore connected components of a graph can be used. The following method proves useful for this and several other purposes.

**Input**-
- A dictionary
`s`, representing a Delaney graph. - A list
`indices`of valid indices, i.e., edge labels, for`s`. - A list
`seeds`of nodes of the Delaney graph.

- A dictionary
**Output**- A spanning forest of the graph obtained by removing all edges
with labels not in
`indices`. This forest is represented as a list of entries of the form (*i*,*C*), where*C*is a node and*i*is either the special object`None`, in which case*C*is the root of a new component, or else an element of`indices`, in which case it is the label of an edge from*C*towards the root of the current component. **Method**^{3}def ordered_depth_first_traversal(s, indices, seeds):

seen = {}

result = []

for seed in seeds:

if not seen.has_key(seed):

result.append((None, seed))

seen[seed] = 1

stack = [seed]

while stack:

C = stack[-1]

del stack[-1]

for i in indices:

Ci = s[i, C]

if not seen.has_key(Ci):

result.append((i, Ci))

seen[Ci] = 1

stack.append(Ci)

return result

For a Delaney symbol of size *n* and *m* indices given,
Algorithm 7 obviously has
time complexity *n***m* and
space complexity *n*. For appropriate inputs, its output can be
analyzed in
linear time to check connectivity or extract connected components and
subsymbols.

The ordered depth-first-traversal can be used to construct a
canonical
labelling for Delaney symbols. First, we define a function to compare
two
labelled symbols of the same size and dimension, represented by `sa`
and `ma` and by `sb` and `mb`, respectively.
For simplicity, we
assume that nodes are labelled consecutively starting at 0. The
function
returns -1 if the first symbol is considered ``better'', 1 if it is
considered ``worse'' and 0 if both symbols are equal.

def compare(dimension, size, sa, ma, sb, mb):

for i in range(dimension+1):

for C in range(size):

if sa[i, C] < sb[i, C]:

return -1

elif sa[i, C] > sb[i, C]:

return 1

for i in range(dimension):

for C in range(size):

if ma[i, C] < mb[i, C]:

return -1

elif ma[i, C] > mb[i, C]:

return 1

return 0

The particular choice of a comparison function is irrelevant here as long as it is used consistently. Following is an algorithm to construct a canonical form:

**Input**- A Delaney symbol.
**Output**- A Delaney symbol in canonical form, with nodes labelled consecutively from 0. The algorithm produces identical output for isomorphic Delaney symbols.
**Method**-
def canonical_form(dimension, elements, s, m):

best_s = best_m = None

indices = range(dimension + 1)

n = len(elements)

for seed in elements:

edges = ordered_depth_first_traversal(s, indices, seed)

old2new = {}

new2old = {}

for k in range(n):

(i, C) = edges[k]

old2new[C] = k

new2old[k] = C

s_new = {}

m_new = {}

for C_new in range(n):

C_old = new2old[C_new]

for i in range(dimension + 1):

s_new[i, C_new] = old2new[s[i, C_old]]

for i in range(dimension):

m_new[i, C_new] = m[i, C_old]

if (best_s is None or

compare(dimension, n, s_new, m_new, best_s, best_m) < 0):

best_s = s_new

best_m = m_new

return (dimension, range(n), best_s, best_m)

Clearly, Algorithm 8
has quadratic time and linear
space complexity. For each node, the symbol is relabelled in ordered
depth-first-order starting at that node. Of all these numberings, the
one
leading to the best labelled symbol according to the `compare`
function is chosen. Because all possible starting nodes are used, the
outcome does not depend on the inital labelling and the canonical form
is
the same for isomorphic symbols.

A straightforward improvement to Algorithm 8 as presented is to merge the comparison into the traversal and stop the traversal as soon as the new labelled graph is determined to be worse than the best seen so far. It is easy to see that the worst case running time of this version is still quadratic. An average case analysis has not been attempted yet. It is conceivable that the average case behaviour will depend significantly on certain properties of the Delaney symbols under consideration, i.e., on the particular application.

Two symbols in canonical form can be tested for isomorphism in
linear time
using the `compare` function. As an example, consider the
tilings shown
in Figure 1. The problem of
deciding on their equivalence
is now easily solved by constructing the respective Delaney symbols,
using
Algorithm 8 to compute
their respective canonical
forms and testing for equality. It turns out that, in fact, those two
tilings are equivalent. Moreover, by a slight extension of
Algorithm 8, the
chambers receiving the label 0 in
the canonical form can be identified in the original symbols and thus
in
the tilings, which may aid in the construction of an actual
homeomorphism
or even, as shown in Figure 9,
a continuous
deformation between these tilings.

Finally, consider the problem of finding the minimal image of a given
*n*- dimensional Delaney symbol **C**.
Let *C* and *D* be two arbitrary
elements of **C**. Assume that there
is some unknown Delaney map *f* which
maps *C* and *D* to a common element *C'*. Then, by
the Definitions, we
must have *m*_{i}(*C*)
= *m*_{i}(*D*) for *i*
{0,..., *n* - 1} and, moreover, for
*i* {0,...,
*n*}, *s*_{i}(*C*) and *s*_{i}(*D*)
must be mapped to the common
element *s*_{i}(*C'*). By performing a parallel
traversal of the Delaney graph
starting with the pair (*C*, *D*), we can partition **C**
into equivalence
classes **C**^{1},...,**C**^{k}
such that two elements in the same class must
have the same image under *f*. Moreover, if a contradiction
appears during
the traversal, we know that there is no such Delaney map.

The following algorithm does the trick. To keep track of equivalence
classes, it uses a so-called *union-find* or *partition*
data
structure (cf. [Sed88]). We
represent this as an instance `p` of a class `Partition`
with two methods `union` and `find`. The `find`
method returns a representative for the equivalence
class its argument is in. Initially, every item is in a class of its
own. The `union` method unites the classes of its two argument.
In the
code, a third method `copy` is used, which produces a copy of
the given
structure. This is necessary because in Python, assignment of complex
objects produces a new reference, but does not copy the data. Partition
data structures are a well-known subject, so the code for the class `Partition`
is not shown. Note however, that it can be implemented as to
require space *O*(*n*) and accumulated running time *O*(*m*^{
. }*a*(*n*)) for any
sequence of *m* > *n* `find` or `union`
operations on a total set of
size *n*, where *a* is the inverse Ackermann function.

**Input**- A Delaney symbol, two elements
*C*and*D*and a partition. **Output**- Nothing (
`None`), if*C*and*D*can not be set equivalent, else the partition resulting from setting them equivalent and drawing all consequences. **Method**-
def try_to_set_equivalent(dimension, elements, s, m, C, D, p):

for i in range(dimension):

if m[i,C] != m[i,D]:

return None

if p.find(C) == p.find(D):

return p

p = p.copy()

p.union(C, D)

stack = [(C, D)]

while stack:

(C, D) = stack[-1]

del stack[-1]

for i in range(dimension+1):

Ci = s[i,C]

Di = s[i,D]

for j in range(dimension):

if m[j,Ci] != m[j,Di]:

return None

A = p.find(Ci)

B = p.find(Di)

if A != B:

p.union(A, B)

stack.append((Ci, Di))

return p

If Algorithm 9 returns a
new partition, all the
*m*-functions are constant on classes and each *s*_{i}
maps the members of
one class into the same ``neighbor''-class. Thus, the *s*_{i}
and *m*_{i} can
be defined classwise and the set of classes forms a Delaney symbol.

By calling Algorithm 9
with *C* staying the same and *D*
ranging through the elements of **C**,
every element that can have the same
image as *C* at all will eventually be found. As above, the final
collection of equivalence classes will form a Delaney symbol **C**_{0}
which will necessarily be minimal. To see this, note that a Delaney map
is
one-to-one whenever there is an element in its image with a unique
preimage. Thus, if **C**_{0}
were not minimal, it would have been possible
to unite the class of *C* with some other class. Moreover, every
image of
**C** by a Delaney map *f* must
map onto **C**_{0} by the
unique Delaney
map which maps *f* (*C*) to the class of *C*.

Here is the code that constructs **C**_{0}:

**Input**- A Delaney symbol.
**Output**- The unique minimal image of the given Delaney symbol by a Delaney map.
**Method**-
def minimal(dimension, elements, s, m):

p = Partition()

C = elements[0]

for D in elements:

q = try_to_set_equivalent(dimension, elements, s, m, C, D, p)

if q is not None:

p = q

old2new = {}

new2old = {}

k = 0

for C in elements:

D = p.find(C)

if not old2new.has_key(D):

old2new[D] = k

new2old[k] = D

k = k + 1

old2new[C] = old2new[D]

s_new = {}

m_new = {}

for C_new in range(k):

C_old = new2old[C_new]

for i in range(dimension + 1):

s_new[i, C_new] = old2new[s[i, C_old]]

for i in range(dimension):

m_new[i, C_new] = m[i, C_old]

return (dimension, range(k), s_new, m_new)

Clearly, Algorithm 9
performs at most *n* - 1 `union`
operations for a *d*-dimensional Delaney symbol of size *n*.
A pair of
elements is pushed onto the stack only following a union operation, so
the
total number of find operations is *O*(*nd* ). The copy
operation clearly
takes time *O*(*n*), while all other operations run in time *O*(*nd*
), thus the
total running time of Algorithm 9
is
*O*(*nd*^{ . }*a*(*n*)).

As Algorithm 9 is
called *n* times in
Algorithm 10 and everything
else there runs in time *O*(*nd* ),
we obtain a total running time of *O*(*n*^{2}*d*^{
. }*a*(*n*)). Thus, for all
practical purposes, we may assume a quadratic time bound for
Algorithm 10.

A slightly modified version of the first loop in
Algorithm 10 can be used to
test for minimality of a given
symbol without actually constructing a minimal image. In that case, the
algorithm terminates and returns `0` for ``false'' as soon as
Algorithm 9 succeeds in
constructing a new
partition. By the simple argument given above, we establish the same
complexity bound of *n*^{2}*d*^{
. }*a*(*n*).

It would be interesting to know whether the construction of
canonical forms
or minimal images or the test for minimality can be done in worst case
running time less than *O*(*n*^{2}).

Hosted by:

Author: Olaf Delgado-Friedrichs (odf at users.sourceforge.net) Date: July 28, 2005