Re: [xsl] Word Ladders as an example of a "Find shortest path between two nodes in a graph" problem

[Dimitre Novatchev <dnovatchev@xxxxxxxxx>]

Ok, I was running it with Saxon 6.4

Now, the times are:

With Saxon:

Wolfgang's transformation: 25sec.

Dimitre's :                            39sec.


However, with XQSharp:

Wolfgang's transformation: 23sec.

Dimitre's :                            14sec.


Therefore, one can't say wich transformation is faster -- it depends
on the XSLT processor being used.


Cheers,
Dimitre



On Wed, Nov 28, 2012 at 7:27 AM, Dimitre Novatchev <dnovatchev@xxxxxxxxx> wrote:
> I get this error, trying to run your code:
>
> SAXON 6.5.4 from Michael Kay
> Java version 1.6.0_31
> Loading my:my
> Preparation time: 250 milliseconds
> Processing file:/C:\XSLT Projects\WordLadders\Ver 0.2\dictGraph4.xml
> Building tree for file:/C:\XSLT Projects\WordLadders\Ver
> 0.2\dictGraph4.xml using class com.icl.saxon.tinytree.TinyBuilder
> Tree built in 351 milliseconds
> Error at xsl:variable on line 23 of file:/(Untitled):
>   Error in expression key('kFindWord', $pStartWord, $vDictGraph)
>                     [count(../*)  lt  count(key('kFindWord',
> $pTargetWord, $vDictGraph)/../* )]                        |
>             key('kFindWord', $pTargetWord, $vDictGraph)
>            [count(../*) le count(key('kFindWord',  $pStartWord,
> $vDictGraph)/../*)]: expected "]", found "<name>"
>
>
> Cheers,
> Dimitre
>
> On Wed, Nov 28, 2012 at 5:40 AM, Wolfgang Laun <wolfgang.laun@xxxxxxxxx> wrote:
>> <xsl:stylesheet version="2.0"
>>    xmlns:xsl="http://www.w3.org/1999/XSL/Transform";
>>    xmlns:my="my:my"
>>    xmlns:xs="http://www.w3.org/2001/XMLSchema";
>>    exclude-result-prefixes="my xs">
>>
>>   <xsl:output method="text"/>
>>
>>   <xsl:variable name="vDictGraph" select="/"/>
>>   <xsl:key name="kFindWord" match="w" use="."/>
>>
>>   <xsl:param name="pStartWord"  select="'nice'" as="xs:string"/>
>>   <xsl:param name="pTargetWord" select="'evil'" as="xs:string"/>
>>
>>   <xsl:variable name="vStartWord" as="xs:string"
>>                 select="key('kFindWord', $pStartWord, $vDictGraph)
>>                          [count(../*)  lt  count(key('kFindWord',
>> $pTargetWord, $vDictGraph)/../* )]
>>                       |
>>                       key('kFindWord', $pTargetWord, $vDictGraph)
>>                          [count(../*) le count(key('kFindWord',
>> $pStartWord, $vDictGraph)/../*)]"/>
>>
>>   <xsl:variable name="vTargetWord" as="xs:string"
>>                 select="($pStartWord, $pTargetWord)[not(. eq $vStartWord)]"/>
>>
>>   <!-- This function iterates over the temporary tree
>>       <result><arc level=".." from=".." to=".."/>...</result>
>>     to find the ladder. It starts at a node matching @to with $vTargetWord
>>     and proceeds with decreasing @level. -->
>>   <xsl:function name="my:find-path" as="xs:string*">
>>     <xsl:param name="root"   as="node()"/>
>>     <xsl:param name="level"  as="xs:integer"/>
>>     <xsl:param name="start"  as="xs:string"/>
>>     <xsl:param name="target" as="xs:string"/>
>>     <xsl:param name="path"   as="xs:string"/>
>>
>>     <xsl:for-each select="$root/result/arc[@level = $level and @to = $target]">
>>       <xsl:variable name="from" select="./@from"/>
>>       <xsl:choose>
>>         <xsl:when test="$start eq $from">
>>           <xsl:value-of select="concat($from,'+',$path)"/>
>>         </xsl:when>
>>         <xsl:otherwise>
>>           <xsl:value-of select="my:find-path($root,$level
>> -1,$start,$from,concat($from,'+',$path))"/>
>>         </xsl:otherwise>
>>       </xsl:choose>
>>     </xsl:for-each>
>>   </xsl:function>
>>
>>   <xsl:template match="/">
>>     <xsl:variable name='arcs'>
>>       <result>
>>       <xsl:call-template name="look-at-starts">
>>         <xsl:with-param name="level"  select="1"/>
>>         <xsl:with-param name="starts" select="$vStartWord"/>
>>         <xsl:with-param name="target" select="$vTargetWord"/>
>>         <xsl:with-param name="toskip" select="()"/>
>>       </xsl:call-template>
>>       </result>
>>     </xsl:variable>
>>
>>     <xsl:variable name="finalArcs" select="$arcs/result/arc[@to =
>> $vTargetWord]"/>
>>     <xsl:value-of select="my:find-path($arcs, $finalArcs[1]/@level,
>> $vStartWord, $vTargetWord, $vTargetWord)"/>
>>   </xsl:template>
>>
>>   <!-- Look at $starters nodes obtained from the current set of words
>>      ending all incomplete ladders. Generate result/arc for each hop to
>>      the next step. Recurse if none of the arc destinations is the overall
>>      target word, otherwise return the last hop. -->
>>   <xsl:template name="look-at-starts">
>>     <xsl:param name="level"  as="xs:integer"/>
>>     <xsl:param name="starts" as="xs:string*"/>
>>     <xsl:param name="target" as="xs:string"/>
>>     <xsl:param name="toskip" as="node()*"/>
>>
>>     <xsl:variable name="starters" as="node()*"
>>                   select="key('kFindWord', $starts, $vDictGraph)/..
>> except $toskip"/>
>>
>>     <xsl:for-each select="$starters">
>>       <xsl:variable name="w" select="./w"/>
>>       <xsl:for-each select="./nb">
>>         <arc level="{$level}" from="{$w}" to="{.}"/>
>>       </xsl:for-each>
>>     </xsl:for-each>
>>
>>     <xsl:variable name="nbs" select="$starters/nb"/>
>>
>>     <xsl:choose>
>>       <xsl:when test="$target = $nbs">
>>         <!--xsl:message select="'found a ladder'"/-->
>>       </xsl:when>
>>       <xsl:otherwise>
>>         <xsl:call-template name="look-at-starts">
>>           <xsl:with-param name="level"  select="$level + 1"/>
>>           <xsl:with-param name="starts" select="distinct-values($nbs)"/>
>>           <xsl:with-param name="target" select="$target"/>
>>           <xsl:with-param name="toskip" select="$toskip union $starters"/>
>>         </xsl:call-template>
>>       </xsl:otherwise>
>>     </xsl:choose>
>>   </xsl:template>
>> </xsl:stylesheet>
>
>
>
> --
> Cheers,
> Dimitre Novatchev
> ---------------------------------------
> Truly great madness cannot be achieved without significant intelligence.
> ---------------------------------------
> To invent, you need a good imagination and a pile of junk
> -------------------------------------
> Never fight an inanimate object
> -------------------------------------
> To avoid situations in which you might make mistakes may be the
> biggest mistake of all
> ------------------------------------
> Quality means doing it right when no one is looking.
> -------------------------------------
> You've achieved success in your field when you don't know whether what
> you're doing is work or play
> -------------------------------------
> Facts do not cease to exist because they are ignored.
> -------------------------------------
> Typing monkeys will write all Shakespeare's works in 200yrs.Will they
> write all patents, too? :)
> -------------------------------------
> I finally figured out the only reason to be alive is to enjoy it.



-- 
Cheers,
Dimitre Novatchev
---------------------------------------
Truly great madness cannot be achieved without significant intelligence.
---------------------------------------
To invent, you need a good imagination and a pile of junk
-------------------------------------
Never fight an inanimate object
-------------------------------------
To avoid situations in which you might make mistakes may be the
biggest mistake of all
------------------------------------
Quality means doing it right when no one is looking.
-------------------------------------
You've achieved success in your field when you don't know whether what
you're doing is work or play
-------------------------------------
Facts do not cease to exist because they are ignored.
-------------------------------------
Typing monkeys will write all Shakespeare's works in 200yrs.Will they
write all patents, too? :)
-------------------------------------
I finally figured out the only reason to be alive is to enjoy it.