Using XSLT and XPath for graph data structure processing?

[Ramon M. Felciano]

Helo all --

I'm trying to gain a deeper understand for what type of semi-declarative programming can be done through XML and XPath/XSLT. I'm looking at graph processing problems as a testbed for this, and came across a problem that I haven't been able to solve elegantly. The problem is to find "linker" vertexes that a pair of verteces from a pre-defined set. For example, if the graph verteces represent cities and edges represent flights between them, then given a list of cities, find all intermediate cities that you would stop in via a "connecting flight".

For example, given the following simple graph:

V1 -> V2 -> V3 -> V4
\<- V5 ->/

(V5 points to both V2 and V4), and its XML serialization:

<graph>
<vertex id="V1"/>
<vertex id="V2" type="anchor"/>
<vertex id="V3"/>
<vertex id="V4" type="anchor"/>
<vertex id="V5"/>
<edge source="V1" target="V2"/>
<edge source="V2" target="V3"/>
<edge source="V3" target="V4"/>
<edge source="V5" target="V2"/>
<edge source="V5" target="V4"/>
</graph>

I would like to transform this into a second graph where all vertexes that "link" two anchor distinct vertexes are flagged as link nodes. In this case, there are two anchor vertexes V2 and V4, and I can link them through V3 (V2 -> V3 -> V4) and V5 (V2 <- V5 -> V4). Note that linked verteces must be distinct, so traversing the V2 <- V1 -> V2 path should not yield V1 as a link node. So I'd like to see something like this:

<graph>
<vertex id="V1"/>
<vertex id="V2" type="anchor"/>
<vertex id="V3" linker="true"/>
<vertex id="V4" type="anchor"/>
<vertex id="V5" linker="true"/>
<edge source="V1" target="V2"/>
<edge source="V2" target="V3"/>
<edge source="V3" target="V4"/>
<edge source="V5" target="V2"/>
<edge source="V5" target="V4"/>
</graph>

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? Or is XPath/XSLT not the right paradigm for this type of information processing and transformation?

Thanks!

Ramon

 

[Andy Dingley]

I'm trying to gain a deeper understand for what type of semi-declarative programming can be done through XML and XPath/XSLT. I'm looking at graph processing problems as a testbed for this,

Don't do graphs in XML, use RDF instead.

Jave & Jena are the tools to use.

 

[Kenneth Stephen]

Don't do graphs in XML, use RDF instead.

Andy,

????? You are aware of course of RDF over XML?

Regards,
Kenneth

 

[Andy Dingley]

????? You are aware of course of RDF over XML?

Sure, but you don't process it _as_ XML.

XML does tree structure, not graphs. ID & IDREF just don't do anything useful for you and there's a whole issue about the difficulty of working with XML which contains a graph that isn't entirely represented by that document (ie. external resources)

If you want to work with "a graph" in something that's transported "in XML", then you need to build a layer above XML. Or you can use one, like RDF, that already exists.

 

[Patrick TJ McPhee]

% I'm trying to gain a deeper understand for what type of % semi-declarative programming can be done through XML and XPath/XSLT.

[...]

[given]

% <graph>
% <vertex id="V1"/>
% <vertex id="V2" type="anchor"/>
% <vertex id="V3"/>
% <vertex id="V4" type="anchor"/>
% <vertex id="V5"/>
% <edge source="V1" target="V2"/>
% <edge source="V2" target="V3"/>
% <edge source="V3" target="V4"/>
% <edge source="V5" target="V2"/>
% <edge source="V5" target="V4"/>
% </graph>

% this case, there are two anchor vertexes V2 and V4, and I can link % them through V3 (V2 -> V3 -> V4) and V5 (V2 <- V5 -> V4). Note that

I don't really understand this last one. It seems like this is a directed graph, so to have a link, you need to start at one anchor and go to the other. V5 would be a linker if there were some way to get to it from an anchor.

[we want to get]

% <graph>
% <vertex id="V1"/>
% <vertex id="V2" type="anchor"/>
% <vertex id="V3" linker="true"/>
% <vertex id="V4" type="anchor"/>
% <vertex id="V5" linker="true"/>
% <edge source="V1" target="V2"/>
% <edge source="V2" target="V3"/>
% <edge source="V3" target="V4"/>
% <edge source="V5" target="V2"/>
% <edge source="V5" target="V4"/>
% </graph>

I start by defining keys which can be used to find the anchors, the sources for each edge, and the targets for each edge:

<xsl:key name='anchors' use='@id' match='vertex[@type = "anchor"]'/> <xsl:key name='sources' use='@source' match='edge'/> <xsl:key name='targets' use='@target' match='edge'/>

If we pay attention to the directions of the edges, we want an expression which is true when the current node is the target of an edge from one or more anchors and the source of an edge towards one or more anchors. We can use the `targets' key and the current node's id attribute to find all the edges for which it's a target

key('targets', @id)

That's a node set made up of edge elements. We can turn it into a node set made up of the corresponding source attributes

key('targets', @id)/@source

then use that as an argument to key, to find the set anchor vertices which are sources of the current node:

key('anchors', key('targets', @id)/@source)

If the current node is the target of an edge from an anchor, the resulting node set will be non-empty. Similarly, here's the set of anchor nodes which are targets of edges from the current node

key('anchors', key('sources', @id)/@target)

we can use those node sets as boolean values, and so create a match expression which matches all vertex elements which are targets of an edge from an anchor and sources of an edge to an anchor

match="vertex[key('anchors', key('targets', @id)/@source) and key('anchors', key('sources', @id)/@target)]"

to ignore the direction of the edges, we can create a union of those two node sets and count the elements in the union

match="vertex[count(key('anchors', key('targets', @id)/@source)| key('anchors', key('sources', @id)/@target)) > 1]"

Note that if we were to make an edge from V2 to V1, the `directed' match expression would call V1 a link, but the undirected one would not.

The full style sheet is

<xsl:stylesheet
xmlns:xsl = 'http://www.w3.org/1999/XSL/Transform' version='1.0'>

<xsl:key name='anchors' use='@id' match='vertex[@type = "anchor"]'/> <xsl:key name='sources' use='@source' match='edge'/> <xsl:key name='targets' use='@target' match='edge'/>

<xsl:template match='node|@*'>
<xsl:copy>
<xsl:apply-templates select='node|@*'/>
</xsl:copy>
</xsl:template>

<xsl:template match='vertex[count(key("anchors", key("targets", @id)/@source) |key("anchors", key("sources", @id)/@target)) > 1]'> <xsl:copy> <xsl:apply-templates select='node|@*'/> <xsl:attribute name='linker'>true</xsl:attribute> </xsl:copy> </xsl:template>

</xsl:stylesheet>

% It would be ideal to come up with a generalized solution that would % let you use 1, 2, .. N intermediate linking nodes.

I'm not sure off the top of my head how you would generalise this.

 

[Dimitre Novatchev]

Helo all --

I'm trying to gain a deeper understand for what type of semi-declarative programming can be done through XML and XPath/XSLT. I'm looking at graph processing problems as a testbed for this, and came across a problem that I haven't been able to solve elegantly. The problem is to find "linker" vertexes that a pair of verteces from a pre-defined set. For example, if the graph verteces represent cities and edges represent flights between them, then given a list of cities, find all intermediate cities that you would stop in via a "connecting flight".

For example, given the following simple graph:

V1 -> V2 -> V3 -> V4
\<- V5 ->/

(V5 points to both V2 and V4), and its XML serialization:

<graph>
<vertex id="V1"/>
<vertex id="V2" type="anchor"/>
<vertex id="V3"/>
<vertex id="V4" type="anchor"/>
<vertex id="V5"/>
<edge source="V1" target="V2"/>
<edge source="V2" target="V3"/>
<edge source="V3" target="V4"/>
<edge source="V5" target="V2"/>
<edge source="V5" target="V4"/>
</graph>

I would like to transform this into a second graph where all vertexes that "link" two anchor distinct vertexes are flagged as link nodes. In this case, there are two anchor vertexes V2 and V4, and I can link them through V3 (V2 -> V3 -> V4) and V5 (V2 <- V5 -> V4). Note that linked verteces must be distinct, so traversing the V2 <- V1 -> V2 path should not yield V1 as a link node. So I'd like to see something like this:

<graph>
<vertex id="V1"/>
<vertex id="V2" type="anchor"/>
<vertex id="V3" linker="true"/>
<vertex id="V4" type="anchor"/>
<vertex id="V5" linker="true"/>
<edge source="V1" target="V2"/>
<edge source="V2" target="V3"/>
<edge source="V3" target="V4"/>
<edge source="V5" target="V2"/>
<edge source="V5" target="V4"/>
</graph>

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? Or is XPath/XSLT not the right paradigm for this type of information processing and transformation?

Thanks!

Ramon

Ramon,

Here's the general solution and it is quite simple and
straightforward. I use a recursive template based on the following rule:

Paths(/.., X, Z) = Union( {X -> Xi} . Paths(X, Xi, Z) )

Where the function Paths(Eset, X, Z) returns all paths from X to Z, that do not include any vertices belonging to the exclusion-set Eset.

Here {X -> Xi} are all edges from X.

As you can see the code of the transformation is 71 lines long, but it should be noted that for the purpose of readability I write some XPath expressions on several lines and also half of these 71 lines are just closing tags.

Here's the code. This transformation:

<xsl:stylesheet version="1.0"
xmlns:xsl="http://www.w3.org/1999/XSL/Transform" xmlns:exsl="http://exslt.org/common" exclude-result-prefixes="exsl"<xslutput omit-xml-declaration="yes" indent="yes"/>

<xsl:key name="kNeighbors" match="vertex"
use="../edge[@target = current/@id]/@source"/>

<xsl:key name="kNeighbors" match="vertex"
use="../edge[@source = current/@id]/@target"/>

<xsl:template match="/">
<xsl:call-template name="getPaths">
<xsl:with-param name="pNode1"
select="/*/vertex[@type='anchor'][1]"/>
<xsl:with-param name="pNode2"
select="/*/vertex[@type='anchor'][2]"/>
</xsl:call-template>
</xsl:template>

<xsl:template name="getPaths">
<xslaram name="pNode1" select="/.."/>
<xslaram name="pNode2" select="/.."/>
<xslaram name="pExcluded" select="/.."/>

<xsl:for-each select=
"key('kNeighbors', $pNode1/@id)
[not(@id = $pExcluded/@id)]">
<xsl:choose>
<xsl:when test="@id = $pNode2/@id">
<path>
<xsl:copy-of
select="/*/edge[$pNode1/@id = @*
and
$pNode2/@id = @*
]"/>
</path>
</xsl:when>
<xsltherwise>
<xsl:variable name="vrtfTail">
<xsl:call-template name="getPaths">
<xsl:with-param name="pNode1"
select="."/>
<xsl:with-param name="pNode2"
select="$pNode2"/>
<xsl:with-param name="pExcluded"
select="$pExcluded | $pNode1"/>
</xsl:call-template>
</xsl:variable>

<xsl:variable name="vTail"
select="exsl:node-set($vrtfTail)/*"/>

<xsl:if test="$vTail">
<path>
<xsl:copy-of
select="/*/edge[$pNode1/@id = @*
and
current/@id = @*
]"/>

<xsl:copy-of select="$vTail/*"/>
</path>
</xsl:if>
</xsltherwise>
</xsl:choose>
</xsl:for-each>
</xsl:template>
</xsl:stylesheet>

when applied on this source.xml:

<graph>
<vertex id="V1"/>
<vertex id="V2" type="anchor"/>
<vertex id="V3"/>
<vertex id="V4" type="anchor"/>
<vertex id="V5"/>
<edge source="V1" target="V2"/>
<edge source="V1" target="V3"/>
<edge source="V2" target="V3"/>
<edge source="V3" target="V4"/>
<edge source="V5" target="V2"/>
<edge source="V5" target="V4"/>
</graph>

produces thewanted result:

<path>
<edge source="V1" target="V2"/>
<edge source="V1" target="V3"/>
<edge source="V3" target="V4"/>
</path>
<path>
<edge source="V2" target="V3"/>
<edge source="V3" target="V4"/>
</path>
<path>
<edge source="V5" target="V2"/>
<edge source="V5" target="V4"/>
</path>

These are all three different paths (with all nodes in the path only once) from V2 to V4 in the graph described by the xml above.

The first solution:

V2 -> V1 -> V3 ->V4

is 3 edges long.

The other two are two edges long each.

I hope this helped in this specific problem and also to answer positively your questions about the expressiveness of XPath/XSLT and the appropriateness of XSLT as a tool for solving this type of problems.

Dimitre Novatchev.
FXSL developer, XML Insider,

http://fxsl.sourceforge.net/ -- the home of FXSL
Resume: http://fxsl.sf.net/DNovatchev/Resume/Res.html

 

[Ed Beroset]

I hope this helped in this specific problem and also to answer positively your questions about the expressiveness of XPath/XSLT and the appropriateness of XSLT as a tool for solving this type of problems.

What, no SVG output? I'm kidding. Seriously, I wasn't the original poster on that one, but I enjoyed looking over your solution.
Nice work!

Ed