Digraphs icon indicating copy to clipboard operation
Digraphs copied to clipboard

Improve `CayleyDigraph` performance

Open reiniscirpons opened this issue 11 months ago • 0 comments

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.

reiniscirpons avatar Apr 07 '25 14:04 reiniscirpons