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]
RE: An elegant implementation of an XML graph traversal

Hi Folks,

As I examine Martin's solution to the problem of traversing an XML graph, it occurs to me that it may be possible to abstract his particular implementation to a declarative (inductive) definition. Here's a go at it: 

("start" is a Section, the minus is set subtraction)

ReachableSections ( start ) =

1. if start has no Includes then start

2. else (start,  ReachableSections ( i ) <- ({union start's Included Sections} - start))

I think this is correct (maybe not). I invented my own notation, perhaps you can create a definition that uses a more standardized notation?


-----Original Message-----
From: Costello, Roger L. [mailto:costello@mitre.org] 
Sent: Saturday, October 08, 2011 2:20 PM
To: xml-dev@lists.xml.org
Subject: [xml-dev] 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.


XML-DEV is a publicly archived, unmoderated list hosted by OASIS
to support XML implementation and development. To minimize
spam in the archives, you must subscribe before posting.

[Un]Subscribe/change address: http://www.oasis-open.org/mlmanage/
Or unsubscribe: xml-dev-unsubscribe@lists.xml.org
subscribe: xml-dev-subscribe@lists.xml.org
List archive: http://lists.xml.org/archives/xml-dev/
List Guidelines: http://www.oasis-open.org/maillists/guidelines.php

[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