XQuery

Question

iki grafik düğümleri arasında bir yol arama xQuery bir grafikte iki düğüm arasında bir yol arar ve bir yol döndüren bir algoritma yapmaya çalışıyorum, bir düğüm döndürdüğü kadarıyla hiç şansım olmadı ve adyanth düğümleri. İlk i grafiği yönlendirilmiş grafiktir ve kökeni ama değil takip ediyor düğümler

için her düğüm bir düğüm sadece bağlantı vardır XML, sıfır, bir veya birden fazla kaynağı olabilir açıkça yapmalıdır İşte bir bazı düğümlerin bir örnek ve bu XML itibaren kendi 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> 

i düğüm 4'e düğüm 1'den yolunu almak istiyorum var (node1-> node2 -> düğüm4) ama olur sadece yapmaya çalışacağım ne olursa olsun node1-node2 ve node3 ver ama node4 'u başka bir şey vermek istemiyorum, başka bir şey olmayan bir yol seçmek istiyorum Ben

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 xquery için bu piton kodunu adapte denedim

ct, ben Düğüm6 yöneliktir Düğüm5 ve node7 ama hem Düğüm5 ve node7 arasındaki yolu istiyorsanız, demek benim değil, bu o this activestate page de haklı kodlayıcı) var aittir

burada

i yapmaya çalıştığım budur:

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 ve Python arasındaki temel fark, XQuery i functional programming language. Bu, bir değişkene bağlanan değerin daha sonra değiştirilemeyeceği anlamına gelir. Örneğin, local:BFS(...) işlevinizde, döngü içinde $queue değerini değiştiremezsiniz, tek yapmanız gereken dış gölgeyi gölgelendiren $queue yeni bir değişken oluşturmaktır.

Çalışmasını sağlamak için dış döngüyü geçerli sıra olarak bir argüman olarak alan yerine recursive function olarak yazabilirsiniz.

Bu başlangıç ​​düğümüne birinci kenarı tedarik çağrılabilir

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

tüm kullanılan döngü her bir yineleme sonra sıranın bir sürümünü fonksiyonunun bir çağırma olan kenarlar $steps'da depolanır. Biz ilk bulana kadar biz hedef bulduktan sonra yolu yeniden inşa etmek için, biz sadece geriye onları hareket ettirebilir: Eğer performansı hakkında endişeleriniz varsa

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 dizileri muhtemelen kullanılacak en iyi veri yapısı değildir sıra olarak. Aynı aramalar için XML parçaları hakkında da söylenebilir. Yani, bir XQuery 3.0 işlemciye erişiminiz varsa, https://github.com/LeoWoerteler/xq-modules adresinde yazdığım bazı (en asimptotik olarak) daha verimli veri yapılarına bakabilirsiniz. Örnek olarak Dijkstra's algorithm'u ekledim.