You can find at least one example of a graph-processing algorithm - looking
for cycles - in my XSLT 2.0 Programmer's Reference. It's entirely doable,
but you need to become familiar with functional programming using recursion.
A slight complication here is that you want to find a set of paths. That's
most naturally modelled as a sequence of sequences of nodes; but
unfortunately the XPath 2.0 data model doesn't allow you to manipulate
sequences of sequences. One workaround might be to collapse them into a
single sequence, using the document node as a marker to indicate where one
sequence ends and the next one starts. Another approach is to model each
path as a string consisting of the node id values, comma separated. That
approach makes it easy to select the paths that pass through B, H, and K
using a regular expression applied to the string representation of the path.
To find all the paths that start at B, you can use a recursive function
something like this:
<xsl:function name="f:extend-path-set" as="xs:string*">
<xsl:param name="path-set" as="xs:string*">
<xsl:for-each select="$path-set">
<xsl:variable name="path" select="tokenize(., ',')"/>
<xsl:sequence select="."/>
<xsl:for-each select="$graph//edge[(_at_)source=$path[last()]][not($path =
@target)]">
<xsl:sequence select="f:extend-path-set(concat(., ',', @target))"/>
</xsl:for-each>
</xsl:for-each>
</xsl:function>
<xsl:variable name="paths-starting-at-B"
select="f:extend-path-set('B')"/>
And then you can find all the paths through B, H, K as
<xsl:variable name="paths-through-B-H-K"
select="$paths-starting-at-B[matches(concat(',',.,','),
',B,[.*,]*H,[.*,]*K,')]"/>
Not tested.
Note that the predicate [not($path = @target)] is to stop infinite looping
if there is a cycle in the data. $graph is a global variable set to the root
node of the input document.
Michael Kay
http://www.saxonica.com/
-----Original Message-----
From: Ken Tam [mailto:kentam(_at_)proteustech(_dot_)com]
Sent: 20 March 2008 04:50
To: xsl-list(_at_)lists(_dot_)mulberrytech(_dot_)com
Subject: [xsl] Graph processing
Hi all,
I need to process graphs in GraphML format. For example,
given the following graph:
A
/ | \
B C D
/ \
E F
/ \ / \
G H I
/ \
J K
will be represented in GraphML as:
<?xml version="1.0" encoding="UTF-8"?>
<graphml xmlns="http://graphml.graphdrawing.org/xmlns"
xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
xsi:schemaLocation="http://graphml.graphdrawing.org/xmlns
http://graphml.graphdrawing.org/xmlns/1.0/graphml.xsd">
<graph id="G" edgedefault="directed">
<node id="A"/>
<node id="B"/>
<node id="C"/>
<node id="D"/>
<node id="E"/>
<node id="F"/>
<node id="G"/>
<node id="H"/>
<node id="I"/>
<node id="J"/>
<node id="K"/>
<edge source="A" target="B"/>
<edge source="A" target="C"/>
<edge source="A" target="D"/>
<edge source="B" target="E"/>
<edge source="B" target="F"/>
<edge source="E" target="G"/>
<edge source="E" target="H"/>
<edge source="F" target="H"/>
<edge source="F" target="I"/>
<edge source="H" target="J"/>
<edge source="H" target="K"/>
</graph>
</graphml>
One sample process is to find all paths starting from "B"
passing through "H" ending in "K". The results are:
B->E->H->K
B->F->H->K
Can XSL/XPATH be used to find the paths? or a transformation
needs to be done first from graph to tree with ID and IDREF
before applying XPATH axis expressions. This is just a simple
example and the real graphs contain many shared paths. Thus,
a tree representation will be very large with many duplicated
branches.
Thanks,
Ken
--~------------------------------------------------------------------
XSL-List info and archive: http://www.mulberrytech.com/xsl/xsl-list
To unsubscribe, go to: http://lists.mulberrytech.com/xsl-list/
or e-mail:
<mailto:xsl-list-unsubscribe(_at_)lists(_dot_)mulberrytech(_dot_)com>
--~--
--~------------------------------------------------------------------
XSL-List info and archive: http://www.mulberrytech.com/xsl/xsl-list
To unsubscribe, go to: http://lists.mulberrytech.com/xsl-list/
or e-mail: <mailto:xsl-list-unsubscribe(_at_)lists(_dot_)mulberrytech(_dot_)com>
--~--