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

The Solution -- Re: how to rearrange nodes based on a

Subject: The Solution -- Re: how to rearrange nodes based on a dependency graph?
From: Dimitre Novatchev <dnovatchev@xxxxxxxxx>
Date: Fri, 21 Dec 2001 07:20:06 -0800 (PST)
how to rearrange id
Hi Gunther,

If I'm not wrong, this problem is a case of the "topological sort" problem.

The solution bellow arranges the DAG into levels of hierarchy -- the nodes that do
not depend on other nodes are at the top, the nodes that depend ***only*** on the
nodes in the sorted hierarchy (up to this moment) form the next level of the
hierarchy.

Suppose that we have the following source xml document:

<document xml:space="preserve">
    <frag id='1'>
        <requires>2</requires>
        <requires>3</requires>
    </frag>

    <frag id='2'>
        <requires>4</requires>
        <requires>5</requires>
    </frag>

    <frag id='3'>
        <requires>5</requires>
    </frag>

    <frag id='4' />

    <frag id='5' />
</document>

The hierarchical representation is:

      1
     / \
    2   3
   / \ /
  4   5


And here's the stylesheet:

<xsl:stylesheet version="1.0" xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
xmlns:msxsl="urn:schemas-microsoft-com:xslt">
  <xsl:output indent="yes" omit-xml-declaration="yes"/>
  <xsl:template match="/">
    <xsl:call-template name="topSort">
      <xsl:with-param name="pSorted" select="/*/frag[not(requires)]"/>
      <xsl:with-param name="pUnsorted" select="/*/frag[requires]"/>
    </xsl:call-template>
  </xsl:template>
  
  <xsl:template name="topSort">
    <xsl:param name="pSorted" select="/.."/>
    <xsl:param name="pUnsorted" select="/.."/>

    <xsl:variable name="vNextLevel"
                  select="$pUnsorted[not(requires[not(. = $pSorted/@id)])]"/>
    <xsl:choose>
      <xsl:when test="not($vNextLevel)">
        <xsl:copy-of select="$pSorted"/>
      </xsl:when>
      <xsl:otherwise>
        <xsl:variable name="vrtfNewSorted">
          <xsl:copy-of select="$pSorted"/>
          <xsl:copy-of select="$vNextLevel"/>
        </xsl:variable>

        <xsl:variable name="vCntNextLevel" select="count($vNextLevel)"/>
        <xsl:variable name="vNewUnsorted"
                      select="$pUnsorted[not(@id = $vNextLevel/@id)] "/>
        <xsl:call-template name="topSort">
          <xsl:with-param name="pSorted" select="msxsl:node-set($vrtfNewSorted)/*"/>
          <xsl:with-param name="pUnsorted" select="$vNewUnsorted"/>
        </xsl:call-template>

      </xsl:otherwise>
    </xsl:choose>
  </xsl:template>
</xsl:stylesheet>

When applied on the above xml source document, the result of the transformation is:

<frag id="4" />
<frag id="5" />
<frag id="2">
        <requires>4</requires>
        <requires>5</requires>
</frag>
<frag id="3">
        <requires>5</requires>
</frag>
<frag id="1">
        <requires>2</requires>
        <requires>3</requires>
</frag>


The tricky part is to express in a single XPath expression the nodes that will form
the next level:

<xsl:variable name="vNextLevel"
              select="$pUnsorted[not(requires[not(. = $pSorted/@id)])]"/>

This is: all elements from $pUnsorted, which do not have any "requires" child that
is not equal to the "id" of one of the elements in the sorted hierarchy $pSorted.

Hope that this really helped.

Cheers,
Dimitre Novatchev.



Gunther Schadow <gunther at aurora dot regenstrief dot org> wrote:
--------------------------------------------------------------------------------

Hi XSL listers,

I'm hung up on a puzzling problem and need your help. I am
relatively new to XSL but thanks to the pretty readable
specification and some example I was so far able to find
my way. Except when I wanted to be really clever, like here.

The purpose of what I'm doing is kind of what you might
know as "literal programming." It's writing a document
that explains the detail of some formal language utterance,
such as a program, or an XML schema or an IDL specification
or whatever have you. The document is to be written for
readability and may well have a different flow than what's
required for the formal language (program or xsd or whatever.)
For example, in describing a Pascal program, I might want to
discuss an outline of the main program first before I go
into the detail of the procedures. Yet in the program text,
the procedures need to come before the main program. The
point of course is that the text document should be the main
focus of development and maintenance, and the program text
should be generated from there. That's where XSLT comes
in and falls short? (you tell me if it does of if I fall
short :-)

Here is an example. This XML instance discusses a mocked up
up XML schema for defining some data.


<document>

Blah bla

<frag id='1' requires='2'>
    BEGIN
      DoSomethingUseful();
    END
</frag>

Blah blah

<frag id='2'>
   PROCEDURE DoSomethingUseful
   BEGIN
     ...
   END
</frag>

</document>




The <frag> tag has an 'id' (ID) attribute with matching
'requires' (IDREFS) attribute.

The XSL templates will go through the document and discard
everything, except when encountering a fragment. It will
then will hunt down the requires idrefs to find other
fragments that should come first. Of course, if a fragment has
already been emitted, it shouldn't appear again. And that't
really my big problem.

Here is my XSL so far:

<xsl:key name='fragkey' match='frag' use='@id' />

<xsl:template match='frag'>
   <xsl:for-each select='@requires'>
     <xsl:apply-templates select="key('fragkey',.)"/>
   </xsl:for-each>

   <xsl:for-each select='*'>
     <xsl:call-template name='copy-stuff'/>
   </xsl:for-each>
</xsl:template>

<xsl:template name='copy-stuff'>
   <xsl:copy>
     <xsl:for-each select='@*|*'>
       <xsl:call-template name='copy-stuff'/>
     </xsl:for-each>
   </xsl:copy>
</xsl:template>



This works nicely, except for the fact that fragment number 2
is emitted twice, first as the dependency of fragment 1 and
then because it appears as the next fragment in the document.
(Similarly this runs amok if there's a circular dependency.)

I tried to use a variable as a check-off list of fragments
already emitted, but that's not possible because XSL "variables"
are actually constants. When I try to write such a function
in LISP without using global variables and side effects, it
get's pretty difficult and the only way to survive here is
because I can examine return values. In XSL, I cannot examine
the output tree, or can I?

Any suggestions are appreciated. Of course I can dumb down
this system and instead of requirement links I could use
some kind of sequence number or forward linking and sort by
that etc. But I feel that the dependency graph is the most
appropriate way to represent this and if XSL is a complete
functional language it should have some way to deal with that.

regards,
-Gunther




__________________________________________________
Do You Yahoo!?
Check out Yahoo! Shopping and Yahoo! Auctions for all of
your unique holiday gifts! Buy at http://shopping.yahoo.com
or bid at http://auctions.yahoo.com

 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.