Wrong result from DigraphPath in the master branch

[wilfwilson]

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.

[james-d-mitchell]

Another example:

D := DigraphFromDigraph6String("&~?@cHOVS]GbccT?a?SKpUJgDwKg@cA_?q?@lK@]T\\WeJR[_B@\
BBW?gdXHR?`?ELDHCcGCqMQvR@@HkQMg]PMI?gGj?GPAe[EhSI\\GofbGSbS_@o|G?~cJU_jccs?Oq\
`qo_OEK_b_V?KB_dJDRCE@rr??qAH]{?L@S@C?QOG?OOjOSP@W_GC@WqWcKQBPKIrUCy@pAGroA?SH\
ODuHE]ASLC@U}gbK?aHocGDKO`waOAyCFi`IC?G[_qKejmZSTCDLb?G@CPO`aG@`kkJKaADioq_jAL\
DqBhwaCQOaG@BB[??JzYtwAC_hBAJ`awCzeJCIgEu{NAhAkspoM__?@?]GziPCECWQ?EcO?ZGDgCgg\
Bgu?SA`?nAH`aqjDts?@OPesqC?YcGCfBQweULIB?GOh|IGGpWB`@wQcd[S@cR?K[KQLOS{RI[c]Ba\
nHdJoGCCOcaK\\aUH?@ofQclXRooh~mKt_jNDaaDB?IobkfO_ayIH_CyD_?KLIXk@aO_{_??okoueJ\
CSPD@pOFkpCIpWGGBf}OAw??wSAC}|^??BA?jDq?O?DyhAlsCUmIe@iSD?QEBo_?kDLMHhWYlEpC_W\
tAEGJMkMUOd?dYbof?Qafx@m?RsJrgCRK_xT@kgs_?{H_}He@Q?X@w@[CaSHYIk_a?GaV`HL?~cK~@\
PSidE?akZCcBepl?H?sE`QQDnD?Y]vaCdR]eC_GkCFGAmsRMJWHU_rDc`EPvOA`QqsgMMAKTNQOEH_\
_MGC?DsDeod_zy}Uhs_W`EOAc[OjXAE`DD?MrfY`BadyBPAWa[cKtP_UCaeRYJArbNJOSo[KhcJaPw\
D|Mo_t_wEAC@O`QLoDAC@royRGD?n@BPT`OSc?KD_GBt?OEJ?OwEXWCVdsGowASS?YZC_rF_BWqda}\
DPV?sU?OCDLBLD?A@c?RqOOpOGOI@@e?Ac@C?V?PALoURwOKSppd?og\\aYxO?`G_^IxuIATCEr?g?\
IXB_EQKeK@LQ@xyUQOTpGo]OJBGbQaijGHROKQOSNlHQCAgH?hjGZY]ALfBgcO]XChOIgM`NBIeiFk\
No@]ROPKgZA_cW@BoH?NPkOKPkA?IL?mrAQN??cFUV_`GsfiHnBI[s]PaDLBaHHW?diuowwF^`cwJy\
AIFl_lpoAyiUE@{?eh?JaRb]Q_akQZd?Y\\ODoG@LAHUOAcLTKh}B?`@qSHxNdYC?CDPYKcgj`rS?P\
@B]oce_RCE?xBfI?CtlkSCGoC@a`hCJPtQEA_rReUCPoDGCBC]_Y??J?f_fCxi@OUahcaMdII??Ce`\
lR_`yiC_X`afCIE^ja]bgehAJG`MHE?HSIOKTClPCa@[cDb?C@o`O{H?eOBiruG_D@J@OF?DGKG?OJ\
@xK\\deBHQL`l\\EKJCY@c@_GPe|GioHOX?TMQ?CBVDEt?hAB@pF@??hX_GLqdfCC`bEKGFCsSGpUH\
_Bv?G`JDbKMObB@EogGQPGC[OGjbSDWujKgBs_irEc[dnptN[_BC?wpB?ylGeBOAhosOdProAG`?PY\
I@sWYBXZtAMXgAA[mFB?YiBEShK~?mDCBoK?ICBq@o_O@TG?Y?wQ@GuqGVoqG[]CQPWK?_CLWS[GQo\
KwQKGe]gWsAGSdb@ogCNkgH?h?S?aiAgQloRDt_ga?@o]Nt[OxPdRjDC?PhS}nL?m|B_")
F := UndirectedSpanningTree(D);
Error, List Element: <list>[3] must have an assigned value in
  if record.parent[record.current] <> record.current then
    Add( data[record.parent[record.current]], record.current );
    Add( data[record.current], record.parent[record.current] );
fi; at /Users/jdm/gap/pkg/digraphs/gap/attr.gi:2298 called from
ExecuteDFS_C( record, data, start, PreOrderFunc, PostOrderFunc, AncestorFunc,
 CrossFunc ); at /Users/jdm/gap/pkg/digraphs/gap/oper.gi:2309 called from
ExecuteDFS( record, data, i, PreOrderFunc, DFSDefault, DFSDefault, DFSDefault
 ); at /Users/jdm/gap/pkg/digraphs/gap/attr.gi:2302 called from
UndirectedSpanningForest( D ) at /Users/jdm/gap/pkg/digraphs/gap/attr.gi:2348 called from
<function "UndirectedSpanningTreeAttr for an immutable digraph">( <arguments> \
)
 called from read-eval loop at *stdin*:13
type 'quit;' to quit to outer loop

[james-d-mitchell]

Wait this problem only exists in the DFS branch moving the comment over there...

[wilfwilson]

I'm going to close this issue. The ExecuteDFS stuff no longer exists in the master branch; however, the master branch does now contain the test at the top of this issue, which was failing. Therefore this problem can't work its way back into the master branch.

Re-adding a fixed version of this stuff is #499, so I don't think there's a need for this issue any longer.