Re: [Exist-open] Topological sort code problem

[Joe W. <jo...@gm...>]

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
>>>
>>