在 XQuery 中搜索两个图节点之间的路径

我正在尝试创建一种算法，用于搜索并返回 xQuery 中图形中两个节点之间的路径，但到目前为止我没有运气，因为它只返回一个节点及其相邻节点。首先，我应该明确该图是一个有向图，每个节点可以有零个、一个或多个原点，在 XML 中，节点仅具有到其原点的链接，但不具有到其后续节点的链接

下面是一些节点及其 XML 的示例

<node>
  <id> 123-456-789</id>
  <name> something </name>
  <Links>
     <Link>
        <origin></origin>
     </Link>
  <Links>

 <node>
  <id> 245-678-901</id>
  <name> node 2</name>
  <Links>
     <Link>
        <origin> 123-456-789 </origin>
     </Link>
  <Links>

  <node>
  <id> xxx-xxx-xxx</id>
  <name> node 3</name>
  <Links>
     <Link>
        <origin> 123-456-789 </origin>
     </Link>
  <Links>

  <node>
  <id> 234-546-768</id>
  <name> node 4</name>
  <Links>
     <Link>
        <origin> 245-678-901</origin>
     </Link>
  <Links>

从该 XML 我想获取从节点 1 到节点 4 的路径（节点 1-> 节点 2 -> 节点 4） 但无论我尝试做什么只会给我node1-node2和node3而不是node4 另一件事是我想选择一条不直接的路径，我的意思是，如果我想要节点5和节点7之间的路径，但节点5和节点7都指向节点6

我尝试将此 python 代码改编为 xquery

def BFS(graph,start,end,q):

temp_path = [start]

q.enqueue(temp_path)

while q.IsEmpty() == False:
    tmp_path = q.dequeue()
    last_node = tmp_path[len(tmp_path)-1]
    print tmp_path
    if last_node == end:
        print "VALID_PATH : ",tmp_path
    for link_node in graph[last_node]:
        if link_node not in tmp_path:
            new_path = []
            new_path = tmp_path + [link_node]
            q.enqueue(new_path)

（代码不是我的，它属于它的合法编码者此活动状态页面 http://code.activestate.com/recipes/576675/)

这是我尝试做的：

declare function local:BFS($graph as element()* , $ini_node as element(Node)*, $end_node as element(Node)*) as element()*
{
    let $seq := $ini_node
    let $queue := ($seq)
    for $item in $queue
        return
            if ( count($queue) > 0) then
                let $seq := remove($queue, count($queue))
                let $last := $seq[last()] return if (deep-equal($last, $end_node)) then $seq
                else
                    for $node in $graph[contains(.,$graph/id[contains(.,$last/Links/Link/origin/text())])] (: what i've tried was to get the graph nodes which id is equal to the origins of the last node :)
                        return if(not(functx:is-node-in-sequence-deep-equal($node,$seq))) then
                            let $new_path:= ()
                            let $new_path:= insert-before($seq, count($seq)+1, $node)
                            let $queue := insert-before($queue,1, $new_path) return $queue
                        else ()

            else
                ()


};

XQuery 和 Python 之间的根本区别在于 XQuery 是一个函数式编程语言 http://en.wikipedia.org/wiki/Functional_programming。这意味着绑定到变量的值之后无法修改。在你的函数中local:BFS(...)例如你不能改变的值$queue在循环内，您所做的就是创建一个新变量$queue遮蔽了外部。

为了让它工作，您可以将外循环编写为递归函数 http://en.wikipedia.org/wiki/Recursion_%28computer_science%29相反，它将当前队列作为参数。循环的每次迭代都是使用队列的更新版本调用该函数：

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
        )
      )
    )
  )
};

可以通过向起始节点提供第一条边来调用它：

declare function local:BFS($graph, $start, $end) {
  local:BFS($graph, $start, <edge to="{$start}" />, $end)
};

所有使用的边都存储在$steps。为了在找到目的地后重建路径，我们可以向后遍历它们，直到找到初始边缘：

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

如果您担心性能，XQuery 序列可能不是用作队列的最佳数据结构。对于用于查找的 XML 片段也是如此。因此，如果您有权访问XQuery 3.0 http://www.w3.org/TR/xquery-30/处理器，你可以看看我写的一些（至少渐近）更有效的数据结构https://github.com/LeoWoerteler/xq-modules https://github.com/LeoWoerteler/xq-modules。我什至包括迪杰斯特拉算法 https://github.com/LeoWoerteler/xq-modules/blob/master/src/test/xquery/dijkstra.xq举个例子。