Re: XSLT question on transitive closures

["Dimitre Novatchev" <dnovatchev@yahoo.com>]

>> I think it would be nice to do it properly based on FXSL higher-order
>
> True (but I'll leave that for Dimitre:-)


I am sorry I only read this a few days ago. Below is the code of the FXSL 
function. While the code is straightforward, the following must be noted:

   1. The "set" at present is only a set of nodes. I will probably produce a 
more general f:closure() function, which operates on any set of items. Then 
this function should be also passed as parameters a "union" and a 
"difference" functions.

  2. It seems that David's solution would go into an infinite loop for more 
involved examples (see the second test with reachability of nodes in cyclic 
graphs below). Therefore, the algorithm was slightly changed and works 
correctly.


The following files can be downloaded from the CVS of the FXSL project:

func-closure.xsl
===========
<xsl:stylesheet version="2.0"
 xmlns:xsl="http://www.w3.org/1999/XSL/Transform";
 xmlns:f="http://fxsl.sf.net/";
 exclude-result-prefixes="f"
>
 <xsl:import href="func-map.xsl"/>

 <xsl:function name="f:closure" as="node()*">
  <xsl:param name="pFun" as="element()"/>
  <xsl:param name="pstartSet" as="node()*"/>

  <xsl:sequence select="f:closure2($pFun, $pstartSet,$pstartSet)"/>
 </xsl:function>

 <xsl:function name="f:closure2" as="node()*">
  <xsl:param name="pFun" as="element()"/>
  <xsl:param name="pCurClosure" as="node()*"/>
  <xsl:param name="pstartSet" as="node()*"/>

  <xsl:if test="exists($pstartSet)">
   <xsl:variable name="vNew" select=
        "f:map($pFun,$pstartSet) except $pCurClosure"/>
   <xsl:sequence select=
         "$pstartSet
         | $vNew
         | f:closure2($pFun,$pCurClosure | $vNew, $vNew)"/>
  </xsl:if>
 </xsl:function>

 <xsl:function name="f:closure" as="node()">
  <xsl:param name="pFun" as="element()"/>

  <xsl:sequence select="f:curry(f:closure(), 2, $pFun)"/>
 </xsl:function>

 <xsl:function name="f:closure" as="element()">
  <f:closure/>
 </xsl:function>

 <xsl:template match="f:closure" mode="f:FXSL"
  as="node()*">
  <xsl:param name="arg1" as="element()"/>
  <xsl:param name="arg2" as="node()*"/>

  <xsl:sequence select="f:closure($arg1,$arg2)"/>
 </xsl:template>
</xsl:stylesheet>



testFunc-closure.xsl
===============
<xsl:stylesheet version="2.0"
 xmlns:xsl="http://www.w3.org/1999/XSL/Transform";
 xmlns:f="http://fxsl.sf.net/";
 exclude-result-prefixes="f"
>

  <xsl:import href="../f/func-closure.xsl"/>
  <xsl:import href="../f/func-map.xsl"/>
  <xsl:import href="../f/func-standardXpathFunctions.xsl"/>

 <xsl:function name="f:aunt" as="node()*">
   <xsl:param name="node" as="node()"/>
   <xsl:sequence select="$node/../../* except $node/parent::*"/>
 </xsl:function>

 <xsl:function name="f:aunt" as="element()">
  <f:aunt/>
 </xsl:function>

 <xsl:template match="f:aunt" mode="f:FXSL" as="node()*">
   <xsl:param name="arg1" as="node()"/>

   <xsl:sequence select="f:aunt($arg1)"/>
 </xsl:template>

 <xsl:function name="f:grandChild" as="node()*">
  <xsl:param name="node" as="node()"/>
  <xsl:sequence select="$node/*/*"/>
 </xsl:function>

 <xsl:function name="f:grandChild" as="element()">
  <f:grandChild/>
 </xsl:function>

 <xsl:template match="f:grandChild" mode="f:FXSL" as="node()*">
  <xsl:param name="arg1" as="node()"/>

  <xsl:sequence select="f:grandChild($arg1)"/>
 </xsl:template>

 <xsl:function name="f:self" as="node()*">
  <xsl:param name="node" as="node()"/>
  <xsl:sequence select="$node/."/>
 </xsl:function>

 <xsl:function name="f:self" as="element()">
  <f:self/>
 </xsl:function>

 <xsl:template match="f:self" mode="f:FXSL" as="node()*">
   <xsl:param name="arg1" as="node()"/>

   <xsl:sequence select="f:self($arg1)"/>
 </xsl:template>

  <xsl:template match="/">

   === self() on a =======
    <xsl:sequence select="f:map(f:name(),f:closure(f:self(),$doc/a))"/>
   =======================

   === aunt() on kkk  ====
    <xsl:sequence select="f:map(f:name(),f:closure(f:aunt(),$doc//kkk))"/>
   =======================

   === grandChild() on a ====
    <xsl:sequence 
select="f:map(f:name(),f:closure(f:grandChild(),$doc/a))"/>
   ==========================

 </xsl:template>



<xsl:variable name="doc">
  <a>
    <b>
      <c>
<d/>
<e>
  <f/>
  <kkk/>
  <hhh>
    <ll/>
  </hhh>
</e>
      </c>
      <c2/>
    </b>
    <b2/>
  </a>
</xsl:variable>

</xsl:stylesheet>


testFunc-closure2.xsl
================
<xsl:stylesheet version="2.0"
 xmlns:xsl="http://www.w3.org/1999/XSL/Transform";
 xmlns:f="http://fxsl.sf.net/";
 exclude-result-prefixes="f"
 >
  <xsl:import href="../f/func-closure.xsl"/>
  <xsl:import href="../f/func-map.xsl"/>

  <xsl:output omit-xml-declaration="yes" indent="yes"/>

  <!-- Requires ../data/testFunc-closure2.xml -->

  <xsl:key name="kTargets" match="node"
  use="../arc[@target = current()/@id]/@source"/>

 <xsl:function name="f:directTargets" as="node()*">
   <xsl:param name="pNode" as="node()"/>

   <xsl:sequence select=
     "key('kTargets',
           $pNode/@id,
           $pNode/ancestor::node()[last()]
           )"/>
 </xsl:function>

 <xsl:function name="f:directTargets" as="element()">
  <f:directTargets/>
 </xsl:function>

 <xsl:template match="f:directTargets" mode="f:FXSL" as="node()*">
   <xsl:param name="arg1" as="node()"/>

   <xsl:sequence select="f:directTargets($arg1)"/>
 </xsl:template>

  <xsl:template match="/">

=== Reachable from V1 =======
<xsl:text/>
    <xsl:sequence select=
      "f:closure(f:directTargets(),/*/node[@id='V1'])

      "/>
=======================

=== Reachable from V2 =======
<xsl:text/>
    <xsl:sequence select=
      "f:closure(f:directTargets(),/*/node[@id='V2'])

      "/>
=======================

 </xsl:template>

 </xsl:stylesheet>


The last transformation should be applied on the following xml file:

testFunc-closure2.xml
================
<graph>
  <node id="V1"/>
  <node id="V2"/>
  <node id="V3"/>
  <node id="V4"/>
  <node id="V5"/>
  <node id="V6"/>
  <node id="V7"/>
  <arc source="V1" target="V3"/>
  <arc source="V1" target="V4"/>
  <arc source="V2" target="V4"/>
  <arc source="V2" target="V6"/>
  <arc source="V3" target="V5"/>
  <arc source="V4" target="V5"/>
  <arc source="V6" target="V5"/>
  <arc source="V6" target="V7"/>
  <arc source="V7" target="V2"/>
</graph>


The result from running the first test transformation (the same tests as in 
David Carlisle's post) above (with Saxon 8.9.0.4) is:

   === self() on a =======
    a
   =======================

   === aunt() on kkk  ====
    d kkk c2 b2
   =======================

   === grandChild() on a ====
    a c f kkk hhh c2
   ==========================


The result from running the second test transformation above (two cases of 
finding all nodes of a given graph, reachable from a specific node. In the 
second case there is a cycle involving the nodes V2, V6, V7) is:

=== Reachable from V1 =======
<node id="V1"/>
<node id="V3"/>
<node id="V4"/>
<node id="V5"/>
=======================

=== Reachable from V2 =======
<node id="V2"/>
<node id="V4"/>
<node id="V5"/>
<node id="V6"/>
<node id="V7"/>
=======================


Due to its generality, the f:closure() function is a useful addition to the 
FXSL library.


Cheers,
Dimitre Novatchev



"David Carlisle" <davidc@nag.co.uk> wrote in message 
news:200710261002.l9QA2L7B010806@edinburgh.nag.co.uk...
>
>
>
>> Transitive closure is intrinsically a higher-order function,
>
> But guessing (since it's Rick) that this is a schematron question
> which means that one's generating a stylesheet dynamically anyway,
> There is thus the possibility to generate, given a function implementing
> an xpath expression, a specific closure function.
>
> As below where the form of the functions c() c2() and c3() are all
> identical, but they can't be parameterised by the function to call, so
> each have a static reference to f() f2()and f3() respectively.
>
>> The other thing that's needed is the ability to check for cycles. Simply
>> blowing the stack or looping isn't good enough.
>
> the code below just uses the Xpath2 except operator so that you only
> recurse on new nodes, hopefully that's efficient enough for this
> purpose.
>
>
>> I think it would be nice to do it properly based on FXSL higher-order
>
> True (but I'll leave that for Dimitre:-)
>
> David
>
> $ saxon8 -it main closure.xsl
> <?xml version="1.0" encoding="UTF-8"?>
>
> === . on a  ====
> a
> ===========
>
> === grandchild on a ====
> a c f kkk hhh c2
> ===========
>
>
> === aunt on kkk ====
> d kkk c2 b2
> ===========
>
>
>
>
>
>
>
>
>
> <xsl:stylesheet version="2.0"
> xmlns:xsl="http://www.w3.org/1999/XSL/Transform";
> xmlns:c="data:,c"
> exclude-result-prefixes="c"
> >
>
> <xsl:function name="c:c" as="node()*">
>  <xsl:param name="nodes" as="node()*"/>
>  <xsl:variable name="n2" select="$nodes/(c:f(.))"/>
>  <xsl:sequence select="$nodes | $n2 |($n2 except $nodes)/c:c(.)"/>
> </xsl:function>
>
> <xsl:function name="c:f" as="node()*">
>  <xsl:param name="node" as="node()"/>
>  <xsl:sequence select="$node/."/>
> </xsl:function>
>
> <xsl:function name="c:c2" as="node()*">
>  <xsl:param name="nodes" as="node()*"/>
>  <xsl:variable name="n2" select="$nodes/(c:f2(.))"/>
>  <xsl:sequence select="$nodes | $n2 |($n2 except $nodes)/c:c2(.)"/>
> </xsl:function>
>
> <xsl:function name="c:f2" as="node()*">
>  <xsl:param name="node" as="node()"/>
>  <xsl:sequence select="$node/*/*"/>
> </xsl:function>
>
>
>
> <xsl:function name="c:c3" as="node()*">
>  <xsl:param name="nodes" as="node()*"/>
>  <xsl:variable name="n2" select="$nodes/(c:f3(.))"/>
>  <xsl:sequence select="$nodes | $n2 |($n2 except $nodes)/c:c3(.)"/>
> </xsl:function>
>
> <xsl:function name="c:f3" as="node()*">
>  <xsl:param name="node" as="node()"/>
>  <xsl:sequence select="$node/../../* except $node/parent::*"/>
> </xsl:function>
>
> <xsl:template name="main">
>
> === . on a  ====
> <xsl:sequence select="c:c($doc/a)/name()"/>
> ===========
>
> === grandchild on a ====
> <xsl:sequence select="c:c2($doc/a)/name()"/>
> ===========
>
>
> === aunt on kkk ====
> <xsl:sequence select="c:c3($doc//kkk)/name()"/>
> ===========
>
>
>
> </xsl:template>
>
>
>
> <xsl:variable name="doc">
>  <a>
>    <b>
>      <c>
> <d/>
> <e>
>   <f/>
>   <kkk/>
>   <hhh>
>     <ll/>
>   </hhh>
> </e>
>      </c>
>      <c2/>
>    </b>
>    <b2/>
>  </a>
> </xsl:variable>
>
> </xsl:stylesheet>
>
> ________________________________________________________________________
> The Numerical Algorithms Group Ltd is a company registered in England
> and Wales with company number 1249803. The registered office is:
> Wilkinson House, Jordan Hill Road, Oxford OX2 8DR, United Kingdom.
>
> This e-mail has been scanned for all viruses by Star. The service is
> powered by MessageLabs.
> ________________________________________________________________________
>
> _______________________________________________________________________
>
> XML-DEV is a publicly archived, unmoderated list hosted by OASIS
> to support XML implementation and development. To minimize
> spam in the archives, you must subscribe before posting.
>
> [Un]Subscribe/change address: http://www.oasis-open.org/mlmanage/
> Or unsubscribe: xml-dev-unsubscribe@lists.xml.org
> subscribe: xml-dev-subscribe@lists.xml.org
> List archive: http://lists.xml.org/archives/xml-dev/
> List Guidelines: http://www.oasis-open.org/maillists/guidelines.php
>
>