Re: topological sort

Subject: Re: topological sort
From: "Peter B. West" <pbwest@xxxxxxxxxxxxxx>
Date: Fri, 10 Nov 2000 21:30:18 +0000
Joerg, David & Jeni,

I am just staring at two new solutions.  As it takes me a few days to
struggle through each iteration, I don't expect to understand these for
a while yet.  In the meantime, I have been experimenting with the use of
keys.  Here's the stylesheet:

<xsl:stylesheet xmlns:xsl="";
  <xsl:output method="text"/>
  <xsl:key name="nodesReferringTo" match="/structs/struct/name"
  <xsl:key name="references" match="/structs/struct/field/type/ref"
  <xsl:key name="nodesReferredTo" match="/structs/struct/name" use="."/>
  <xsl:template match="structs">
    <xsl:variable name="nodes"
		  select="struct/name[not(key('nodesReferringTo', .))]"/>
    <xsl:call-template name="resolve">
      <xsl:with-param name="testnodes" select="$nodes"/>
      <xsl:with-param name="resolved" select="/.."/>
  <xsl:template name="resolve">
    <xsl:param name="testnodes"/>
    <xsl:param name="resolved"/>
    <xsl:if test="$testnodes">
      <xsl:variable name="finished"
      <xsl:apply-templates select="$finished[not($resolved)]"/>
      <xsl:call-template name="resolve">
	<xsl:with-param name="testnodes"
			key('references', $testnodes))"/>
	<xsl:with-param name="resolved"
      <xsl:for-each select="$testnodes">
	<xsl:if test="count($resolved|$finished|.) >
	  <xsl:apply-templates select="."/>

  <xsl:template match="name">
    <xsl:value-of select="."/>
    <xsl:text> </xsl:text>


Firstly, this takes FOUR times as long for the transformation as Joerg's
model, as massaged by me and David.  I'm using Xalan, as distributed
with Cocoon 1.8.  I think it's 1.0.1.

The output is, like Jeni's version, A C E B D.   This is because of the
start conditions.

I have made no attempt to protect against circular references.  I think
that involves another parameter, but I can't see how to do it.

The algorithm is

find the set of nodes which have no references to them
         I.e., that are the start of the reference chains.
         (This is what the key 'nodesReferringTo' is for.)

call the template 'resolve' with that set as as the nodes to test,
 and an empty 'resolved' set.

resolve($testnodes, $resolved)
  if the $testnodes set is non-empty
    construct the set $finished from $testnodes with no type/ref
    output the nodes in $finished unless they are also in $resolved
          (This takes care of multiple references.)
    construct a new $testnodes set from nodes referred to by current
          (the keys 'references' and 'nodesReferredTo' used here)
    construct a new $resolved set from the union of $resolved and
    resolve($testnodes, $resolved)
          (resolve all nodes further along the reference chain)
    output nodes in original $testnodes unless they are members of
      $resolved or $finished

Use of sets.
The property that node-sets have no duplicates was useful, but in some
cases my attempts at set manipulation failed.  My first cut was
outputting individual struct names within for-each loops.  I tried to
eliminate these by forming node-sets and using apply-templates to pass
output handling on to the "name" template.  However, this did not always

E.g., although commands like
<xsl:apply-templates select="$finished[not($resolved)]"/>
worked, when I changed
      <xsl:for-each select="$testnodes">
	<xsl:if test="count($resolved|$finished|.) >
	  <xsl:apply-templates select="."/>

to begin with
      <xsl:for-each select="$testnodes[not($resolved|$finished)]">
with the intention of going to

the stylesheet broke.  What, if anything, is wrong with the above

I was originally passing around sets of "struct" nodes, but, because all
of the key manipulations were focussed on "name" nodes, I changed to
using sets of "name" nodes.  This made the nested key call feasible.

I'm sorry that this is such a long posting, but this is my school for

Peter B. West  pbwest@xxxxxxxxxxxxxx
"Lord, to whom shall we go?"

 XSL-List info and archive:

Current Thread