RE: An elegant implementation of an XML graph traversal

["Costello, Roger L." <costello@mitre.org>]

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?

/Roger

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

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.


_______________________________________________________________________

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