Re[2]: topological sort

Subject: Re[2]: topological sort
From: Jeni Tennison <mail@xxxxxxxxxxxxxxxx>
Date: Fri, 10 Nov 2000 12:47:11 +0000
Joerg & Peter,

>> I suspect that something useful could be done with keys here, but I have
>> no idea what.
>
> Me too. Can one of the gurus please enlighten us? Is there another
> algorithm which doesn't use string lists for bookkeeping? Should i
> rearrange my XML structure to make a more efficient algorithm feasible?
> I'm still waiting for any ideas.

I don't know whether you'll be satisfied with this solution.  It's not
as nicely logical as yours are, but you might find it interesting as a
different take on the problem.  It's not a pure XSLT 1.0 solution,
because it uses the node-set extension function, but I don't feel bad
about doing that any more, and it's a good example of how much better
XSLT life will be when it enters the main stream in XSLT 1.1.

First, I build a summary of the dependencies throughout the structs.
For each of the structs, I build an XML summary that lists *all* the
other structs its dependant on.  So, for example, struct C gives:

  <dependant name="D"><on>E</on><on>C</on></dependant>

Building this structure is a matter of recursively finding the
dependants for a particular struct.  There is a use of keys here.  I
define a key so that I can jump from the value of the ref in a field
to the struct that has that name:

<xsl:key name="structs" match="struct" use="name" />

So, for example, when I'm looking at struct E, and I see that it has a
field/type/ref equal to 'C', then I use:

  key('structs', 'C') [i.e. key('structs', field/type/ref)]

to give me the struct element whose name is 'C'.

The templates that build the summary structure are:

<xsl:template match="struct">
   <dependant name="{name}">
      <xsl:apply-templates select="field/type/ref" />
   </dependant>
</xsl:template>

<xsl:template match="ref">
   <on><xsl:value-of select="." /></on>
   <xsl:apply-templates select="key('structs', .)/field/type/ref" />
</xsl:template>

[Note this recursion goes infinite if there are circular references.
You could prevent that with a template that tested whether a
particular struct is dependent on itself.]

Once this structure is built, then you can use it to construct your
list of dependencies.  As a simple approach, I just sorted the list of
the generated 'dependant' elements according to the number of structs
they were dependent on, and outputted that.

<xsl:template match="structs">
   <xsl:variable name="dependencies-rtf">
      <xsl:apply-templates />
   </xsl:variable>
   <xsl:variable name="dependencies"
                 select="saxon:node-set($dependencies-rtf)/dependant" />
   <xsl:for-each select="$dependencies">
      <xsl:sort select="count(on)" />
      <xsl:value-of select="@name" />
   </xsl:for-each>
</xsl:template>

The result with the example you gave was ACEBD, which might not be as
logical an order as ACBED but is still logically correct. Naturally,
you could perform further transformations on the generated structure
instead.

I hope this gives you some ideas for alternative approaches,

Jeni

---
Jeni Tennison
http://www.jenitennison.com/



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


Current Thread