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 為空。在每次迭代中，計算僅依賴於已排序節點的節點集，並將這些節點從未排序節點中刪除並新增到已排序節點中。