[xsl] topological sort

Subject: [xsl] topological sort
From: Bill Keese <billk@xxxxxxxxxxxxxxxxxxxx>
Date: Thu, 09 Oct 2003 11:34:37 +0900
Regarding the post from two years ago about topological sorting (http://www.biglist.com/lists/xsl-list/archives/200101/msg00161.html),
here is another approach that I came up with. To me it seems to be more in the spirit of XSLT, ie, writing functionally rather than procedurally. Tell me what you think.

Topological sort refers to printing the nodes in a graph such that you print a node before you print any nodes that reference that node. Here's an example of a topologically sorted list:

       <element id="bar"/>
       <element id="bar2"/>
       <element id="foo">
           <idref  id="bar"/>

My algorithm is simply:
1. each node gets a weight which is greater than the weight of any nodes it references
2. sort by weight

The algorithm is O(n^2) for a simple XSLT processor, but it would be O(n) if the XSLT processor was smart enough to cache the values returned from the computeWeight(node) function. Does saxon do this? Maybe it would if I used keys.

Here is the code. Note that it's XSLT V2 (although it could be written more verbosely in XSLT V1).

<xsl:stylesheet xmlns:xsl="http://www.w3.org/1999/XSL/Transform";

Here's the code to compute the weight of a node (This code doesn't detect circular dependencies, but it should be easy to add. That's left as an exercise to the reader. :-)

<xsl:function name="bill:computeWeight" as="xs:integer*">
<xsl:param name="node"/>
<!-- generate a sequence containing the weights of each node I reference -->
<xsl:variable name="referencedNodeWeights" as="xs:integer*">
<xsl:sequence select="0"/>
<xsl:for-each select="$node/idref/@id">
<xsl:value-of select="bill:computeWeight(//element[@id=current()])"/>
<!-- make my weight higher than any of the nodes I reference -->
<xsl:value-of select="max($referencedNodeWeights)+1"/>

Here's the driver code, that sorts the elements according to their weight.

   <xsl:template match="/">
       <xsl:for-each select="top/element">
           <xsl:sort select="bill:computeWeight(.)" data-type="number"/>
           <xsl:copy-of select="."/>


XSL-List info and archive: http://www.mulberrytech.com/xsl/xsl-list

Current Thread