Add a rudimentary `RepresentativeAction` function for digraphs

[wilfwilson]

RepresentativeAction(G, D1, D2) and RepresentativeAction(G, D1, D2, OnDigraphs) should return an element g of the permutation group G that maps D1 to D2, i.e. OnDigraphs(D1, g) = D2.

For G = SymmetricDigraph(n), where n >= DigraphNrVertices(D1), we can simply return IsomorphismDigraphs(D1, D2).

For a general permutation group G, we can return return either fail or an element of

Intersection(G, AutomorphismGroup(D1) * IsomorphismDigraphs(D1, D2))

if D1 and D2 are isomorphic, and the intersection is non-empty. I expect that computing this group-coset intersection would be slow in general, but correct (I think?)

Once 'graph backtrack' (my project in Halle with @ChrisJefferson and Rebecca Waldecker) has a fast implementation available via GAP, we could use that instead for the general case (probably via https://github.com/peal/GraphBacktracking).

[ChrisJefferson]

This is probably easier to do by adapting IsIsomorphicDigraph -- it almost calculates this, just change the last line so, once you have checked if the graphs are Isomorphic, return NautyCanonicalLabelling(D)*NautyCanonicalLabelling(C)^-1 (modulo if I've got the multiplications, and inverse, in the right place).

[wilfwilson]

We already do this in the function IsomorphismDigraphs:

Digraphs/gap/isomorph.gi

Line 457 in fda0c30

return NautyCanonicalLabelling(C) / NautyCanonicalLabelling(D);

But nauty only looks in the whole symmetric group for a possible isomorphism - I intend this issue to be about finding an isomorphism in an arbitrary permutation group. (Sorry if I've misunderstood what you're saying.) i.e. "Find me an element of G that maps C to D".

[wilfwilson]

I originally wrote:

Once 'graph backtrack' (my project in Halle with @ChrisJefferson and Rebecca Waldecker) has a fast implementation available via GAP, we could use that instead for the general case

The result of this research is a new package called Vole. Vole integrates with (and requires) the Digraphs package, and lets you do various permutation group-related computations, including many that involve Digraphs package digraphs. For instance, you can do the thing that I asked for in this issue:

gap> D := CycleDigraph(6);;
gap> Vole.RepresentativeAction(SymmetricGroup(6), D, DigraphReverse(D), OnDigraphs);
(1,4)(2,3)(5,6)
gap> Vole.RepresentativeAction(AlternatingGroup(6), D, DigraphReverse(D), OnDigraphs);
(1,5)(2,4)

(see https://peal.github.io/vole/doc/chap4_mj.html#X857DC7B085EB0539).

Vole is still a work in progress, but it's progressing rapidly. At some point I'll probably close this issue, given that the requested feature is now available in Vole (and can't be easily duplicated in Digraphs, as-is).

[james-d-mitchell]

Would it maybe be a good idea to mention this in the Digraphs manual too? @wilfwilson ?

[wilfwilson]

Yes, that is probably a good idea. I'll give some thought about how/where to do that!

I also need to think about installing methods for the actual RepresentativeAction operation, with the arguments being a group, two digraphs, and OnDigraphs. (Rather than only having it behind Vole.RepresentativeAction). So far with Vole we're not positioning our methods to override any built-in GAP methods, only to serve as an alternative for now. But there is no such built-in version of RepresentativeAction.

It might also be sensible to have Vole as a suggested package for Digraphs, so that it will autoload when Digraphs loads, if a user has it installed.