Allow not calculating the automorphism group before finding homomorphisms?

[flsmith]

There are cases where the user knows that calculating the automorphism group of a digraph will take far longer than looking for homomorphisms. For example, if you look for embeddings between these two digraphs with the specified colouring(of which there are none) it takes about a minute to just compute the automorphism group of the target graph, while it really only needs to check one additional vertex!

gap> source_colours := [1 .. 5];;
gap> colours := [ 1, 2, 3, 3, 4, 4, 4, 4, 4, 4, 4, 3, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5,
>   4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6,
>   6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
>   6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
>   6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
>   6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
>   6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 4, 5, 4, 5,
>   4, 5, 4, 5 ];;
gap> D := DigraphFromDiSparse6String(".~?Ad__B`oLa?Jrg@_K@_K@_K@_Md_O?__?_SK?CM?SO?cX?k^?[dBKiBSnB[wBc\\fo]gW^h__iG`aLV@|_A|dCTnAlxA]BC[JpGLqwc");
<immutable digraph with 165 vertices, 38 edges>
gap> C := DigraphDisjointUnion(ChainDigraph(3), ChainDigraph(2));;
gap> partial_map := [1, , 15, 158, 2];;
gap> order := [1, 3, 4, 5, 2];;
gap> Size(HomomorphismDigraphsFinder(source, 
                                     D,
                                     fail,
                                     [],
                                     1,
                                     fail,
                                     1,
                                     DigraphVertices(D),
                                     partial_map,
                                     source_colours,
                                     colours,
                                     order) > 0;
false

Perhaps there should simply be another option to the HomomorphismsDigraphFinder which prevents the automorphism group from being calculated. Presently there is no user workaround if colours are given, but otherwise the user can use SetAutomorphismGroup to avoid this.

[ChrisJefferson]

Do you have a feeling for why it takes so long? I wouldn't expect a graph on 165 vertices to take bliss very long. Is it actually bliss, or gap/digraphs pre- and post- processing?

[james-d-mitchell]

The reason is that the graph has few edges, so the calculation in the homomorphism finder is quicker than that of the automorphism group. The point of @flsmith PR #285 is to allow specifying automorphism to the homomorphism finder, which circumvents this, which I think is completely reasonable.