xquery - BFS查找兩個節點之間的所有路徑

Question

我已經問了一個問題2個月左右，我需要幫助在xquery中實現BFS算法以找到有向圖中兩個節點之間的最短路徑，幸運的是有人幫我他們給我的代碼做了一些小修改。

現在的事情是，測試整個程序我得出結論，我需要找到兩個節點之間的所有路徑。該代碼，我到現在爲止是：

declare function local:result($steps, $dest) { 
let $pred := 
for $node in $steps 
return if($node/@to = $dest)then string($node/@from) else() 
return if(exists($pred)) then (local:result($steps, $pred), $dest) 
else $dest 
}; 

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

declare function local:BFS($graph, $queue, $steps, $end, $iteracion) { 
if(empty($queue)) then error(xs:QName('local:NOTFOUND'), $iteracion) 
else (
    let $curr := $queue[1], $rest-queue := $queue[position() > 1] 
    return (
    if($curr eq $end) then local:result($steps, $end) 
    else (
     let $successors := if (empty($graph)) then error(xs:QName('local:NOTFOUND'), 'no grafo') else 
     for $node in $graph/Enlaces/Enlace/origen 
     return if(string($node) = $curr) then $graph[Enlaces/Enlace/origen/text() = $node]/id/text() else () 
     let $new-steps := 
     for $succ in $successors 
      return <edge from="{$curr}" to="{$succ}" /> 
     return local:BFS($graph,($rest-queue, $successors),($steps, $new-steps),$end, $iteracion + 1) 
) 
) 
)}; 

，因爲它是，是工作，但只找到兩個節點之間的最短路徑的代碼，它甚至發現一些路徑時，它們的長度是相同的，但我需要它找到所有可能的路徑。

所以我的問題是我如何修改給定的代碼來查找所有路徑？或者我甚至可以接受另一種算法，如DFS，我知道如何實現其他語言，但我不知道如何將其轉換爲xQuery

我不精通xQuery，也沒有功能性編程，所以這就是爲什麼我不'儘管我嘗試過，但我自己做了。

編輯：

這個程序A樣本輸入將是一個曲線圖，如

<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/> 

然後，如果我打電話第一個節點上的功能那就要返回所有後續節點作爲第一節點是「根」在這個例子中，但如果我呼籲節點2的功能，它會爲它的起源節點2

Answer 1

返回節點4對於所有的路徑，你還不如用DFS：

<nodes> 
    <node> 
    <id>1</id> 
    <edges> 
     <edge to="2"/> 
     <edge to="5"/> 
    </edges> 
    </node> 
    <node> 
    <id>2</id> 
    <edges> 
     <edge to="3"/> 
     <edge to="1"/> 
    </edges> 
    </node> 
    <node> 
    <id>3</id> 
    <edges/> 
    </node> 
    <node> 
    <id>5</id> 
    <edges> 
     <edge to="3"/> 
     <edge to="4"/> 
    </edges> 
    </node> 
    <node> 
    <id>4</id> 
    <edges> 
     <edge to="3"/> 
    </edges> 
    </node> 
</nodes> 

然後用這個

declare function local:DFS($graph, $visited as xs:string*, $start, $end) { 
    if ($start/id = $end/id) then (string-join($visited, '->')) else (
    for $edge in $start//edge 
    return if (not($visited = $edge/@to)) then (local:DFS($graph, ($visited, data($edge/@to)), $graph//node[id = $edge/@to], $end)) else()) 
}; 

declare function local:DFS($graph, $start, $end) { 
    local:DFS($graph, ($start/id/text()), $start, $end) 
}; 

local:DFS(., //node[id='1'], //node[id='3'])