The fundamental difference between XQuery and Python is that XQuery is a functional programming language. This means that the value bound to a variable cannot be modified afterwards. In your function local:BFS(...)
for example you cannot change the value of $queue
inside the loop, all you do is create a new variable $queue
that shadows the outer one.
In order to get it to work, you can write the outer loop as a recursive function instead that takes the current queue as an argument. Each iteration of the loop is then one invocation of the function with an updated version of the queue:
declare function local:BFS($graph, $queue, $steps, $end) {
if(empty($queue)) then error(xs:QName('local:NOTFOUND'), 'No path found.')
else (
let $curr := $queue[1], $rest-queue := $queue[position() > 1]
return (
if($curr eq $end) then local:result($steps, $end)
else (
let $successors :=
$graph//node[Links/Link/origin = $curr and not($steps/@to = id)]/id/string()
let $new-steps :=
for $succ in $successors
return <edge from="{$curr}" to="{$succ}" />
return local:BFS(
$graph,
($rest-queue, $successors),
($steps, $new-steps),
$end
)
)
)
)
};
It can be called by supplying the first edge to the start node:
declare function local:BFS($graph, $start, $end) {
local:BFS($graph, $start, <edge to="{$start}" />, $end)
};
All used edges are stored in $steps
. In order to reconstruct the path after we found the destination, we can just traverse them backwards until we find the initial edge:
declare function local:result($steps, $dest) {
let $pred := $steps[@to = $dest]/@from/string()
return if(exists($pred)) then (local:result($steps, $pred), $dest)
else $dest
};
If you are concerned about performance, XQuery sequences are probably not the best data structure to use as a queue. The same can be said about XML fragments for lookups. So if you have access to an XQuery 3.0 processor, you can have a look at some (at least asymptotically) more efficient data structures I wrote at https://github.com/LeoWoerteler/xq-modules. I even included Dijkstra's algorithm as an example.