[xsl] Re: topological sort

[Joerg Pietschmann <joerg.pietschmann@xxxxxx>]

Hello,
i finally finished a stylesheet for processing elements in
topological sorted order. It is based on my original approach
sent to this list some months ago. It no longer uses string
lookups, is pure XSLT 1.0 and will not loop infinitely in case
of circular dependencies. The trick is to carefully select
elements from the document into variables so that they are
node sets and cen be selected later on. The List was a great
help in developing the right ideas. Training in formal logic
and predicate calculus helped too, and i'm somewhat sorry
that i have not yet answered Peter West's post from 2000-11-12.

The complete problem is stated in an earlier post (2000-11-04)
and can be found in the archive.

Pseudocode:
  select structs with no dependencies
  process them
  repeat
    if not all structs are processed
      select structs which are
        not processed
        have only dependencies which are processed
      if empty
        stop
      else
        process them
  done

This translates into the following stylesheet:

<?xml version="1.0" encoding="ISO-8859-1"?>
<xsl:stylesheet version="1.0"
                xmlns:xsl="http://www.w3.org/1999/XSL/Transform";>
  <xsl:output method="text"/>
  
  <xsl:template match="structs">
    <xsl:call-template name="process">
      <xsl:with-param name="nodes" select="struct[not(field/type/ref)]"/>
      <xsl:with-param name="finished" select="/.."/>
    </xsl:call-template>
  </xsl:template>

  <xsl:template name="process">
    <xsl:param name="nodes"/>
    <xsl:param name="finished"/>
    <xsl:variable name="processed" select="$nodes|$finished"/>
    <xsl:for-each select="$nodes">
      <xsl:value-of select="name"/>
    </xsl:for-each>
    <xsl:if test="count(struct)>count($processed)">
      <xsl:variable name="nextnodes"
         select="struct[not($processed/name=name)
                 and count(field/type/ref)=count(field/type/ref[$processed/name=.])]"/>
      <xsl:if test="$nextnodes">
        <xsl:call-template name="process">
          <xsl:with-param name="nodes" select="$nextnodes"/>
          <xsl:with-param name="finished" select="$processed"/>
        </xsl:call-template>
      </xsl:if>
    </xsl:if>
  </xsl:template>

</xsl:stylesheet>

The structs are processed in increasing distance from leaves in the
dependency graph.
Can one of the gurus please comment on the "count(field/type/ref)=count(...)"
construct, and whether this could be substituted by a possibly more
efficient condition? In my real world examples with some 200+ structs
it takes quite some time, if there are cheap optimisations i would
appreciate it.
Applying the stylesheet to the following example document gives the
expected result of
 ACBED

<?xml version="1.0" encoding="ISO-8859-1"?>
<!DOCTYPE structs [

<!ELEMENT structs (struct*)>
<!ELEMENT struct (name,field*)>
<!ELEMENT field (name,type)>
<!ELEMENT name (#PCDATA)>
<!ELEMENT type (ref|long)>
<!ELEMENT ref (#PCDATA)>
<!ELEMENT long EMPTY>
]>

<structs>
  <struct>
    <name>A</name>
    <field>
      <name>A1</name>
      <type><long/></type>
    </field>
  </struct>
  <struct>
    <name>B</name>
    <field>
      <name>B1</name>
      <type><ref>A</ref></type>
    </field>
    <field>
      <name>B2</name>
      <type><ref>C</ref></type>
    </field>
  </struct>
  <struct>
    <name>C</name>
    <field>
      <name>C1</name>
      <type><long/></type>
    </field>
  </struct>
  <struct>
    <name>D</name>
    <field>
      <name>D1</name>
      <type><ref>E</ref></type>
    </field>
    <field>
      <name>D2</name>
      <type><ref>A</ref></type>
    </field>
  </struct>
  <struct>
    <name>E</name>
    <field>
      <name>E1</name>
      <type><ref>C</ref></type>
    </field>
  </struct>
</structs>

Will this make it into the FAQ? <grin>

Regards
J.Pietschmann

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