Digraphs
Digraphs copied to clipboard
Improve `CayleyDigraph` performance
The current CayleyDigraph method is rather inefficient, see excerpt below:
set := AsSet(G);
D := Digraph(IsImmutableDigraph,
G,
set,
OnLeftInverse,
{x, y} -> LeftQuotient(x, y) in gens);
The issue comes from using the Digraph method for this. In the current form, the check LeftQuotient(x, y) in gens is run for each element x, y in the group G. This means the final algorithm has complexity O(|G|^2). On the other hand, using something like the Todd-Coxeter or maybe even Froidure-Pin would have complexity O(|G|*|gens|) where gens is the set of generators of G that we are constructing the group with. So it would be quite useful to improve the CayleyDigraph method to use one of these algorithms instead.