Skip to content

Wrong result from DigraphPath in the master branch #487

Closed
Closed
Wrong result from DigraphPath in the master branch#487
Labels
bugA label for issues that are bugs

Description

@wilfwilson
wilfwilson
opened on May 28, 2021

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.

Activity

  1. wilfwilson
    added
    bugA label for issues that are bugs
    on May 28, 2021

  2. james-d-mitchell commented on Sep 30, 2021

    @james-d-mitchell
    james-d-mitchell
    on Sep 30, 2021
    Member

    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

  3. james-d-mitchell commented on Sep 30, 2021

    @james-d-mitchell
    james-d-mitchell
    on Sep 30, 2021
    Member

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

  4. wilfwilson commented on Oct 27, 2021

    @wilfwilson
    wilfwilson
    on Oct 27, 2021
    CollaboratorAuthor

    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.

  5. wilfwilson
    closed this as completedon Oct 27, 2021
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    bugA label for issues that are bugs

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions