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@[...].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