Subject: RE: [xsl] Seeking an elegant implementation of a graph traversal From: "Costello, Roger L." <costello@xxxxxxxxx> Date: Sat, 8 Oct 2011 18:03:50 +0000 |
Martin Honnen wrote: > With XSLT 2.0 I have tried > > <xsl:stylesheet > -- snip -- > </xsl:stylesheet> Wow! Wow! Wow! Martin, that is an extraordinary solution. It is incredibly elegant. Thank you very, very much. /Roger -----Original Message----- From: Martin Honnen [mailto:Martin.Honnen@xxxxxx] Sent: Saturday, October 08, 2011 12:50 PM To: xsl-list@xxxxxxxxxxxxxxxxxxxxxx Subject: Re: [xsl] Seeking an elegant implementation of a graph traversal Costello, Roger L. wrote: > 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. Do you want a particular output order? > 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? With XSLT 2.0 I have tried <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. -- Martin Honnen --- MVP Data Platform Development http://msmvps.com/blogs/martin_honnen/
Current Thread |
---|
|
<- Previous | Index | Next -> |
---|---|---|
Re: [xsl] Seeking an elegant implem, Martin Honnen | Thread | Re: [xsl] Seeking an elegant implem, TW |
Re: [xsl] Seeking an elegant implem, Martin Honnen | Date | Re: [xsl] Seeking an elegant implem, TW |
Month |