Re: [xml-dev] Using XSLT and XPath for graph data structure processing?

[Sjoerd Visscher <sjoerd@w3future.com>]

Ramon M. Felciano Yahoo wrote:

> It would be ideal to come up with a generalized solution that would let 
> you use 1, 2, .. N intermediate linking nodes. I've been able to get 
> this working with nested loops, but it isn't particularly declarative or 
> speedy, and is certainly more verbose than I'd like, so I'm wondering if 
> anyone here has insights into how to do this elegantly and in XSLT/XPath 
> style. For example, is it possible to write a single XPath expression 
> that will select <vertex> elements that obey the above criteria? If not, 
> does anyone have any suggestions for how to code this effectively and 
> efficiently with XSLT?

The following XSL transformation does what you want:

<?xml version="1.0"?>
<xsl:transform version="1.0" 
xmlns:xsl="http://www.w3.org/1999/XSL/Transform";>

<xsl:key name="a" match="/graph/vertex[@type='anchor']" use="@id" />
<xsl:key name="e1" match="/graph/edge/@target" use="../@source" />
<xsl:key name="e2" match="/graph/edge/@source" use="../@target" />

<!-- identity template -->
<xsl:template match="@* | node()">
   <xsl:copy>
     <xsl:apply-templates select="@* | node()" />
   </xsl:copy>
</xsl:template>

<xsl:template match="vertex">
   <xsl:copy>
     <xsl:apply-templates select="@* | node()" />
     <!-- more than one edge to an anchor vertex? -->
     <xsl:if test="count(key('a',key('e1',@id)|key('e2',@id)))&gt;1">
       <xsl:attribute name="linker">true</xsl:attribute>
     </xsl:if>
   </xsl:copy>
</xsl:template>

</xsl:transform>

I've used the key function here as both a look-up and as a filter 
shortcut. The neat thing about the key function is that it returns a set 
of distinct nodes. F.e. if you'd have two edges from V1 to V2, the 
expression key('e1', @id) returns 2 nodes, but when put through the key 
function again to find the anchor vertices, there's only one result: the 
V2 vertex.

Extending this to a generalized solution is still hard though...

-- 
Sjoerd Visscher
http://w3future.com/weblog/