[XSL-LIST Mailing List Archive Home] [By Thread] [By Date]

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


Subject: Re: [xsl] Seeking an elegant implementation of a graph traversal
From: Michael Kay <mike@xxxxxxxxxxxx>
Date: Sun, 09 Oct 2011 00:01:19 +0100

If you have a copy of my book, you'll find an example on page 251 (4th ed).

If you're looking for elegance, then one nice feature of my code is that the code for graph traversal (and checking for cycles) is parameterized by a function that establishes how the relation between nodes is established (in your case, by following the idref/id foreign key). This approach will work even better of course with first-class functions as offered in XPath 3.0.

Michael Kay
Saxonica

On 08/10/2011 17:05, Costello, Roger L. wrote:
Hi Folks,

I am seeking an elegant XSLT implementation for the following problem.

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.

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?

/Roger


Current Thread
Keywords