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

["Costello, Roger L." <costello@xxxxxxxxx>]

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.Honnen@xxxxxx]
Sent: Saturday, October 08, 2011 12:50 PM
To: xsl-list@xxxxxxxxxxxxxxxxxxxxxx
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/