suche einen Pfad zwischen zwei Grafikknoten in XQuery

Question

Ich versuche, einen Algorithmus zu machen, der einen Pfad zwischen zwei Knoten in einem Graph in xQuery sucht und zurückgibt, ich hatte bisher kein Glück, da es nur einen Knoten zurückgibt es sind benachbarte Knoten. Zuerst sollte ich klarstellen, dass der Graph ein gerichteter Graph ist und jeder Knoten kann null, eine oder mehrere Ursachen haben, in der XML ein Knoten nur den Link muss es Ursprung ist aber nicht beschränkt auf es folgende Knoten

hier ist ein Beispiel für einige Knoten und ihre 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> 

von diesem XML ich möchte den Pfad von Knoten 1 zu Knoten erhalten 4 (node1-> Knoten2 -> node4) aber was ich versuchen würde, genau das zu tun gib mir node1-node2 und node3, aber nicht node4 eine andere Sache ist, dass ich einen Pfad auswählen möchte, der nicht dire ist ct, ich meine, wenn ich den Weg zwischen Knoten5 und node7 wollen aber beide Knoten5 und node7 sind auf node6 gerichtet

Ich habe versucht, diese Python-Code Anpassung

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 nicht von mir XQuery es gehört es zu this activestate page)

hier rechtmäßigen Coder ist das, was ich zu tun habe versucht: ist

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

Der grundlegende Unterschied zwischen XQuery und Python, dass XQuery i s ein functional programming language. Dies bedeutet, dass der an eine Variable gebundene Wert nicht nachträglich geändert werden kann. In Ihrer Funktion local:BFS(...) zum Beispiel können Sie den Wert von $queue innerhalb der Schleife nicht ändern, alles, was Sie tun, ist eine neue Variable $queue, die die äußere Schatten.

Um es zum Laufen zu bringen, können Sie die äußere Schleife als recursive function schreiben, die stattdessen die aktuelle Warteschlange als Argument nimmt. Jede Iteration der Schleife wird dann ein Aufruf der Funktion mit einer aktualisierten Version der Warteschlange:

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

Es kann bei der ersten Kante auf den Startknoten genannt werden:

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

All verwendete Kanten werden in $steps gespeichert. Um den Weg zu rekonstruieren, nachdem wir das Ziel gefunden haben, können wir sie nur durchqueren nach hinten, bis wir die Anfangskante finden:

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

Wenn Sie über die Leistung betrifft, sind XQuery-Sequenzen wahrscheinlich nicht die beste Datenstruktur zu verwenden, als eine Warteschlange. Das gleiche gilt für XML-Fragmente für Lookups. Wenn Sie also Zugriff auf einen XQuery 3.0 Prozessor haben, können Sie sich einige (mindestens asymptotisch) effizientere Datenstrukturen ansehen, die ich unter https://github.com/LeoWoerteler/xq-modules geschrieben habe. Ich habe sogar als ein Beispiel aufgenommen.