Creating Cayley Graphs from Group Presentations

Definitions:

A Cayley graph is a directed graph showing how to get from any element of a group to any other using only a finite number of "generator" elements.  For example, in the group $\mathbb{Z}_2\times\mathbb{Z}_2$ we could use the generators $a = (1,0)$ and $b = (0,1)$ and we'd end up with a graph that looks like a square with arrows going round the edges.

A Group presentation defines a group by specifying generators and relations between them.  For example the presentation $\langle a,b \vert a^2=1,b^2=1,aba^{-1}b^{-1}=1\rangle$ specifies a group.  In fact the group it specifies is isomorphic to  $\mathbb{Z}_2\times\mathbb{Z}_2$ and we can prove this using the facts that $a$ and $b$ commute and both have order 2.  In this case it's easy to see what group we have but in general it's a bit more difficult.  A useful first step would be to be able to draw the Cayley graph automatically.

Question:

Is it possible to automatically generate a Cayley graph from a group presentation?

Answer: Yes!

I've been playing around in python and thrown together some code to convert a group presentation into a Cayley graph.  Let's take the rotational symmetries of the cube as an example group.  Let $a$ to be a rotation of $90^\circ$ around one of the faces, and $b$ be a rotation of $120^\circ$ around one of the vertices.  Playing around with a real cube I've determined that $(ab)^2 = 1$, although this depends on the choice of $a$ and $b$.  This suggests the presentation below, but note that we can't tell for sure yet whether it will require additional relations.

$$
\langle a,b \vert a^4=1,b^3=1,(ab)^2=1\rangle
$$

Putting this presentation through the algorithm generates the following graph

The Cayley graph is a Rhombicuboctahedron!

This group has 24 members, which happens to be the number of rotational symmetries of the cube, since every rotational symmetry corresponds to a permutation of the 4 diagonals and vice versa.  This tells us that we don't need any further relations in our presentation to get the group we are interested in.

The Code:

Here's the python code that produced the graphviz output, that generated the image.

#!/usr/bin/env python3
class CayleyGraph:
    def __init__(self, generators, relations, max_edges=None):
        """
        E.g. <a,b|ababa = b> (which is the same as <a,b|ababab^-1 = 1>) is created using arguments:

            CayleyGraph({"a", "b"},{("a","b","a","b","a","b^-1")})

        Only works for finite graphs
        """

        # TODO: validate relations

        # E.g. identity_relations  == {(("a",1),("b",1),("a",1),("b",1),("a",1),("b",-1))}
        identity_relations = set()
        for relation in relations:
            _l = []
            for token in relation:
                if "^" in token:
                    g, n = token.split("^")
                    _l.append((g, int(n)))
                else:
                    g = token
                    _l.append((g, 1))
            identity_relations.add(tuple(_l))

        unprocessed_nodes = [1]
        idx = 2

        # edges allows looking node pairs to look up generator e.g. self.edges[1,2] == "a"
        self.edges = {}

        # build graph
        while len(unprocessed_nodes) > 0:
            # Add each identity relations to node, creating new nodes as we go
            node = unprocessed_nodes.pop(0)
            for relation in identity_relations:
                src = None
                dst = node
                for g, n in relation:
                    while n > 0:
                        src = dst
                        dst = idx
                        unprocessed_nodes.append(dst)
                        idx += 1
                        self.edges[src, dst] = g
                        n -= 1
                    while n < 0:
                        src = dst
                        dst = idx
                        unprocessed_nodes.append(dst)
                        idx += 1
                        self.edges[dst, src] = g
                        n += 1
                # replace dst with node
                if (src, dst) in self.edges:
                    self.edges[src, node] = self.edges[src, dst]
                    self.edges.pop((src, dst))
                    unprocessed_nodes.remove(dst)
                if (dst, src) in self.edges:
                    self.edges[node, src] = self.edges[dst, src]
                    self.edges.pop((dst, src))
                    unprocessed_nodes.remove(dst)

            # Remove any aliases
            while True:
                pair = self._find_alias()
                if pair is None:
                    break
                a, b = min(pair), max(pair)
                edges = dict(self.edges)
                for (x, y), g in self.edges.items():
                    if x == b:
                        edges[a, y] = g
                        edges.pop((x, y))
                    elif y == b:
                        edges[x, a] = g
                        edges.pop((x, y))
                self.edges = edges
                if b in unprocessed_nodes:
                    unprocessed_nodes.remove(b)

            if max_edges != None and len(self.edges) >= max_edges:
                break

        # Cosmetic
        self._relabel_nodes()

    def _relabel_nodes(self):
        # Cosmetic: rename nodes other than 1 with labels starting at g2
        nodes = set()
        for a, b in self.edges:
            nodes.add(a)
            nodes.add(b)
        nodes.remove(1)
        nodes = list(nodes)
        nodes.sort()
        lookup = {1: "1"}
        idx = 2
        for a in nodes:
            lookup[a] = f"g{idx}"
            idx += 1
        edges = {}
        for (a, b), g in self.edges.items():
            edges[lookup[a], lookup[b]] = g
        self.edges = edges

    def _find_alias(self):
        # Find a pair of nodes that must be aliases
        # Examples:
        #  * if self.edges contains (2,3):'a'  and (2,5):'a' then 3 and 5 are aliases.
        #  * if self.edges contains (3,2):'b'  and (5,2):'b' then 3 and 5 are aliases.
        fdict = {}
        rdict = {}
        for (a, b), g in self.edges.items():
            if (a, g) in fdict:
                return b, fdict[a, g]
            if (b, g) in rdict:
                return a, rdict[b, g]
            fdict[a, g] = b
            rdict[b, g] = a
        return None

    def __str__(self):
        s = [
            "# pipe into 'neato -Tpng -ooutput.png && open output.png'",
            "digraph cayley {",
            "    overlap=false;",
            "    node [fixedsize=true,shape=circle,style=filled];",
        ]
        # ? filter for nodes in nodes_complete
        for (a, b), g in self.edges.items():
            s.append(f'    "{a}" -> "{b}" [label="{g}"];')
        s.append("}")
        return "\n".join(s)


if __name__ == "__main__":
    print(CayleyGraph({"a", "b"}, {("a", "b", "a", "b"), ("a^4",), ("b^3",)}))