0

我问了一个问题 2 个月左右，我需要帮助在 xquery 中实现 BFS 算法以找到有向图中两个节点之间的最短路径，幸运的是有人帮助了我，他们给我的代码做了一些小的修改。

现在的事情是测试整个程序我得出的结论是我需要找到两个节点之间的所有路径。我现在的代码是：

declare function local:result($steps, $dest) {
let $pred := 
for $node in $steps
return if($node/@to = $dest)then string($node/@from) else ()
return if(exists($pred)) then (local:result($steps, $pred), $dest)
else $dest
};

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

declare function local:BFS($graph, $queue, $steps, $end, $iteracion) {
if(empty($queue)) then error(xs:QName('local:NOTFOUND'), $iteracion)
else (
  let $curr := $queue[1], $rest-queue := $queue[position() > 1]
  return (
     if($curr eq $end) then local:result($steps, $end)
     else (
        let $successors :=  if (empty($graph)) then error(xs:QName('local:NOTFOUND'), 'no grafo') else 
        for $node in $graph/Enlaces/Enlace/origen
        return if(string($node) = $curr) then $graph[Enlaces/Enlace/origen/text() = $node]/id/text() else  ()
        let $new-steps  := 
        for $succ in $successors
          return <edge from="{$curr}" to="{$succ}" />
        return local:BFS( $graph,($rest-queue, $successors),($steps, $new-steps),$end, $iteracion + 1)
  )
)
)};

原样的代码正在工作，但只能找到两个节点之间的最短路径，它甚至可以在它们的长度相同时找到几条路径，但我需要它来找到所有可能的路径。

所以我的问题是如何修改给定的代码以查找所有路径？或者我什至可以接受另一种算法，如 DFS，我知道如何用其他语言实现，但我不知道如何将它翻译成 xQuery

我不精通 xQuery 也不精通函数式编程，所以尽管我尝试过，但我不自己做。

编辑：

该程序的示例输入将是一个图形，例如

<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/>

然后，如果我在第一个节点上调用该函数，则必须返回所有后续节点，因为在本示例中第一个节点是“根”，但如果我在节点 2 上调用该函数，则必须返回节点 4，因为它的原点是节点 2

4

1 回答 1

1

对于所有路径，您不妨使用 DFS：

<nodes>
  <node>
    <id>1</id>
    <edges>
      <edge to="2"/>
      <edge to="5"/>
    </edges>
  </node>
  <node>
    <id>2</id>
    <edges>
      <edge to="3"/>
      <edge to="1"/>
    </edges>
  </node>
  <node>
    <id>3</id>
    <edges/>
  </node>
  <node>
    <id>5</id>
    <edges>
      <edge to="3"/>
      <edge to="4"/>
    </edges>
  </node>
  <node>
    <id>4</id>
    <edges>
      <edge to="3"/>
    </edges>
  </node>
</nodes>

然后用这个

declare function local:DFS($graph, $visited as xs:string*, $start, $end) {
  if ($start/id = $end/id) then (string-join($visited, '->')) else (
  for $edge in $start//edge
    return if (not($visited = $edge/@to)) then (local:DFS($graph, ($visited, data($edge/@to)), $graph//node[id = $edge/@to], $end)) else ())
};

declare function local:DFS($graph, $start, $end) {
  local:DFS($graph, ($start/id/text()), $start, $end)
};

local:DFS(., //node[id='1'], //node[id='3'])
于 2014-06-27T10:36:13.860 回答