XQuery

Question

में दो ग्राफ़ नोड्स के बीच एक पथ खोजें, मैं एक एल्गोरिदम बनाने की कोशिश कर रहा हूं जो xQuery में ग्राफ में दो नोड्स के बीच पथ खोजता है और देता है, मेरे पास अभी तक कोई भाग्य नहीं है क्योंकि यह केवल एक नोड देता है और यह adyacent नोड्स है। सबसे पहले मैं स्पष्ट कर दिया कि ग्राफ एक निर्देशित ग्राफ है और प्रत्येक नोड शून्य, एक या एक से अधिक मूल हो सकता है, 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 से है मैं नोड से 4 नोड 1 से पथ प्राप्त करना चाहते हैं (node1-> node2 -> node4) लेकिन जो कुछ भी मैं होता तो बस करने की कोशिश मुझे नोड 1-नोड 2 और नोड 3 दें लेकिन नोड 4 एक और बात यह नहीं है कि मैं एक रास्ता चुनना चाहता हूं जो सख्त नहीं है सीटी, मेरा मतलब, अगर मैं node5 और node7 लेकिन दोनों node5 और node7 के बीच पथ चाहते node6 की ओर निर्देशित कर रहे हैं

मैं

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) 

(कोड XQuery को यह अजगर कोड अनुकूल कोशिश की है मेरा नहीं है, यह अंतर्गत आता है यह 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 और अजगर के बीच मौलिक अंतर यह है कि XQuery मैं एस 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 दृश्यों शायद उपयोग करने के लिए सबसे अच्छा डेटा संरचना नहीं हैं एक कतार के रूप में। लुकअप के लिए एक्सएमएल टुकड़ों के बारे में भी यही कहा जा सकता है। इसलिए यदि आपके पास XQuery 3.0 प्रोसेसर तक पहुंच है, तो आप https://github.com/LeoWoerteler/xq-modules पर लिखे गए कुछ (कम से कम असम्बद्ध रूप से) अधिक कुशल डेटा संरचनाओं पर एक नज़र डाल सकते हैं। मैंने उदाहरण के रूप में Dijkstra's algorithm भी शामिल किया।