Search

Topological sorting in XQuery

In the course of my attempts to implement an XQuery engine for the XML pipeline language XPL, I realized that I would need to sort the processes so that each process has its inputs available, i.e. a topological sort.

Given a sequence of nodes and references with the Relax-NG schema:



                                        

element node {           attribute id { xs:string },           element ref {               attribute id { xs:string }           }*       }+


The post-condition after sorting can be defined as:


                                        

                                            

                                                
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};

and the recursive function to order the nodes is:



                                        

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 local:topological-sort( $unordered except $nodes, ($ordered, $nodes ))};

Sweet, eh? Even if this implementation is not the most efficient, it has the advantage of being obviously correct.

See (and improve!) the XQuery WikiBook article.