Re: [Exist-open] Topological sort code problem

[Chris W. <kit...@gm...>]

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