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

Question

我试图做一个算法，在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我想获得到节点4从节点1的路径（node1->节点2 - >节点4） 但无论我尝试做只想给我node1-node2和node3但不是node4 另一件事是，我想选择一个不是可怕的路径CT，我的意思是，如果我想和节点5，但node7两个节点5和node7之间的路径是针对node6

我试图适应这个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) 

（代码不是我的，它属于它在this activestate page合法编码器）

这里就是我试图做的事：

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


}; 

Answer 1

的XQuery和Python之间的根本区别是，我的XQuery s a functional programming language。这意味着绑定到变量的值不能在之后修改。例如，在您的函数local:BFS(...)中，您无法更改循环内的$queue的值，只需创建一个影响外部变量的新变量$queue。

为了让它起作用，你可以将外循环写为recursive function，而不是将当前队列作为参数。该循环的每次迭代，然后与一个更新版本的队列的功能中的一个调用：

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处理器，则可以查看我在https://github.com/LeoWoerteler/xq-modules上编写的一些（至少渐近地）更高效的数据结构。我甚至包括Dijkstra's algorithm作为例子。