Subject: Re: [xsl] Word Ladders as an example of a "Find shortest path between two nodes in a graph" problem From: Wolfgang Laun <wolfgang.laun@xxxxxxxxx> Date: Fri, 7 Dec 2012 16:56:57 +0100 |
A note on memory usage, see below On 07/12/2012, Dimitre Novatchev <dnovatchev@xxxxxxxxx> wrote: >>> # XSLT/Wolfgang: 1.70s > > 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. Comparing what saxon displays about memory, running java -Xmx1000M -Xms1000M -cp /.../saxon9he.jar net.sf.saxon.Transform -t ... Dimitri: 378665104 Wolfgang 143474736 I'm not sure whether this reflects the maximum usage, since it varies wildly with smaller -Xm settings where (I think) GC kicks in in both transformations. I have an inquiry pending on the saxon list. -W 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: [xsl] 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: [xsl] 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: [xsl] 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: [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.
Current Thread |
---|
|
<- Previous | Index | Next -> |
---|---|---|
Re: [xsl] Word Ladders as an exampl, Michael Kay | Thread | Re: [xsl] Word Ladders as an exampl, Wolfgang Laun |
Re: [xsl] Word Ladders as an exampl, Wolfgang Laun | Date | Re: [xsl] serialized form of XML us, Michael Kay |
Month |