Re: [Exist-open] Topological sort code problem

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

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
>