Subject: Re: [xsl] Seeking an elegant implementation of a graph traversal From: TW <zupftom@xxxxxxxxxxxxxx> Date: Sat, 8 Oct 2011 22:00:55 +0200 |
Just for sports, an XSLT 1.0 version (mis)using string manipulation: <?xml version="1.0"?> <stylesheet xmlns="http://www.w3.org/1999/XSL/Transform" version="1.0"> <output method="text"/> <key name="sec-by-id" match="Section" use="@id"/> <param name="search" select="'A'"/> <template match="Include"> <param name="found-sections"/> <if test="not(contains($found-sections,concat(' ',@idref,' ')))"> <value-of select="concat(@idref,' ')"/> <apply-templates select="key('sec-by-id',@idref)/Include"> <with-param name="found-sections" select="concat($found-sections,@id,' ')"/> </apply-templates> </if> </template> <template name="sort-out-duplicates"> <!-- $space-separated-items has space after every item, like "A B C D " --> <param name="space-separated-items"/> <variable name="first-item" select="substring-before($space-separated-items,' ')"/> <!-- $remaining-items has leading space and space after every item, like " B C D " --> <variable name="remaining-items" select="substring-after($space-separated-items,$first-item)"/> <if test="not(contains($remaining-items,concat(' ',$first-item,' ')))"> <value-of select="$first-item"/> <if test="$remaining-items != ' '"> <value-of select="', '"/> </if> </if> <if test="$remaining-items != ' '"> <call-template name="sort-out-duplicates"> <with-param name="space-separated-items" select="substring($remaining-items,2)"/> </call-template> </if> </template> <template match="/"> <variable name="ids-with-duplicates"> <value-of select="concat($search,' ')"/> <apply-templates select="key('sec-by-id',$search)/Include"> <with-param name="found-sections" select="concat(' ',$search,' ')"/> </apply-templates> </variable> <call-template name="sort-out-duplicates"> <with-param name="space-separated-items" select="$ids-with-duplicates"/> </call-template> </template> </stylesheet> 2011/10/8 Martin Honnen <Martin.Honnen@xxxxxx>: > 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, Costello, Roger L. | Thread | Re: [xsl] Seeking an elegant implem, Michael Kay |
RE: [xsl] Seeking an elegant implem, Costello, Roger L. | Date | Re: [xsl] Seeking an elegant implem, Michael Kay |
Month |