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

[Wolfgang Laun <wolfgang.laun@xxxxxxxxx>]

The fact that one XSLT program runs three times faster on one XSLT
implementation
than on another one is strange, *very* strange. But is Saxon 6.4 the
"dernier cri"?
I'd very much like to hear Michael Kay's opinion on this.

With Saxon HE 9.2.0 running with the -t option, I compare execution times:
   1209 ms with 40065592 bytes for WL's solution
to
   2768 ms with 81184768 bytes for DN's solution.

Note: DN's solution being the one *without* the optimizations!

Not that this is conclusive. Algorithms like this one must be judged
by more than a single run:
they may behave well for small word lengths and small ladder sizes,
and scale badly, or
the other way round. (Dimitre and I aren't even using the same word
data, AFAIK.)

As an aside, I'd like to say that neither DN's nor WL's solution is
something that should
be used if this problem (i.e., shortest path) should ever need a
solution. I think that this
isn't something that should be solved in XSLT at all, except as an
academic exercise.
(Feel free to disagree - I'll not reply to anything contradicting me.)

Cheers

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