search a path between two graph nodes in XQuery

exist-db, xml, xquery, xslt

Solution

The fundamental difference between XQuery and Python is that XQuery is a functional programming language. This means that the value bound to a variable cannot be modified afterwards. In your function `local:BFS(...)` for example you cannot change the value of `$queue` inside the loop, all you do is create a new variable `$queue` that shadows the outer one.

In order to get it to work, you can write the outer loop as a recursive function instead that takes the current queue as an argument. Each iteration of the loop is then one invocation of the function with an updated version of the queue:

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

It can be called by supplying the first edge to the start node:

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

All used edges are stored in `$steps`. In order to reconstruct the path after we found the destination, we can just traverse them backwards until we find the initial edge:

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

If you are concerned about performance, XQuery sequences are probably not the best data structure to use as a queue. The same can be said about XML fragments for lookups. So if you have access to an XQuery 3.0 processor, you can have a look at some (at least asymptotically) more efficient data structures I wrote at https://github.com/LeoWoerteler/xq-modules. I even included Dijkstra's algorithm as an example.

Problem

I'm trying to make an algorithm that searchs and returns a path between two nodes in a graph in xQuery, i've had no luck so far as it returns just one node and it's adyacent nodes. First i should make clear that the graph is a directed graph and every node can have zero, one or more origins, in the XML a node only has the link to it's origin but not to it's following nodes Here's an example of some nodes and their 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> ``` From that XML i would like to get the path from node 1 to node 4 ( node1-> node2 -> node4) but whatever i try to do would just give me node1-node2 and node3 but not node4 another thing is that i want to select a path that is not direct, i mean, if i want the path between node5 and node7 but both node5 and node7 are directed towards node6 I've tried adapting this python code to 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) ``` (code not mine, it belongs to it's rightful coder at this activestate page) here is what i've tried to do: ``` 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 () }; ```

Original source