next up previous
Next: Bibliography Up: Data structures and algorithms Previous: Delaney symbols

Algorithms

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 si and one for the functions mi. 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.

Algorithm 7 (Ordered depth-first-traversal)  
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.

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:

Algorithm 8 (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.

Figure 9: A continuous deformation between tilings.
\includegraphics[width=1in]{c01}     \includegraphics[width=1in]{c02}     \includegraphics[width=1in]{c03}     \includegraphics[width=1in]{c04}


\includegraphics[width=1in]{c08}     \includegraphics[width=1in]{c07}     \includegraphics[width=1in]{c06}     \includegraphics[width=1in]{c05}


\includegraphics[width=1in]{c09}     \includegraphics[width=1in]{c10}     \includegraphics[width=1in]{c11}     \includegraphics[width=1in]{c12}

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 mi(C) = mi(D) for i $ \in$ {0,..., n - 1} and, moreover, for i $ \in$ {0,..., n}, si(C) and si(D) must be mapped to the common element si(C'). By performing a parallel traversal of the Delaney graph starting with the pair (C, D), we can partition C into equivalence classes C1,...,Ck 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.

Algorithm 9 (Checking and propagating equivalence)  
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 si maps the members of one class into the same ``neighbor''-class. Thus, the si and mi 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 C0 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 C0 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 C0 by the unique Delaney map which maps f (C) to the class of C.

Here is the code that constructs C0:

Algorithm 10 (Minimal image)  
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(n2d . 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 n2d . 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(n2).


next up previous
Next: Bibliography Up: Data structures and algorithms Previous: Delaney symbols


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