Re: Seeking an elegant implementation of a graph trav

Play the video

Subject: Re: Seeking an elegant implementation of a graph traversal
From: Martin Honnen <Martin.Honnen@xxxxxx>
Date: Sat, 08 Oct 2011 18:49:59 +0200

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
Seeking an elegant implementation of a graph traversal Costello, Roger L. - 8 Oct 2011 16:06:04 -0000 Martin Honnen - 8 Oct 2011 16:50:11 -0000 <= Costello, Roger L. - 8 Oct 2011 18:04:07 -0000 TW - 8 Oct 2011 20:01:06 -0000 Michael Kay - 8 Oct 2011 23:01:33 -0000 Dimitre Novatchev - 9 Oct 2011 01:37:37 -0000

<- Previous	Index	Next ->
Seeking an elegant implementa, Costello, Roger L.	Thread	RE: Seeking an elegant implem, Costello, Roger L.
Seeking an elegant implementa, Costello, Roger L.	Date	RE: Seeking an elegant implem, Costello, Roger L.
	Month

PURCHASE STYLUS STUDIO ONLINE TODAY!

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

Download The World's Best XML IDE!

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

Subscribe in XML format

RSS 2.0
Atom 0.3

XML Editor - Download a 15 Day Free Trial Now >

See What's New in Stylus Studio >

Buy Stylus Studio - XML Editor - Now >