искать путь между двумя узлами графа в XQuery

Question

Я пытаюсь сделать алгоритм, который ищет и возвращает путь между двумя узлами в графе в xQuery, мне не повезло, пока он возвращает только один узел и это аддитивные узлы. Во-первый я должен пояснить, что граф представляет собой ориентированный граф, и каждый узел может иметь ноль, один или несколько происхождения, в XML узел имеет только ссылку на его происхождение, но не это следующие узлы

Вот пример некоторых узлов и их 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> 

с этого XML я хотел бы получить путь от узла 1 к узлу 4 (node1-> node2 -> node4) но все, что я пытаюсь сделать бы просто дайте мне node1-node2 и node3, но не node4 . Другое дело, что я хочу выбрать путь, который не является ужасным кт, я имею в виду, если я хочу, чтобы путь между node5 и node7, но как node5 и node7 направлены node6

Я попытался адаптировать этот питон код 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) 

(код не мой, это принадлежит к этому законному кодировщик в this activestate page)

вот что я пытался сделать:

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 
       () 


}; 

Answer 1

Принципиальное различие между XQuery и Python является то, что XQuery я s a functional programming language. Это означает, что значение, связанное с переменной, впоследствии не может быть изменено. В вашей функции local:BFS(...), например, вы не можете изменить значение $queue внутри цикла, все, что вы делаете, - это создать новую переменную $queue, которая будет тени внешней.

Чтобы заставить его работать, вы можете написать внешний цикл как recursive function вместо этого, который принимает текущую очередь в качестве аргумента. Каждая итерация цикла затем один вызов функции с обновленной версией очереди:

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

Он может быть вызван путем подачи первого края до начального узла:

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

Все используемые края хранятся в $steps. Для того, чтобы восстановить путь после того, как мы нашли место назначения, мы можем просто пройти их назад, пока мы не найдем начальный край:

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

Если вы беспокоитесь о производительности, XQuery последовательность, вероятно, не лучшая структура данных для использования как очередь. То же самое можно сказать об XML-фрагментах для поиска. Поэтому, если у вас есть доступ к процессору XQuery 3.0, вы можете взглянуть на некоторые (по крайней мере асимптотически) более эффективные структуры данных, которые я написал в https://github.com/LeoWoerteler/xq-modules. В качестве примера я даже включил Dijkstra's algorithm.