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

[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/