Closed
Description
This example came from the failing Semigroups package tests https://github.com/semigroups/Semigroups/pull/746/checks?check_run_id=2688637629 although there are likely to be smaller examples.
gap> D := Digraph([
> [ 2, 3, 4, 5, 5 ], [ 6, 3, 4, 7, 5 ], [ 8, 9, 10, 8, 11 ],
> [ 12, 13, 14, 15, 16 ], [ 2, 13, 4, 12, 17 ], [ 6, 9, 4, 16, 11 ],
> [ 18, 13, 4, 12, 8 ], [ 8, 19, 10, 19, 20 ], [ 8, 9, 10, 8, 21 ],
> [ 12, 13, 14, 15, 16 ], [ 22, 13, 14, 12, 16 ], [ 23, 13, 24, 12, 8 ],
> [ 19, 9, 19, 8, 24 ], [ 19, 13, 19, 15, 16 ], [ 21, 19, 24, 19, 20 ],
> [ 25, 13, 10, 12, 8 ], [ 26, 13, 10, 12, 17 ], [ 6, 3, 4, 7, 27 ],
> [ 19, 19, 19, 19, 19 ], [ 28, 13, 19, 12, 16 ], [ 29, 13, 14, 12, 16 ],
> [ 23, 3, 24, 7, 30 ], [ 29, 9, 14, 16, 24 ], [ 12, 19, 14, 19, 19 ],
> [ 8, 8, 10, 24, 15 ], [ 8, 8, 10, 24, 31 ], [ 30, 19, 4, 19, 20 ],
> [ 19, 8, 19, 24, 12 ], [ 23, 9, 24, 16, 21 ], [ 6, 13, 4, 12, 17 ],
> [ 32, 13, 24, 12, 17 ], [ 29, 3, 14, 7, 7 ] ]);;
gap> path := DigraphPath(D, 5, 5);;
gap> IsDigraphPath(D, path);
false
Some more detail about why it's not a path:
gap> # Check the value against the definition - wrong
gap> ForAll([1 .. Length(path[2])], i -> OutNeighbours(D)[path[1][i]][path[2][i]] = path[1][i + 1]);
false
gap> # Check whether the vertices are even correct (with just the edges being wrong) - no
gap> ForAll([1 .. Length(path[2])], i -> path[1][i + 1] in OutNeighbours(D)[path[1][i]]);
false
gap> # This is the first spot where it goes wrong
gap> First([1 .. Length(path[2])], i -> OutNeighbours(D)[path[1][i]][path[2][i]] <> path[1][i + 1]);
14
This is likely related to the recent changes to the depth-first search infrastructure, since DigraphPath uses a DFS.