Subject: Re: graph traversal From: "Nikolai Grigoriev" <grig@xxxxxxx> Date: Sat, 19 Feb 2000 23:45:20 +0300 |
Hi! Jeff Lansing wrote: >How can I traverse a graph with XSL? There was a lot of discussion about the XSLT power, so I felt kinda challenged to write a graph traversal stylesheet. Given below are my humble results. The stylesheet operates on files of the kind described in the original letter by Jeff Lansing. It lists files reachable from the top node, ordering them by the number of hyperlink transitions required to get there from the root. (It is not exactly the same as was requested; I have chosen the simplest output, to avoid stylesheet overgrowth). The output looks like this (in Jeff's case): Level 1: left_branch.html right_branch.html Level 2: leaf.html The whole thing uses no extensions to XSLT REC, and has been tested under SAXON and XT. Sure enough, it isn't a complete graph traversal engine: it may choke on files distributed in multiple directories, it produces a spurious reference to root.html (since there is no info about the initial path), etc. Nevertheless, I think the possibility to traverse the graph has been proven, and the rest of functionality is easy to incorporate. Regards, Nikolai ================================================== <xsl:stylesheet version="1.0" xmlns:xsl="http://www.w3.org/1999/XSL/Transform"> <xsl:output method="text" encoding="ISO-8859-1"/> <xsl:param name="delimiter" select="'|'"/> <xsl:variable name="separator" select="concat ($delimiter, $delimiter)"/> <!-- ===================================================== --> <!-- Top template: get a list of links and start recursion --> <!-- ===================================================== --> <xsl:template match="/"> <!-- collect links for the first level --> <xsl:variable name="links"> <xsl:apply-templates select="html"/> </xsl:variable> <!-- start recursion --> <xsl:call-template name="visit-node-list"> <xsl:with-param name="level" select="1"/> <xsl:with-param name="node-list" select="$links"/> <xsl:with-param name="visited-nodes" select="$links"/> </xsl:call-template> </xsl:template> <!-- ===================================================== --> <!-- Extract unique unvisited links from a document. --> <!-- Names of visited nodes are stored in a string; --> <!-- $delimiter is prepended and appended to every entry --> <!-- ===================================================== --> <xsl:template match="html"> <xsl:param name="visited-nodes"/> <xsl:message>Processing node <xsl:value-of select="@version"/></xsl:message> <xsl:for-each select=".//a"> <xsl:variable name="link" select="@href"/> <xsl:variable name="link-record" select="concat($delimiter, $link, $delimiter)"/> <!-- check if this is the first occurence of the $link --> <xsl:if test="not (preceding::a[@href=$link]) and not (contains($visited-nodes, $link-record))"> <xsl:value-of select="$link-record"/> </xsl:if> </xsl:for-each> </xsl:template> <!-- ===================================================== --> <!-- Process all documents from a list. Invokes a document --> <!-- enumeration template for a list, then recurses. --> <!-- ===================================================== --> <xsl:template name="visit-node-list"> <xsl:param name="level" select="1"/> <xsl:param name="node-list"/> <xsl:param name="visited-nodes"/> <xsl:if test="contains ($node-list, $delimiter)"> <!-- print out level info --> <xsl:text>Level </xsl:text> <xsl:value-of select="$level"/> <xsl:text>: </xsl:text> <xsl:value-of select="translate($node-list, $delimiter, ' ')"/> <xsl:text>
</xsl:text> <!-- collect links for the next level --> <xsl:variable name="links"> <xsl:call-template name="enumerate-links-from-list"> <xsl:with-param name="node-list" select="$node-list"/> <xsl:with-param name="visited-nodes" select="$visited-nodes"/> </xsl:call-template> </xsl:variable> <!-- recurse to next level --> <xsl:call-template name="visit-node-list"> <xsl:with-param name="level" select="$level+1"/> <xsl:with-param name="node-list" select="$links"/> <xsl:with-param name="visited-nodes" select="concat($visited-nodes, $links)"/> </xsl:call-template> </xsl:if> </xsl:template> <!-- ===================================================== --> <!-- Enumerates all documents pointed out from a node list --> <!-- ===================================================== --> <xsl:template name="enumerate-links-from-list"> <xsl:param name="node-list"/> <xsl:param name="visited-nodes"/> <xsl:if test="contains($node-list, $delimiter)"> <!-- split the first record from the $node-list --> <xsl:variable name="head-record"> <xsl:choose> <xsl:when test="contains($node-list, $separator)"> <xsl:value-of select="substring-before($node-list, $separator)"/> </xsl:when> <xsl:otherwise> <xsl:value-of select="$node-list"/> </xsl:otherwise> </xsl:choose> </xsl:variable> <xsl:variable name="head" select="translate($head-record, $delimiter, '')"/> <!-- collect links from the first document in the $node-list --> <xsl:variable name="links"> <xsl:apply-templates select="document($head)/html"> <xsl:with-param name="visited-nodes" select="$visited-nodes"/> </xsl:apply-templates> </xsl:variable> <xsl:value-of select="$links"/> <!-- recursion: repeat the same for the rest of the $node-list --> <xsl:call-template name="enumerate-links-from-list"> <xsl:with-param name="node-list" select="substring-after($node-list, $separator)"/> <xsl:with-param name="visited-nodes" select="concat($visited-nodes, $links)"/> </xsl:call-template> </xsl:if> </xsl:template> </xsl:stylesheet> XSL-List info and archive: http://www.mulberrytech.com/xsl/xsl-list
Current Thread |
---|
|
<- Previous | Index | Next -> |
---|---|---|
Re: graph traversal, David Carlisle | Thread | [no subject], menkell |
Re: variables and substring, John E. Simpson | Date | Re: variables and substring, Nikolai Grigoriev |
Month |