[xsl] Re: The Solution -- Re: how to rearrange nodes based on a dependency graph?

[Gunther Schadow <gunther at aurora dot regenstrief dot org>]

Wow, thanks Dimitre, this looks exactly right! And so much more
elegant than what I have been fiddling with! I had been close
to banging my "nodes-seen" list into XSL but your solution is
so much better!

Thanks,
-Gunther

Dimitre Novatchev wrote:

> 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
> 


-- 
Gunther Schadow, M.D., Ph.D.                    gschadow@regenstrief.org
Medical Information Scientist      Regenstrief Institute for Health Care
Adjunct Assistant Professor        Indiana University School of Medicine
tel:1(317)630-7960                         http://aurora.regenstrief.org



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