[XSL-LIST Mailing List Archive Home] [By Thread] [By Date] [Recent Entries] [Reply To This Message]

Re: Seeking an elegant implementation of a graph trav

Subject: Re: Seeking an elegant implementation of a graph traversal
From: TW <zupftom@xxxxxxxxxxxxxx>
Date: Sat, 8 Oct 2011 22:00:55 +0200
Re:  Seeking an elegant implementation of a graph  trav
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/

Current Thread

PURCHASE STYLUS STUDIO ONLINE TODAY!

Purchasing Stylus Studio from our online shop is Easy, Secure and Value Priced!

Buy Stylus Studio Now

Download The World's Best XML IDE!

Accelerate XML development with our award-winning XML IDE - Download a free trial today!

Don't miss another message! Subscribe to this list today.
Email
First Name
Last Name
Company
Subscribe in XML format
RSS 2.0
Atom 0.3
Site Map | Privacy Policy | Terms of Use | Trademarks
Free Stylus Studio XML Training:
W3C Member
Stylus Studio® and DataDirect XQuery ™are products from DataDirect Technologies, is a registered trademark of Progress Software Corporation, in the U.S. and other countries. © 2004-2013 All Rights Reserved.