Subject: RE: [xsl] Graph processing From: "Michael Kay" <mike@xxxxxxxxxxxx> Date: Thu, 20 Mar 2008 14:31:52 -0000 |
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
Current Thread |
---|
|
<- Previous | Index | Next -> |
---|---|---|
Re: [xsl] Graph processing, Dimitre Novatchev | Thread | Re: [xsl] push-pull, Mukul Gandhi |
Re: [xsl] Processing multiple input, Sean Tiley | Date | [xsl] Building a bidirectional map , Farrukh Najmi |
Month |