xsl-list
[Top] [All Lists]

RE: [xsl] Graph processing

2008-03-20 07:32:27

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>
--~--

<Prev in Thread] Current Thread [Next in Thread>