[XSL-LIST Mailing List Archive Home] [By Thread] [By Date] [Recent Entries] [Reply To This Message]

topological sort

Subject: topological sort
From: Joerg Pietschmann <joerg.pietschmann@xxxxxx>
Date: Sat, 04 Nov 2000 14:48:13 +0100
topological sort
Hello,
i want to implement a topological sort in XSLT. This is necessary
for generating program code (IDL for example) out of an XML file
which contains a specification for program structures, like the following:

<!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>
  </struct>
  <struct>
    <name>E</name>
    <field>
      <name>E1</name>
      <type><ref>C</ref></type>
    </field>
  </struct>
</structs>


The data types for structure fields may refer to other structures.
Programming languages usually require the structures alredy defined
before they can be referenced. I don't want to put the burden on the
user to enter the specifications in proper order.
Preferably the algorithm should not be confused by reference loops.

The usual algorithm is to walk the dependencies while keeping a list
with already processed structure definitions. This, however requires
assignable variables for bookkeeping.
Another solution is to output the structures at levels of increasing
distance from the leaves in the dependency graph. This can be implemented
in XSLT but it is somewhat unelegant.

Some pseudo code for orientation:

processed_list=nil
template process
  generate structures which are not in the processed_list
                      and only refer to structure types not in the processed_list
  add the structure to the processed list
  call process

The recursion may be terminated either if the processed list contains all
structures (equivalently if it is exactly as long as the list with all
structures) or if no more structures has been processed in a step.
The first condition alone is not sufficient in case of loops which are
stopped by the second condition, however, the second condition alone
imposes an extra step. The following stylesheet uses only the second
condition. The concatenations with the double colons should guard against
spurious substring matches.

<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="processed" select="':'"/>
    </xsl:call-template>
  </xsl:template>

  <xsl:template name="process">
    <xsl:param name="processed"/>
    <xsl:for-each select="/structs/struct[not(contains($processed,concat(':',name,':')))
 and count(field[count(type/ref)>0 and not(contains($processed,concat(':',./type/ref,':')))])=0]">
      <xsl:value-of select="./name"/>
    </xsl:for-each>
    <xsl:variable name="actualprocessed">
      <xsl:for-each select="/structs/struct[not(contains($processed,concat(':',name,':')))
 and count(field[count(type/ref)>0 and not(contains($processed,concat(':',./type/ref,':')))])=0]">
        <xsl:value-of select="concat(./name,':')"/>
      </xsl:for-each>
    </xsl:variable>
    <xsl:if test="string-length($actualprocessed)>0">
      <xsl:call-template name="process">
        <xsl:with-param name="processed" select="concat($processed,$actualprocessed)"/>
      </xsl:call-template>
    </xsl:if>
  </xsl:template>

</xsl:stylesheet>

This outputs "ACBED" which is the correct dependency order.

Is there a better solution, or can the stylesheet be improved?
What bothers me most is that the struct elements must be processed twice,
one for output and again for updating the processed_list.

Thanks for help

J.Pietschmann

-- 

----------------------------------------------------------------------
Zuercher Kantonalbank ZKB        Internet : joerg.pietschmann@xxxxxx
Neue Hard 9                      Telefon  : ++41 01-275 85 03 
Postfach                         Fax      : ++41 01-275 80 34
CH-8010 Zuerich
----------------------------------------------------------------------


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


Current Thread

PURCHASE STYLUS STUDIO ONLINE TODAY!

Purchasing Stylus Studio from our online shop is Easy, Secure and Value Priced!

Buy Stylus Studio Now

Download The World's Best XML IDE!

Accelerate XML development with our award-winning XML IDE - Download a free trial today!

Don't miss another message! Subscribe to this list today.
Email
First Name
Last Name
Company
Subscribe in XML format
RSS 2.0
Atom 0.3
Site Map | Privacy Policy | Terms of Use | Trademarks
Free Stylus Studio XML Training:
W3C Member
Stylus Studio® and DataDirect XQuery ™are products from DataDirect Technologies, is a registered trademark of Progress Software Corporation, in the U.S. and other countries. © 2004-2013 All Rights Reserved.