[XML-DEV Mailing List Archive Home] [By Thread] [By Date] [Recent Entries] [Reply To This Message]

An elegant implementation of an XML graph traversal

• From: "Costello, Roger L." <costello@mitre.org>
• To: "xml-dev@lists.xml.org" <xml-dev@lists.xml.org>
• Date: Sat, 8 Oct 2011 18:19:49 +0000

Hi Folks,

Recall that, while an XML document is sometimes a tree, in the general case it is a graph. And that graph may have loops. In traversing the graph, how does one avoid getting trapped in an infinite loop? Below is an example of an XML document that is a graph. The problem is to start at an element and traverse outward, without getting trapped in a loop. After the description of the problem is an extraordinary solution provided by Martin Honnen.  /Roger

PROBLEM DESCRIPTION

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?

PROBLEM SOLUTION

Here is the extraordinary solution, provided by Martin Honnen:

<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.

• Follow-Ups:
  • Re: An elegant implementation of an XML graph traversal
    • From: Richard Salz <rsalz@us.ibm.com>