Menu
▾
▴
Re: [Exist-open] Topological sort code problem
|
From: Chris W. <kit...@gm...> - 2023-05-12 05:24:46
|
Looking for a workaround I found this works - wrapping the sequence in an
element
declare function local:topological-sort($unordered, $ordered-graph) {
if (empty($unordered))
then $ordered-graph/*
else
let $ordered := $ordered-graph/*
let $nodes := $unordered [ every $id in ref/@id satisfies $id =
$ordered/@id]
return
if ($nodes)
then let $remainder := $unordered except $nodes
let $ordered-graph := element graph {($ordered ,
$nodes)}
return local:topological-sort($remainder, $ordered-graph)
else () (: cycles so no order possible :)
};
On Fri, May 12, 2023 at 4:47 AM Chris Wallace <kit...@gm...> wrote:
> 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
>>>>>
>>>>
|
