Fwd: Topological sort code problem

---------- Forwarded message ---------
From: Chris Wallace <[email protected]>
Date: Fri, 12 May 2023, 04:47
Subject: Re: [Exist-open] Topological sort code problem
To: Joe Wicentowski <[email protected]>


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, <[email protected]> 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 <[email protected]>
> 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 <[email protected]> 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 <[email protected]>
>>> 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
>>>> [email protected]
>>>> https://lists.sourceforge.net/lists/listinfo/exist-open
>>>>
>>>

_______________________________________________
Exist-open mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/exist-open