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

[Dimitre Novatchev <dnovatchev@xxxxxxxxx>]

Herman,

That I have initially used a not probably the most efficient algorithm
/ implementation, shouldn't be used to make general conclusions about
the appropriateness of using XSLT in solving a particular class of
problems.

Cheers,

Dimitre

On Thu, Dec 6, 2012 at 8:15 AM, Hermann Stamm-Wilbrandt
<STAMMW@xxxxxxxxxx> wrote:
>> ... I think that this
>> isn't something that should be solved in XSLT at all, except as an
>> academic exercise. ...
>>
> Agreed, nice XSLT solution, but not fast.
>
> This simple C program does find the longest path (35) to angry in a
> second (on a W520 Thinkpad) based on Dimitie's word list of length 5:
> http://www.stamm-wilbrandt.de/en/xsl-list/5.c
>
> $ time ./5 angry
> yasht
> yacht
> pacht
> pecht
> wecht
> wicht
> wight
> dight
> digit
> dimit
> demit
> remit
> refit
> befit
> besit
> beset
> besee
> belee
> belve
> beeve
> breve
> brave
> brace
> braca
> araca
> arara
> amara
> amala
> alala
> alula
> aluta
> abuta
> abura
> anura
> anury
> angry
> 35
>
> real    0m1.046s
> user    0m1.039s
> sys     0m0.004s
> $
>
>
> Mit besten Gruessen / Best wishes,
>
> Hermann Stamm-Wilbrandt
> Level 3 support for XML Compiler team and Fixpack team lead
> WebSphere DataPower SOA Appliances
> https://www.ibm.com/developerworks/mydeveloperworks/blogs/HermannSW/
> https://twitter.com/#!/HermannSW/
> ----------------------------------------------------------------------
> IBM Deutschland Research & Development GmbH
> Vorsitzende des Aufsichtsrats: Martina Koederitz
> Geschaeftsfuehrung: Dirk Wittkopp
> Sitz der Gesellschaft: Boeblingen
> Registergericht: Amtsgericht Stuttgart, HRB 243294
>
>
> |------------>
> | From:      |
> |------------>
>   >------------------------------------------------------------------------------------------------------------------------------------------|
>   |Wolfgang Laun <wolfgang.laun@xxxxxxxxx>                                                                                                   |
>   >------------------------------------------------------------------------------------------------------------------------------------------|
> |------------>
> | To:        |
> |------------>
>   >------------------------------------------------------------------------------------------------------------------------------------------|
>   |xsl-list@xxxxxxxxxxxxxxxxxxxxxx,                                                                                                          |
>   >------------------------------------------------------------------------------------------------------------------------------------------|
> |------------>
> | Date:      |
> |------------>
>   >------------------------------------------------------------------------------------------------------------------------------------------|
>   |11/28/2012 07:15 PM                                                                                                                       |
>   >------------------------------------------------------------------------------------------------------------------------------------------|
> |------------>
> | Subject:   |
> |------------>
>   >------------------------------------------------------------------------------------------------------------------------------------------|
>   |Re: [xsl] Word Ladders as an example of a "Find shortest path between two nodes in a graph" problem                                       |
>   >------------------------------------------------------------------------------------------------------------------------------------------|
>
>
>
>
>
> 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.
>



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