Re: Ordering of Blocks based on Input/Output

Dan Diebolt wrote:
> 
> Starting from B1, there are only two ways to order the
> blocks so that each Block's inputs are provided by a
> proceeding Block's output:
> 
> B1 , B2 , B3 , B4 , B5
> B1 , B3 , B2 , B4 , B5
> 
> My problem is to produce *one* such feasible ordering of
> the blocks. 

The attached seems fairly efficient.

Hope this helps - a fun challenge at the end of the day!

Francis.

C:\xml>type t.xslt
<?xml version="1.0" encoding="UTF-8"?>
<xsl:stylesheet version="1.0"
xmlns:xsl="http://www.w3.org/1999/XSL/Transform">
  <xsl:output method="xml" version="1.0" encoding="UTF-8" indent="yes"/>
  <xsl:template match="/">
    <order>
      <!-- call the order function with the parameters -->
      <xsl:call-template name="order">
        <xsl:with-param name="done" select="/.."/>
        <xsl:with-param name="todo" select="/root/system/block/name"/>
      </xsl:call-template>
    </order>
  </xsl:template>
  <!-- recurse through this printing out one block at a time -->
  <xsl:template name="order">
    <xsl:param name="done"/>
    <xsl:param name="todo"/>
    <!-- always need a terminate condition in recursive functions -->
    <xsl:if test="count($todo) > 0">
      <!-- links into todo -->
      <xsl:variable name="into"
select="/root/system/connect[input/@block = $todo]"/>
      <!-- find first block $todo that has no inputs from any (other)
block in $todo -->
      <xsl:variable name="next" select="$todo[. !=
$into/output/@block][1]"/>
      <!-- now copy it out -->
      <xsl:copy-of select="$next"/>
      <!-- now recurse with $next transferred from $todo to $done -->
      <xsl:call-template name="order">
        <xsl:with-param name="done" select="$done | $next"/>
        <xsl:with-param name="todo" select="$todo[generate-id(.) !=
generate-id($next)]"/>
      </xsl:call-template>
    </xsl:if>
  </xsl:template>
</xsl:stylesheet>

C:\xml>saxon t.xml t.xslt
<?xml version="1.0" encoding="UTF-8"?>
<order>
   <name>B1</name>
   <name>B2</name>
   <name>B3</name>
   <name>B4</name>
   <name>B5</name>
</order>
C:\xml>

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