[xsl] topological sort
Regarding the post from two years ago about topological sorting
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:
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).
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*">
<!-- generate a sequence containing the weights of each node I
<xsl:variable name="referencedNodeWeights" as="xs:integer*">
<!-- make my weight higher than any of the nodes I reference -->
Here's the driver code, that sorts the elements according to their weight.
<xsl:sort select="bill:computeWeight(.)" data-type="number"/>
XSL-List info and archive: http://www.mulberrytech.com/xsl/xsl-list