Menu
▾
▴
[Exist-open] Fwd: Topological sort code problem
|
From: Chris W. <kit...@gm...> - 2023-05-12 03:48:38
|
---------- Forwarded message --------- From: Chris Wallace <kit...@gm...> Date: Fri, 12 May 2023, 04:47 Subject: Re: [Exist-open] Topological sort code problem To: Joe Wicentowski <jo...@gm...> Hi Joe , fake news from me Im afraid - too quick and bad testing so my larger graphs are in fact failing, as did a re-write avoiding the high order constructs which I see you tried too. Kit On Thu, 11 May 2023, 23:24 Joe Wicentowski, <jo...@gm...> wrote: > Hi Chris, > > Sure! Your post was really concerning, so I wanted to see if I could > reproduce it and report it in the form of an XQSuite test ( > https://exist-db.org/exist/apps/doc/xqsuite). This is the best way to > demonstrate a bug to the core developers so they can begin analyzing it and > test their own fixes. Also, they often incorporate the tests directly into > the eXist CI test suite, to ensure the bug doesn't appear again. > > It's interesting to hear that you're not seeing the same problem with > larger graphs. I just added a post to the issue, with a new variant of the > simple (i.e., non-XQSuite) test, which lets you configure how large you > want the graph to be. For me, eXist fails to sort any graphs with more than > 2 nodes, whereas the same tests all pass in BaseX and Saxon. Here's the > link to that variant: > > https://github.com/eXist-db/exist/issues/4918#issuecomment-1544753088 > > Joe > > On Thu, May 11, 2023 at 3:42 PM Chris Wallace <kit...@gm...> > wrote: > >> Hi Joe, >> Many thanks for looking at this - yes I was just about to confess that >> I'd called the test function incorrectly and that it's fine >> >> My god, Joe, you are a hard worker ! That's quite some test you >> constructed there! >> >> Ive just been running the same algorithm on a number of larger graphs >> (the context is ordering the evaluation of computations in a >> spreadsheety thing) >> and all have been sorted correctly so it does seem to be just that case >> of a sequence of 3 - weird. >> >> Awe and regards >> >> Kit >> >> >> On Thu, May 11, 2023 at 7:28 PM Joe Wicentowski <jo...@gm...> wrote: >> >>> Hi Kit, >>> >>> I can confirm that eXist returns incorrectly sorted results in 6.2.0, >>> and BaseX and Saxon return the correct results. >>> >>> I did find one mistake in your query: your $issorted variable should be >>> changed to check $sortedNodes/node instead of $sortedNodes. This shows that >>> the local:topological-sorted function returns the expected results in >>> eXist, and the problem is limited to the something that happens in the >>> course of eXist's processing of local:topological-sort function. >>> >>> It's possible that the query once worked in eXist but a regression was >>> introduced at some point. >>> >>> I've worked on refining your report into an XQSuite test, and I've >>> posted an issue: >>> >>> https://github.com/eXist-db/exist/issues/4918 >>> >>> Joe >>> >>> On Wed, May 10, 2023 at 1:20 PM Chris Wallace <kit...@gm...> >>> wrote: >>> >>>> Back in the day (2008) , I wrote an algorithm for a topological sort >>>> and put it in the wikibook >>>> >>>> https://en.wikibooks.org/wiki/XQuery/Topological_Sort >>>> >>>> It's been there for 14 years and is unchanged but it doesn't now on my >>>> 3.0 version nor on 5.3.1 >>>> <sorted> <graph> <node id="b"> <ref id="c"/> </node> <node id="c"/> >>>> <node id="a"> <ref id="b"/> <ref id="c"/> </node> </graph> </sorted> >>>> >>>> It returns all nodes but they are not in the right order and even more >>>> puzzling the condition for the nodes to be in order evaluates true for both >>>> the expected value and the erroneous result. >>>> >>>> Has it always been wrong - I'm sure it worked on the then current >>>> version. It seems to be transparently correct or has something changed? >>>> >>>> The problem seems to be that in constructing the >>>> expression ($ordered,$nodes), the ordering of of the $ordered nodes is lost >>>> >>>> Here is the test script >>>> >>>> declare function local:topological-sorted($nodes) as xs:boolean { >>>> every $n in $nodes satisfies >>>> every $id in $n/ref/@id >>>> satisfies $id = $n/preceding::node/@id >>>> }; >>>> >>>> declare function local:topological-sort($unordered, $ordered) { >>>> if (empty($unordered)) >>>> then $ordered >>>> else >>>> let $nodes := $unordered [ every $id in ref/@id satisfies $id = >>>> $ordered/@id] >>>> return >>>> if ($nodes) >>>> then local:topological-sort( $unordered except $nodes, >>>> ($ordered, $nodes )) >>>> else () (: cycles so no order possible :) >>>> }; >>>> >>>> let $graph := >>>> <graph> >>>> <node id="a"> >>>> <ref id="b"/> >>>> <ref id="c"/> >>>> </node> >>>> <node id="b"> >>>> <ref id="c"/> >>>> </node> >>>> <node id="c"/> >>>> </graph> >>>> >>>> let $expected := >>>> <graph> >>>> <node id="c"/> >>>> <node id="b"> >>>> <ref id="c"/> >>>> </node> >>>> <node id="a"> >>>> <ref id="b"/> >>>> <ref id="c"/> >>>> </node> >>>> </graph> >>>> >>>> let $sortedNodes := >>>> <graph>{local:topological-sort($graph/node,())}</graph> >>>> let $issorted := local:topological-sorted($sortedNodes) >>>> let $expectedsorted := local:topological-sorted($expected/node) >>>> return >>>> element result { >>>> element input {$graph}, >>>> element expected {$expected}, >>>> element sorted {$sortedNodes}, >>>> element issorted {$issorted}, >>>> element expected-sorted {$expectedsorted} >>>> } >>>> >>>> >>>> _______________________________________________ >>>> Exist-open mailing list >>>> Exi...@li... >>>> https://lists.sourceforge.net/lists/listinfo/exist-open >>>> >>> |
