xsl-list
[Top] [All Lists]

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

2011-10-08 13:04:07
Martin Honnen wrote:

With XSLT 2.0 I have tried

<xsl:stylesheet
    -- snip --
</xsl:stylesheet>

Wow! Wow! Wow!

Martin, that is an extraordinary solution. It is incredibly elegant.

Thank you very, very much.

/Roger


-----Original Message-----
From: Martin Honnen [mailto:Martin(_dot_)Honnen(_at_)gmx(_dot_)de] 
Sent: Saturday, October 08, 2011 12:50 PM
To: xsl-list(_at_)lists(_dot_)mulberrytech(_dot_)com
Subject: Re: [xsl] Seeking an elegant implementation of a graph traversal

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/

--~------------------------------------------------------------------
XSL-List info and archive:  http://www.mulberrytech.com/xsl/xsl-list
To unsubscribe, go to: http://lists.mulberrytech.com/xsl-list/
or e-mail: <mailto:xsl-list-unsubscribe(_at_)lists(_dot_)mulberrytech(_dot_)com>
--~--


--~------------------------------------------------------------------
XSL-List info and archive:  http://www.mulberrytech.com/xsl/xsl-list
To unsubscribe, go to: http://lists.mulberrytech.com/xsl-list/
or e-mail: <mailto:xsl-list-unsubscribe(_at_)lists(_dot_)mulberrytech(_dot_)com>
--~--