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

[Dimitre Novatchev <dnovatchev@xxxxxxxxx>]

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.