[XSL-LIST Mailing List Archive Home] [By Thread] [By Date] [Recent Entries] [Reply To This Message]

Re: Word Ladders as an example of a "Find shortest pat

Subject: Re: Word Ladders as an example of a "Find shortest path between two nodes in a graph" problem
From: Martynas Jusevičius <martynas@xxxxxxxxxxxx>
Date: Fri, 7 Dec 2012 16:18:41 +0200
Re:  Word Ladders as an example of a "Find shortest pat
Sorry if I'm also missing the point here -- but it would be
interesting to try this example as an RDF/SPARQL application. RDF data
model is graph, so it could (should?) be more natural to process than
XML/XSLT, which is dealing with trees.

Martynas
graphity.org

On Fri, Dec 7, 2012 at 4:10 PM, Dimitre Novatchev <dnovatchev@xxxxxxxxx> wrote:
>>> # XSLT/Wolfgang: 1.70s
>>>
>> that number is impressive.
>
> On my computer the typical time for Wolfgang's transformation was  0.67seconds.
>
> This is very impressive.
>
> I have analyzed Wolfgang's alogrithm -- its merit (and probably risk,
> because for an arbitrary graph there may not be sufficient memory to
> do this) is that he obtains in a single step all nodes on level N+1
> and uses the " except" operator to exclude the already processed
> nodes, and the "distinct-values()" function to remove duplicates. This
> also allows all shortest paths to be found, which is an added plus.
>
> I will upgrade my implementation using the same technique -- now it
> just uses general comparison to exclude nodes and this as we all know
> is slow.
>
> Cheers,
>
> Dimitre
>
> On Fri, Dec 7, 2012 at 5:51 AM, Hermann Stamm-Wilbrandt
> <STAMMW@xxxxxxxxxx> wrote:
>> Thanks Wolfgang,
>>
>>> # XSLT/Wolfgang: 1.70s
>>>
>> that number is impressive.
>>
>> Can we find "XSLT/Wolfgang" earlier in the thread?
>> If not, can you post it here?
>>
>>
>> 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:      |
>> |------------>
>>   >------------------------------------------------------------------------------------------------------------------------------------------|
>>   |12/07/2012 12:54 PM                                                                                                                       |
>>   >------------------------------------------------------------------------------------------------------------------------------------------|
>> |------------>
>> | Subject:   |
>> |------------>
>>   >------------------------------------------------------------------------------------------------------------------------------------------|
>>   |Re:  Word Ladders as an example of a "Find shortest path between two nodes in a graph" problem                                       |
>>   >------------------------------------------------------------------------------------------------------------------------------------------|
>>
>>
>>
>>
>>
>> Hi Hermann,
>>
>> On 07/12/2012, Hermann Stamm-Wilbrandt <STAMMW@xxxxxxxxxx> wrote:
>>> Hello Wolfgang,
>>>
>>> its really good to hear about your results.
>>> It seems to indicate that XSLT seems to be really quick in your
>> environment
>>
>> Linux
>> MemTotal:        2013668 kB
>> Intel(R) Core(TM)2 Duo CPU     T9600  @ 2.80GHz
>> bogomips        : 5581.98
>> jdk1.6.0_23
>> saxonhe9-2-0-2j
>>
>> You C timings indicate that your system is a little faster, but not much.
>>
>>>
>>> In my C implementation I was sloppy, not only the initEdges was of
>>> quadratic
>>> complexity, but also BFS itself.
>>
>> I saw that.
>>
>>>
>>> In the night I made the code really linear (by making use of perfect hash
>>> function with uninitialized array safely).
>>
>> See below. - This hash technique limits you to a maximum word length
>> 6, but I guess a more general hash wouldn't slow you down much.
>>
>>>
>>> Since you seem to have a pretty fast system, may you please determine the
>>> XSLT time needed to go from "anyone" to "chinik" in 47 steps?
>>> As you can see below that 6 letter problem completed in 0.4s (5q in
>> 0.3s).
>>
>> # XSLT/Dimitre #1: 18.90s
>> # XSLT/Wolfgang: 1.70s
>> # Java/Wolfgang: 0.45s  (finds *all* ladders)
>> # C/Hermann: 0.58s
>> # C/Hermann, faster Hash-F: 0.49s
>>
>> A faster hash function with a smaller Pool (for array V) is:
>> #define POOL (26*26*26*26*26*26)
>> #define D(c)((c&0x1f)-1)
>> #define I(W)  (((((D(W[0])*26 + D(W[1]))*26 + D(W[2]&0x1f))*26 +
>> D(W[3]))*26 + D(W[4]))*26 + D(W[5])
>>
>> For adequate comparison C/Java I excluded reading the word file from
>> timing in the Java program.
>>
>>>
>>> On your question:
>>> If your solution really comes into subsecond range, I would choose XSLT.
>>> But if a C solution on bigger combinatorial complexity problems would
>>> outperform a XSLT solution, I would go with that, at least for the
>> compute
>>> intense part component.
>>
>> Preceding comparisons haven't even included the time it takes to
>> create the graph, which, for XSLT, is done with a separate program
>> producing the XML bundling a word with its immediate neighbours. OK,
>> so this only needs to be done once, but your C and my Java program do
>> this "on the fly". For XSLT, the additional time (using saxon's -t) is
>> 4.9 (Dimitre) or 2.1 (Wolfgang).
>>
>> The great benefits of XSLT's matching capacity and unsurpassed XML
>> processing capabilities just can't be employed with this kind of
>> problem.
>>
>> Cheers
>> Wolfgang
>>
>>>
>>> http://stamm-wilbrandt.de/en/xsl-list/5q.c
>>> http://stamm-wilbrandt.de/en/xsl-list/6q.c
>>>
>>> $ time ./5q angry
>>> yasht
>>> yacht
>>> ...
>>> anury
>>> angry
>>> 35 - 0
>>> |V|=8416(10228)  |E|=22661  degree_avg=5.39
>>> 0.296955s
>>>
>>> real           0m0.302s
>>> user           0m0.127s
>>> sys            0m0.171s
>>> $
>>>
>>>
>>> $ time ./6q anyone
>>> chinik
>>> chinin
>>> ...
>>> ancone
>>> anyone
>>> 47 - 0
>>> |V|=8329(17705)  |E|=21701  degree_avg=5.21
>>> 0.391279s
>>>
>>> real           0m0.396s
>>> user           0m0.211s
>>> sys            0m0.182s
>>> $
>>>
>>>
>>> For completeness, the complete output:
>>>
>>> $ time ./6q anyone
>>> chinik
>>> chinin
>>> chitin
>>> chiton
>>> chiron
>>> charon
>>> sharon
>>> sharan
>>> shaman
>>> seaman
>>> seasan
>>> season
>>> geason
>>> genson
>>> genion
>>> genian
>>> genial
>>> denial
>>> dental
>>> rental
>>> rectal
>>> recoal
>>> recool
>>> recook
>>> recock
>>> relock
>>> relick
>>> relink
>>> reline
>>> meline
>>> maline
>>> saline
>>> spline
>>> upline
>>> unline
>>> unfine
>>> unfile
>>> unfill
>>> unfull
>>> ungull
>>> ungula
>>> angula
>>> angola
>>> angora
>>> ancora
>>> ancona
>>> ancone
>>> anyone
>>> 47 - 0
>>> |V|=8329(17705)  |E|=21701  degree_avg=5.21
>>> 0.391279s
>>>
>>> real           0m0.396s
>>> user           0m0.211s
>>> sys            0m0.182s
>>> $
>>>
>>>
>>>
>>> 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:      |
>>> |------------>
>>>
>>>>------------------------------------------------------------------------------------------------------------------------------------------|
>>
>>>   |12/07/2012 09:21 AM
>>>                                                                 |
>>>
>>>>------------------------------------------------------------------------------------------------------------------------------------------|
>>
>>> |------------>
>>> | Subject:   |
>>> |------------>
>>>
>>>>------------------------------------------------------------------------------------------------------------------------------------------|
>>
>>>   |Re:  Word Ladders as an example of a "Find shortest path between
>> two
>>> nodes in a graph" problem                                       |
>>>
>>>>------------------------------------------------------------------------------------------------------------------------------------------|
>>
>>>
>>>
>>>
>>>
>>>
>>> Hello Hermann,
>>>
>>> nevertheless comparisons should be made on an equal basis. The C program
>>> doesn't search for a ladder from A to B (which might be implemented
>>> easily),
>>> and it uses a compiled-in dictionary, which saves time.
>>>
>>> When I compare 5.c "as is" to my (!) XSLT version of finding the ladder
>>> from
>>> "yasht" to "angry", it's 1.3sec (/usr/bin/time) to 1.9sec (saxon9he
>>> -t). (Dimitre's version #1 takes 26.3sec.)
>>>
>>> And if I /usr/bin/time my Java version that finds *all* ladders
>>> between "yasht" to "angry", it's 0.6sec...
>>>
>>> But that's not the key issue for me. Let me put it this way: if you
>>> would plan for a widely portable SW product "Word Ladders" (relying on
>>> OS SW only) with the joint capabilities of finding all ladders between
>>> words or all ladders of a given length, with a user interface for end
>>> users and another one for administrators (for updating the
>>> dictionary), what would you use?
>>>
>>> Cheers
>>> Wolfgang
>>>
>>> On 06/12/2012, Hermann Stamm-Wilbrandt <STAMMW@xxxxxxxxxx> wrote:
>>>> Hi Dimitre,
>>>>
>>>>> 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.
>>>>>
>>>> I agree with you -- and your solution is nice.
>>>>
>>>> But breadth-first-search algorithm can be implemented as linear time
>>>> algorithm in C or C++ -- I doubt that you can do linear time
>>>> implementation in XSLT since constant time array access is missing ...
>>>>
>>>>
>>>> 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:      |
>>>> |------------>
>>>>
>>>>>------------------------------------------------------------------------------------------------------------------------------------------|
>>
>>>
>>>>   |Dimitre Novatchev <dnovatchev@xxxxxxxxx>
>>>>                                                                 |
>>>>
>>>>>------------------------------------------------------------------------------------------------------------------------------------------|
>>
>>>
>>>> |------------>
>>>> | To:        |
>>>> |------------>
>>>>
>>>>>------------------------------------------------------------------------------------------------------------------------------------------|
>>
>>>
>>>>   |xsl-list@xxxxxxxxxxxxxxxxxxxxxx,
>>>>                                                                 |
>>>>
>>>>>------------------------------------------------------------------------------------------------------------------------------------------|
>>
>>>
>>>> |------------>
>>>> | Date:      |
>>>> |------------>
>>>>
>>>>>------------------------------------------------------------------------------------------------------------------------------------------|
>>
>>>
>>>>   |12/06/2012 05:50 PM
>>>>                                                                 |
>>>>
>>>>>------------------------------------------------------------------------------------------------------------------------------------------|
>>
>>>
>>>> |------------>
>>>> | Subject:   |
>>>> |------------>
>>>>
>>>>>------------------------------------------------------------------------------------------------------------------------------------------|
>>
>>>
>>>>   |Re:  Word Ladders as an example of a "Find shortest path between
>>> two
>>>> nodes in a graph" problem                                       |
>>>>
>>>>>------------------------------------------------------------------------------------------------------------------------------------------|
>>
>>>
>>>>
>>>>
>>>>
>>>>
>>>>
>>>> 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:  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.

Current Thread

PURCHASE STYLUS STUDIO ONLINE TODAY!

Purchasing Stylus Studio from our online shop is Easy, Secure and Value Priced!

Buy Stylus Studio Now

Download The World's Best XML IDE!

Accelerate XML development with our award-winning XML IDE - Download a free trial today!

Don't miss another message! Subscribe to this list today.
Email
First Name
Last Name
Company
Subscribe in XML format
RSS 2.0
Atom 0.3
Site Map | Privacy Policy | Terms of Use | Trademarks
Free Stylus Studio XML Training:
W3C Member
Stylus Studio® and DataDirect XQuery ™are products from DataDirect Technologies, is a registered trademark of Progress Software Corporation, in the U.S. and other countries. © 2004-2013 All Rights Reserved.