Possible bug in HomomorphismDigraphsFinder

[james-d-mitchell]

Gordon Royle reports:

d := Digraph([[ 2, 3, 4, 5, 6, 7, 8, 9, 10 ],
[ 22, 1, 13, 14, 15, 16, 19, 20, 21 ],
[ 22, 1, 13, 16, 17, 18, 9, 20, 21 ],
[ 22, 1, 15, 16, 17, 18, 19, 20, 10 ],
[ 17, 1, 18, 19, 21, 22, 8, 10, 12 ],
[ 1, 12, 15, 17, 7, 19, 20, 10, 21 ],
[ 1, 13, 14, 6, 18, 19, 9, 20, 21 ],
[ 22, 1, 13, 14, 5, 16, 18, 19, 9 ],
[ 22, 1, 3, 15, 17, 7, 8, 10, 21 ],
[ 1, 14, 4, 5, 16, 6, 18, 9, 20 ],
[ 22, 12, 13, 15, 17, 18, 19, 20, 21 ],
[ 11, 13, 14, 5, 16, 6, 18, 19, 20 ],
[ 11, 12, 2, 3, 15, 17, 7, 8, 21 ],
[ 22, 12, 2, 15, 7, 8, 19, 10, 21 ],
[ 11, 2, 13, 14, 4, 16, 6, 9, 20 ],
[ 22, 12, 2, 3, 4, 15, 17, 8, 10 ],
[ 11, 13, 3, 4, 5, 16, 6, 18, 9 ],
[ 11, 12, 3, 4, 5, 17, 7, 8, 10 ],
[ 11, 12, 2, 14, 4, 5, 6, 7, 8 ],
[ 11, 12, 2, 3, 4, 15, 6, 7, 10 ],
[ 11, 2, 13, 3, 14, 5, 6, 7, 9 ],
[ 11, 2, 3, 14, 4, 5, 16, 8, 9 ]]);;
HomomorphismDigraphsFinder(d,d,fail,[],1,fail,false,[ 1, 3, 4, 5, 8, 9, 10, 16, 17, 18, 22 ],[],fail,fail);
# returns [ Transformation( [ 1, 3, 4, 3, 8, 10, 4, 5, 10, 9, 8, 5, 22, 17, 9, 17, 16, 22, 18, 1, 16, 18 ] )

But:

gap> Orbit(AutomorphismGroup(d), [ 1, 3, 4, 5, 8, 9, 10, 16, 17, 18, 22 ],OnSets);
[ [ 1, 3, 4, 5, 8, 9, 10, 16, 17, 18, 22 ], [ 2, 6, 7, 11, 12, 13, 14, 15, 19, 20, 21 ] ]
gap> HomomorphismDigraphsFinder(d,d,fail,[],1,fail,false,[ 2, 6, 7, 11, 12, 13, 14, 15, 19, 20, 21 ],[],fail,fail);
[  ]

Another way to see this is that:

dd := InducedSubdigraph(d, [ 2, 6, 7, 11, 12, 13, 14, 15, 19, 20, 21 ]);
t := DigraphHomomorphism(d, dd);
# returns Transformation( [ 1, 6, 10, 9, 11, 9, 7, 6, 8, 7, 10, 2, 8, 11, 4, 5, 2, 3, 3, 5, 1, 4 ] )

[james-d-mitchell]

I think I know how to fix this, it seems to be caused by an assumption in the C code that the very first point assigned in the homomorphism finding code is an orbit representative of the automorphism group of the graph, and in the example that fails, this orbit rep is 1, but this does not occur in the set of specified images [ 2, 6, 7, 11, 12, 13, 14, 15, 19, 20, 21 ]. If this restriction is removed, then the code appears to work again.