XQuery/拓扑排序

动机

您有一个有向无环图 (DAG) 来跟踪诸如依赖关系图之类的信息。您希望对输入 DAG 中的节点进行排序，以便在输出中反映依赖关系结构。

有向无环图的拓扑排序将节点按顺序排列，以便每个节点仅引用前面的节点。

例如，在管道中调度进程时需要此排序。

例如，给定一个定义为以下的 DAG

<node id="a">
       <ref id="b"/>
       <ref id="c"/>
</node>
<node id="b">
       <ref  id="c"/>
</node>
<node id="c"/>

拓扑顺序将是

<node id="c"/>
<node id="b">
       <ref  id="c"/>
 </node>
<node id="a">
       <ref id="b"/>
       <ref id="c"/>
</node>

拓扑排序的定义可以用 XQuery 简单地表达出来

declare function local:topological-sorted($nodes) as xs:boolean {
    every $n in $nodes satisfies
          every $id in $n/ref/@id 
                 satisfies $id = $n/preceding::node/@id
};

递归算法也很直接

declare function local:topological-sort($unordered, $ordered )   {
    if (empty($unordered))
    then $ordered
    else
        let $nodes := $unordered [ every $id in ref/@id satisfies $id = $ordered/@id]
        return 
          if ($nodes)
          then local:topological-sort( $unordered except $nodes, ($ordered, $nodes ))
          else ()  (: cycles so no order possible :)
};

其调用方式为

let $graph :=
 <graph>
    <node id="a">
       <ref id="b"/>
       <ref id="c"/>
    </node>
    <node id="b">
       <ref  id="c"/>
    </node>
    <node id="c"/>
 </graph>
let $sortedNodes := <graph>{local:topological-sort($graph/node,())}</graph>
return local:topological-sorted($sortedNodes/node)

解释

$ordered 最初是原始序列，$ordered 为空。在每次迭代中，计算仅依赖于已排序节点的节点集，并将这些节点从未排序节点中删除并添加到已排序节点中。