search

digraphs / Digraphs

The GAP package Digraphs
https://digraphs.github.io/Digraphs
Other
29 stars 42 forks source link

Possible bug in HomomorphismDigraphsFinder #111

Closed james-d-mitchell closed 6 years ago

james-d-mitchell commented 6 years ago

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 commented 6 years ago

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.