搜索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作爲例子。