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'])