RE: [xsl] Graph processing

["Michael Kay" <mike@xxxxxxxxxxxx>]

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[@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@xxxxxxxxxxxxxxx] 
> Sent: 20 March 2008 04:50
> To: xsl-list@xxxxxxxxxxxxxxxxxxxxxx
> 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