我只是返回一个节点并且它是相邻的节点,所以我没有运气 . First i should make clear that the graph is a directed graph and every node can have zero, one or more origins, in the XML a node only has the link to it's origin but not to it's following nodes
这是一些节点及其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
我已经尝试将这个python代码改编为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
()
};
1 回答
XQuery和Python之间的根本区别在于XQuery是functional programming language . 这意味着之后不能修改绑定到变量的值 . 例如,在函数
local:BFS(...)
中,你不能在循环中更改$queue
的值,你所要做的就是创建一个新的变量$queue
,它会遮蔽外部变量 .为了使它工作,您可以将外部循环编写为recursive function,而不是将当前队列作为参数 . 然后,循环的每次迭代都是使用更新版本的队列调用函数:
可以通过向起始节点提供第一个边来调用它:
所有使用的边都存储在
$steps
中 . 为了在找到目的地后重建路径,我们可以向后遍历它们直到找到初始边缘:如果您担心性能,XQuery序列可能不是用作队列的最佳数据结构 . 关于用于查找的XML片段也可以这样说 . 因此,如果您可以访问XQuery 3.0处理器,您可以查看我在https://github.com/LeoWoerteler/xq-modules处写的一些(至少是渐近的)更有效的数据结构 . 我甚至以Dijkstra's algorithm为例 .