OASIS Mailing List ArchivesView the OASIS mailing list archive below
or browse/search using MarkMail.


Help: OASIS Mailing Lists Help | MarkMail Help

[Date Prev] | [Thread Prev] | [Thread Next] | [Date Next] -- [Date Index] | [Thread Index]
An elegant implementation of an XML graph traversal

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


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

    <Section id="A">
        <Include idref="B" />
        <Include idref="C" />
    <Section id="B">
        <Include idref="D" />
    <Section id="C">
        <Include idref="D" />
    <Section id="D">
        <Include idref="A" />
    <Section id="E" />

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?


Here is the extraordinary solution, provided by Martin Honnen:

   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: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=", "/>


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.

[Date Prev] | [Thread Prev] | [Thread Next] | [Date Next] -- [Date Index] | [Thread Index]

News | XML in Industry | Calendar | XML Registry
Marketplace | Resources | MyXML.org | Sponsors | Privacy Statement

Copyright 1993-2007 XML.org. This site is hosted by OASIS