xsl-list
[Top] [All Lists]

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

2012-11-28 09:28:16
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(_dot_)laun(_at_)gmail(_dot_)com> 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.

--~------------------------------------------------------------------
XSL-List info and archive:  http://www.mulberrytech.com/xsl/xsl-list
To unsubscribe, go to: http://lists.mulberrytech.com/xsl-list/
or e-mail: <mailto:xsl-list-unsubscribe(_at_)lists(_dot_)mulberrytech(_dot_)com>
--~--

<Prev in Thread] Current Thread [Next in Thread>