geometry_tools.automata.coxeter_automaton

  1"""coxeter_automaton
  2
  3Code to generate a finite-state automaton accepting geodesic words in
  4Coxeter groups.
  5
  6Code originally by Florian Stecker, with some small adaptations by
  7Teddy Weisman
  8
  9"""
 10
 11import numpy as np
 12import math
 13from copy import copy
 14from collections import deque, defaultdict
 15from . import fsa
 16
 17class Root:
 18        def __init__(self, id, rank, depth = 0, v = None, neighbors = None):
 19                self.id = id
 20                self.rank = rank
 21                self.depth = depth
 22                if v:
 23                        self.v = v
 24                else:
 25                        self.v = [0] * rank
 26                if neighbors:
 27                        self.neighbors = neighbors
 28                else:
 29                        self.neighbors = [None] * rank
 30
 31        def __copy__(self):
 32                return Root(self.id, self.rank, self.depth, self.v.copy(), self.neighbors.copy())
 33
 34class Groupelement:
 35        def __init__(self, id, rank, word):
 36                self.id = id
 37                self.rank = rank
 38                self.word = word
 39                self.length = len(word)
 40                self.left = [None]*rank
 41                self.right = [None]*rank
 42                self.node = None
 43                self.lex_node = None
 44                self.inverse = None
 45
 46# compute <alpha_k, beta> where alpha_k is one of the simple roots and beta any root
 47def form_gen_root(form, k, root):
 48        rank = len(form)
 49        return sum([root[i] * form[i][k] for i in range(rank)])
 50
 51# compute beta - 2<alpha_k, beta>alpha_k, i.e. the reflection of beta along alpha_k
 52def apply_gen_to_root(form, k, root):
 53        root[k] -= 2*form_gen_root(form, k, root)
 54
 55# find a sequence of generators to apply to obtain a negative root, from left to right
 56# "startwith" argument can be used to force the first entry
 57def find_word_to_negative(form, root_, startwith = None):
 58        rank = len(form)
 59        root = root_.copy()
 60        word = []
 61        while not next(filter(lambda x: x < -1e-6, root), None): # while root has no negative entry
 62                for k in range(rank):
 63                        if startwith and k != startwith:
 64                                continue
 65                        # avoiding 0 might be a problem for reducible groups?
 66                        f = form_gen_root(form, k, root)
 67                        if f > 1e-6:
 68                                apply_gen_to_root(form, k, root)
 69                                word.append(k)
 70                                break
 71                startwith = None
 72        return word
 73
 74# use find_word_to_negative() to find the root, if we already have it
 75def find_root_from_vector(form, roots, vector):
 76        rank = len(form)
 77        for k in range(rank):
 78                word = find_word_to_negative(form, vector, startwith = k)
 79
 80                if not word:
 81                        continue
 82
 83                rootobj = roots[word.pop()]
 84
 85                while len(word) > 0:
 86                        letter = word.pop()
 87                        if not rootobj.neighbors[letter]:
 88                                rootobj = None
 89                                break
 90                        else:
 91                                rootobj = rootobj.neighbors[letter]
 92
 93                if rootobj:
 94                        return rootobj
 95        return None
 96
 97def find_small_roots(form):
 98        rank = len(form)
 99        small_roots = []
100
101        # the simple roots are just the standard basis vectors
102        for i in range(rank):
103                r = Root(i, rank)
104                r.v[i] = 1
105                r.depth = 1
106                small_roots.append(r)
107
108        # find the other small roots by applying generators to all existing roots
109        # and using find_root_from_vector() to see if we already have it
110        # then add it if it is a small root = was obtained via a short edge (form between -1 and 0)
111        i = 0
112        while i < len(small_roots):
113                root = small_roots[i]
114                for k in range(rank):
115                        newroot = root.v.copy()
116                        apply_gen_to_root(form, k, newroot)
117
118                        rootobj = find_root_from_vector(form, small_roots, newroot)
119
120                        if rootobj:
121                                root.neighbors[k] = rootobj
122                        else:
123                                f = form_gen_root(form, k, root.v)
124                                if f > -1 + 1e-6 and f < -1e-6:      # root is new and is a small root
125                                        rootobj = Root(len(small_roots), rank, root.depth+1, newroot)
126                                        small_roots.append(rootobj)
127                                        root.neighbors[k] = rootobj
128                i = i+1
129        return small_roots
130
131
132def apply_gen_to_node(small_roots, k, node, position, lex_reduced = False):
133        # if we want to get the lex reduced langauge
134        if lex_reduced:
135                for j in range(k):
136                        if small_roots[j].neighbors[k] and position == small_roots[j].neighbors[k].id:
137                                return 1
138
139        if position == k:
140                return 1
141        elif small_roots[position].neighbors[k]:
142                swappos = small_roots[position].neighbors[k].id
143                return node[swappos]
144        else:
145                return 0
146
147def generate_automaton(small_roots, lex_reduced = False):
148        nroots = len(small_roots)
149        rank = small_roots[0].rank
150        start = tuple([0]*nroots)
151        todo = deque([start])
152        nodes = {start: 0}
153        levels = {start: 0}
154        edges = []
155        id = 1
156
157        while todo:
158                node = todo.pop()
159                for k in range(rank):
160                        if node[k] == 1:
161                                continue
162                        newnode = tuple(
163                                apply_gen_to_node(small_roots, k, node, i, lex_reduced = lex_reduced)
164                                for i in range(nroots))
165                        if not newnode in nodes:
166                                nodes[newnode] = id
167                                levels[newnode] = levels[node]+1
168                                todo.appendleft(newnode)
169                                id += 1
170                        edges.append((nodes[node], nodes[newnode], k))
171
172        graph = defaultdict(dict)
173        for (fr,to,gen) in edges:
174                graph[fr][gen] = to
175
176        return fsa.FSA(dict(graph), start_vertices=[0])
177
178
179def enumerate_group(graph, graph_lex, max_len):
180        rank = len(graph[0])
181        group = [Groupelement(0, rank, tuple())]
182        group[0].inverse = group[0]
183        group[0].node = group[0].lex_node = 0
184
185        i = 0
186        size = 1
187        while True:
188                current = group[i]
189                i+=1
190
191                # break if current has the max length we have, as that's when we would start adding elements 1 longer
192                if current.length >= max_len:
193                        break
194
195                for gen, new_lex_node in filter(lambda x: x[1], enumerate(graph_lex[current.lex_node])):
196                        new_element = Groupelement(size, rank, current.word + (gen,))
197                        new_element.lex_node = new_lex_node
198                        new_element.node = graph[current.node][gen]
199                        group.append(new_element)
200                        size += 1
201
202                        # w = w_1 t, w s = w_1
203                        # right multiplication, if it decreases length
204                        for k in range(rank):
205                                if not graph[new_element.node][k]:
206                                        word = list(new_element.word)
207                                        longer_suffix = group[0]
208                                        while len(word) > 0:
209                                                letter = word.pop()
210                                                shorter_suffix = longer_suffix
211                                                longer_suffix = shorter_suffix.left[letter]
212
213                                                # w = w_1 t w_2, w_2 s_k = t w_2
214                                                # in the case word = [] longer_suffix could be None
215                                                if len(word) == 0 or shorter_suffix.right[k] == longer_suffix:
216                                                        # finish word
217                                                        while len(word) > 0:
218                                                                shorter_suffix = shorter_suffix.left[word.pop()]
219                                                        new_element.right[k] = shorter_suffix
220                                                        shorter_suffix.right[k] = new_element
221
222                        # find inverse and left multiply
223                        inverse = group[0]
224                        word = list(new_element.word)
225                        while len(word) > 0:
226                                inverse = inverse.right[word.pop()]
227                                if not inverse:
228                                        break
229                        if inverse:
230                                new_element.inverse = inverse
231                                inverse.inverse = new_element
232                                for k in range(rank):
233                                        if inverse.right[k]:
234                                                other = inverse.right[k].inverse
235                                                new_element.left[k] = other
236                                                other.left[k] = new_element
237                                        if new_element.right[k]:
238                                                other = new_element.right[k].inverse
239                                                inverse.left[k] = other
240                                                other.left[k] = inverse
241        return group
242
243def word(w):
244        return ''.join([chr(ord('a')+x) for x in w])
245
246def generate_automaton_coxeter_matrix(coxeter_matrix, lex_reduced = False):
247        form = [[-math.cos(math.pi/m) if m > 0 else -1 for m in row] for row in coxeter_matrix]
248        rank = len(coxeter_matrix)
249        small_roots = find_small_roots(form)
250        return generate_automaton(small_roots, lex_reduced)
251
252def even_graph(graph):
253        rank = len(graph[0])
254        result = []
255        for node in graph:
256                newnode = {}
257                for i in range(rank):
258                        for j in range(rank):
259                                if node[i] and graph[node[i]][j]:
260                                        newnode[(i,j)] = graph[node[i]][j]
261                result.append(newnode)
262        return result