Re: [xsl] Seeking an elegant implementation of a graph traversal

[TW <zupftom@xxxxxxxxxxxxxx>]

Just for sports, an XSLT 1.0 version (mis)using string manipulation:

<?xml version="1.0"?>
<stylesheet xmlns="http://www.w3.org/1999/XSL/Transform"; version="1.0">
  <output method="text"/>
  <key name="sec-by-id" match="Section" use="@id"/>

  <param name="search" select="'A'"/>

  <template match="Include">
    <param name="found-sections"/>
    <if test="not(contains($found-sections,concat(' ',@idref,' ')))">
      <value-of select="concat(@idref,' ')"/>
      <apply-templates select="key('sec-by-id',@idref)/Include">
        <with-param name="found-sections"
select="concat($found-sections,@id,' ')"/>
      </apply-templates>
    </if>
  </template>

  <template name="sort-out-duplicates">
    <!-- $space-separated-items has space after every item, like "A B C D "
-->
    <param name="space-separated-items"/>
    <variable name="first-item"
select="substring-before($space-separated-items,' ')"/>
    <!-- $remaining-items has leading space and space after every
item, like " B C D " -->
    <variable name="remaining-items"
select="substring-after($space-separated-items,$first-item)"/>

    <if test="not(contains($remaining-items,concat(' ',$first-item,' ')))">
      <value-of select="$first-item"/>
      <if test="$remaining-items != ' '">
        <value-of select="', '"/>
      </if>
    </if>
    <if test="$remaining-items != ' '">
      <call-template name="sort-out-duplicates">
        <with-param name="space-separated-items"
select="substring($remaining-items,2)"/>
      </call-template>
    </if>
  </template>

  <template match="/">
    <variable name="ids-with-duplicates">
      <value-of select="concat($search,' ')"/>
      <apply-templates select="key('sec-by-id',$search)/Include">
        <with-param name="found-sections" select="concat(' ',$search,' ')"/>
      </apply-templates>
    </variable>
    <call-template name="sort-out-duplicates">
      <with-param name="space-separated-items"
select="$ids-with-duplicates"/>
    </call-template>
  </template>

</stylesheet>


2011/10/8 Martin Honnen <Martin.Honnen@xxxxxx>:
> Costello, Roger L. wrote:
>
>> I have a Document consisting of a bunch of Sections. Each Section has a
>> unique identifier. Each Section may reference other Sections via an
Include
>> element, e.g.,
>>
>> <Document>
>>     <Section id="A">
>>         <Include idref="B" />
>>         <Include idref="C" />
>>     </Section>
>>     <Section id="B">
>>         <Include idref="D" />
>>     </Section>
>>     <Section id="C">
>>         <Include idref="D" />
>>     </Section>
>>     <Section id="D">
>>         <Include idref="A" />
>>     </Section>
>>     <Section id="E" />
>> </Document>
>>
>> Problem: Write a function and pass a Section to it. The function outputs
>> the Section and all the Sections it Includes and all the Sections each of
>> them Includes, and so on.
>>
>> Be sure there are no duplicates in the output.
>
> Do you want a particular output order?
>
>> Example: invoke the function with Section A. Here's the output:
>>
>> A, B, C, D
>>
>> Is there an elegant XSLT implementation of this graph traversal problem?
>
> With XSLT 2.0 I have tried
>
> <xsl:stylesheet
>  xmlns:xsl="http://www.w3.org/1999/XSL/Transform";
>  xmlns:xs="http://www.w3.org/2001/XMLSchema";
>  xmlns:mf="http://example.com/mf";
>  version="2.0"
>  exclude-result-prefixes="xs mf">
>
>  <xsl:param name="search" as="xs:string" select="'A'"/>
>
>  <xsl:output method="text"/>
>
>  <xsl:key name="sec-by-id" match="Section" use="@id"/>
>
>  <xsl:function name="mf:find-sections" as="element(Section)+">
>    <xsl:param name="start" as="element(Section)"/>
>    <xsl:param name="found" as="element(Section)+"/>
>    <xsl:variable name="includes" as="element(Section)*"
> select="key('sec-by-id', $start/Include/@idref, root($start))"/>
>    <xsl:sequence select="$start | ($includes except
> $found)/mf:find-sections(., . | $found)"/>
>  </xsl:function>
>
>  <xsl:template match="/">
>    <xsl:variable name="start" as="element(Section)"
select="key('sec-by-id',
> $search)"/>
>    <xsl:value-of select="mf:find-sections($start, $start)/@id" separator=",
> "/>
>  </xsl:template>
>
> </xsl:stylesheet>
>
> and for your sample input both Saxon 9.3 as well as AltovaXML output "A, B,
> C, D". The stylesheet exploits that the "union" operator "|" eliminates
> duplicates. Output order should be input document order that way.
>
>
>
>
>
> --
>
>        Martin Honnen --- MVP Data Platform Development
>        http://msmvps.com/blogs/martin_honnen/