This is the mail archive of the
xsl-list@mulberrytech.com
mailing list .
Re: topological sort
- To: XSL List <xsl-list at lists dot mulberrytech dot com>
- Subject: [xsl] Re: topological sort
- From: Joerg Pietschmann <joerg dot pietschmann at zkb dot ch>
- Date: Fri, 05 Jan 2001 09:47:44 +0100
- Organization: ZKB
- Reply-To: xsl-list at lists dot mulberrytech dot com
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