Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
An implementation of the Todd-Coxeter Algorithm for Semigroups and Monoids in python3
#!/usr/bin/env python3
class ToddCoxeter:
def __init__(self):
self.nodes = [0]
self.edges = None
self.kappa = []
self.next_node = 1
self.R = []
def set_alphabet(self, A: str) -> None:
self.A = A
self.edges = [[None] * len(A)]
def add_relation(self, u: int, v: int) -> None:
u = [self.A.index(x) for x in u]
v = [self.A.index(x) for x in v]
self.R.append((u, v))
def path(self, c: int, w: list) -> int:
w = [w] if not isinstance(w, list) else w
for a in w:
c = self.edges[c][a]
if c is None:
return None
return c
def tc1(self, c: int, a: int) -> int:
if self.edges[c][a] is None:
self.nodes.append(self.next_node)
self.edges[c][a] = self.next_node
self.edges.append([None] * len(self.A))
self.next_node += 1
return self.edges[c][a]
def tc2(self, c: int, u: list, v: list) -> None:
u_1, v_1 = u[:-1], v[:-1]
a, b = u[-1] if len(u) > 0 else [], v[-1] if len(v) > 0 else []
if (
self.path(c, u) is None
and self.path(c, v) is not None
and self.path(c, u_1) is not None
):
self.edges[self.path(c, u_1)][a] = self.path(c, v)
elif (
self.path(c, u) is not None
and self.path(c, v) is None
and self.path(c, v_1) is not None
):
self.edges[self.path(c, v_1)][b] = self.path(c, u)
elif (
self.path(c, u) is not None
and self.path(c, v) is not None
and self.path(c, u) != self.path(c, v)
):
self.kappa.append((self.path(c, u), self.path(c, v)))
def tc3(self, i: int, j: int) -> bool:
if i == j:
return False
if i > j:
i, j = j, i
for a in self.A:
if self.path(j, a) is not None:
if self.path(i, a) is None:
self.edges[i, a] = self.path(j, a)
else:
self.kappa.append((self.path(i, a), self.path(j, a)))
for c in self.nodes:
for a in self.A:
if self.path(c, a) == j:
self.edges[c][a] = i
self.kappa = [[i, l] if k == j else [k, l] for k, l in self.kappa]
self.kappa = [[k, i] if l == j else [k, l] for k, l in self.kappa]
self.nodes.remove(j)
return True
def felsch(self) -> int:
self.A = range(len(self.A))
while True:
d, a = next(
(
(d, a)
for d in self.nodes
for a in self.A
if self.path(d, a) is None
),
(None, None),
)
if d is None:
return self.size()
self.tc1(d, a)
for c in self.nodes:
for u, v in self.R:
self.tc2(c, u, v)
while len(self.kappa) != 0:
self.tc3(*self.kappa.pop())
def hlt(self) -> int:
self.A = range(len(self.A))
seen = set()
while True:
current = next((c for c in self.nodes if c not in seen), None)
if current is None:
return self.size()
for u, v in self.R:
c = current
for a in u:
c = self.tc1(c, a)
c = current
for a in v[:-1]:
c = self.tc1(c, a)
self.tc2(current, u, v)
while len(self.kappa) != 0:
self.tc3(*self.kappa.pop())
seen.add(current)
def size(self) -> int:
if any((True for u, v in self.R if len(u) == 0 or len(v) == 0)):
return len(self.nodes)
else:
return len(self.nodes) - 1
C = ToddCoxeter()
C.set_alphabet("ab")
C.add_relation("aaa", "a")
C.add_relation("bbb", "b")
C.add_relation("abab", "aa")
assert C.felsch() == 14
assert C.hlt() == 14
C = ToddCoxeter()
C.set_alphabet("ab")
C.add_relation("aaa", "a")
C.add_relation("bb", "b")
C.add_relation("abab", "aa")
assert C.felsch() == 5
assert C.hlt() == 5
C = ToddCoxeter()
C.set_alphabet("abc")
C.add_relation("ac", "aa")
C.add_relation("bb", "b")
C.add_relation("ca", "aa")
C.add_relation("bc", "cb")
C.add_relation("cc", "aa")
C.add_relation("aaa", "aa")
C.add_relation("aba", "aa")
assert C.felsch() == 8
assert C.hlt() == 8
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment