xQuery - BFS to find all paths between two nodes

Question

I've asked a question 2 months or so where i needed help implementing the BFS algorithm in xquery to find the shortest path between two nodes in a directed graph, luckily someone helped me and the code they gave me worked with some minor modifications.

The thing now is that testing the whole program i came to the conclusion that i need to find all paths between two nodes. The code i have as of now is:

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

The code as it is, is working but only finds the shortest path between two nodes, it even finds several paths when their lengths are the same but i need it to find all possible paths.

so my question is how do i modify the given code to find all paths? or i could even accept another algorithm like DFS which i know how to implement in other languages but i don't know how to translate it to xQuery

I'm not proficient in xQuery nor functional programming so that's why i don't do it by myself although i tried.

EDIT:

A Sample input for this program would be a graph such as

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

then if i call the function on the first node it would have to return all subsequent nodes as the first node is the 'root' in this example but if i call the function on node 2 it would have to return node 4 as it's origin is node 2

Answer 1

For all paths you might as well use 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>

Then use this

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