xquery - 두 노드 사이의 모든 경로를 찾는 BFS

Question

2 개월 전까지, 또는 xquery에서 BFS 알고리즘을 구현하여 2 개의 노드 사이의 최단 경로를 찾을 수 있도록 도와주었습니다. 다행히도 누군가 나를 도와주었습니다. 그들이 저에게 준 코드는 사소한 수정 작업을했습니다.

이제 모든 프로그램을 테스트하면 두 노드 사이의 모든 경로를 찾아야한다는 결론에 도달했습니다. 내가 지금으로이 코드는 다음과 같습니다

자신의 길이가 동일하지만 난 그것을 필요로 할 때 그대로, 작업 만 두 노드 사이의 최단 경로가 발견 된 코드가, 그것도 여러 경로를 발견

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

가능한 모든 경로를 찾으십시오.

그래서 내 질문은 어떻게 모든 경로를 찾기 위해 주어진 코드를 수정합니까? 또는 다른 언어로 구현하는 방법을 알고 있지만 xQuery로 변환하는 방법을 모르는 DFS 같은 다른 알고리즘을 받아 들일 수도 있습니다.

xquery 또는 함수형 프로그래밍에 익숙하지 않아서 ' 내가 시험해 보았지만 나 혼자하지 마라.

EDIT이 프로그램에 대한 샘플 입력 그래프 다음과 같은

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

제가 제 노드에 함수를 호출하는 경우는 먼저 모든 후속 노드를 반환해야 될

DFS 노드는이 예에서 '루트'입니다하지만 난 노드 2의 함수를 호출하는 경우는 원점 노드 2

Answer 1

이다 그건 당신이뿐만 아니라 사용할 수있는 모든 경로에 대한 노드 4를 반환해야합니다 :

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