Przeszukuj ścieżkę między dwoma węzłami wykresów w XQuery

Question

Próbuję utworzyć algorytm, który wyszukuje i zwraca ścieżkę między dwoma węzłami na wykresie w XQuery, nie miałem szczęścia, o ile zwraca tylko jeden węzeł i to są odpowiednie węzły. Najpierw należy wyjaśnić, że wykres jest graf skierowany, a każdy węzeł może mieć zero, jeden lub więcej początków w XML węzeł ma tylko link do jego pochodzenie, ale nie jest to następujących węzłów

Oto przykład niektórych węzłów i ich 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> 

od tego XML chciałbym uzyskać ścieżkę od węzła 1 do węzła 4 (node1-> Node2 -> node4) ale co próbuję zrobić, to po prostu daj mi węzeł1-węzeł2 i węzeł3, ale nie węzeł4 kolejną rzeczą jest to, że chcę wybrać ścieżkę, która nie jest groźna ct, to znaczy, jeśli chcę ścieżkę między node5 i node7 ale obie node5 i node7 są skierowane node6

Próbowałem dostosowania ten kod Pythona do 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) 

(kod nie moje, to należy do jego prawowitego koder w this activestate page)

oto co próbowałem zrobić:

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

Podstawowa różnica między XQuery i Python jest to, że ja XQuery s a functional programming language. Oznacza to, że wartości przypisanej do zmiennej nie można później zmodyfikować. Na przykład w swojej funkcji local:BFS(...) nie można zmienić wartości $queue w pętli, wystarczy jedynie utworzyć nową zmienną $queue, która zacienia zewnętrzną.

Aby go uruchomić, można zapisać zewnętrzną pętlę jako recursive function zamiast tego, która przyjmuje bieżącą kolejkę jako argument. Każda iteracja pętli jest wtedy jeden wywołanie funkcji ze zaktualizowaną wersją kolejki:

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

To może być wywołana poprzez dostarczanie pierwszą krawędź do węzła start:

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

Wszystkie wykorzystane krawędzie są przechowywane w $steps. W celu odtworzenia ścieżki po okazało się, że cel, możemy po prostu przechodzić je do tyłu, aż znajdziemy początkowej krawędzi:

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

Jeśli chodzi o wydajność, sekwencje XQuery nie są prawdopodobnie najlepszy struktury danych do wykorzystania jako kolejka. To samo można powiedzieć o fragmentach XML dla odnośników. Więc jeśli masz dostęp do procesora XQuery 3.0, możesz rzucić okiem na niektóre (przynajmniej asymptotycznie) bardziej wydajne struktury danych, które napisałem pod numerem https://github.com/LeoWoerteler/xq-modules. Jako przykład posłużyłem nawet Dijkstra's algorithm.