An implementation of the Todd-Coxeter Algorithm for Semigroups and Monoids in python3

todd_coxeter.py

#!/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