[XSL-LIST Mailing List Archive Home] [By Thread] [By Date]

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

---

---

On 07/12/2012, Hermann Stamm-Wilbrandt <STAMMW@xxxxxxxxxx> wrote:
>
> Can we find "XSLT/Wolfgang" earlier in the thread?
> If not, can you post it here?

Here are both of them.
-W

*** Create the graph XML from a flat XML containing the words ***

<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 omit-xml-declaration="yes" indent="yes"/>

  <xsl:function name="my:key-set" as="xs:string+">
    <xsl:param name="word" as="xs:string"/>
    <xsl:for-each select="1 to string-length($word)">
      <xsl:variable name="pos" select="."/>
      <xsl:sequence select="concat(substring($word, 1, $pos -1),'.',
                                   substring($word, $pos +1,
string-length($word) -$pos))"/>
    </xsl:for-each>
  </xsl:function>

  <xsl:key name="kFindWord" match="w/text()" use="my:key-set(.)"/>
  <xsl:variable name="vDict" select="/"/>

  <xsl:template match="/">
    <words>
      <xsl:apply-templates select="*"/>
    </words>
  </xsl:template>

  <xsl:template match="w">
    <xsl:variable name="w" select="."/>
    <word>
      <xsl:sequence select="$w"/>
      <xsl:for-each select="my:key-set($w)">
        <xsl:variable name="key" select="."/>
        <xsl:for-each select="key('kFindWord', $key, $vDict)">
          <xsl:if test=". != $w">
            <nb><xsl:sequence select="."/></nb>
          </xsl:if>
        </xsl:for-each>
      </xsl:for-each>
    </word>
  </xsl:template>

</xsl:stylesheet>

*** find ladders between two words ***
<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="'white'" as="xs:string"/>
  <xsl:param name="pTargetWord" select="'black'" as="xs:string"/>


  <xsl:variable name="vStartWord" as="xs:string"
                select="if(count(key('kFindWord', $pStartWord,
$vDictGraph)/../*)
                           lt
                           count(key('kFindWord', $pTargetWord,
$vDictGraph)/../*))
                           then $pStartWord else $pTargetWord"/>

  <xsl:variable name="vTargetWord" as="xs:string"
                select="($pStartWord, $pTargetWord)[not(. eq $vStartWord)]"/>

  <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="key('kFindArc', $target, $root)[@level = $level]">
      <xsl:variable name="from" as="xs:string" 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="distinct-values(my:find-path($root,$level
-1,$start,$from,concat($from,'+',$path)))"/>
        </xsl:otherwise>
      </xsl:choose>
    </xsl:for-each>
  </xsl:function>

  <xsl:template match="/">
    <xsl:if test="not( key('kFindWord', $pStartWord, $vDictGraph) )">
      <xsl:message terminate="yes"
                              select="concat($pStartWord, ' not in
dictionary')"/>
    </xsl:if>
    <xsl:if test="not( key('kFindWord', $pTargetWord, $vDictGraph) )">
      <xsl:message terminate="yes"
                              select="concat($pTargetWord, ' not in
dictionary')"/>
    </xsl:if>

    <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="key('kFindArc', $vTargetWord, $arcs)"/>

    <xsl:choose>
      <xsl:when test="$finalArcs">
        <xsl:value-of select="my:find-path($arcs,
$finalArcs[1]/@level, $vStartWord, $vTargetWord, $vTargetWord)"/>
      </xsl:when>
      <xsl:otherwise>
        <xsl:value-of select="concat('No ladder from ', $pStartWord, '
to ', $pTargetWord )"/>
      </xsl:otherwise>
    </xsl:choose>
  </xsl:template>

  <xsl:key name="kFindArc" match="arc" use="@to"/>

  <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:if test="$starters">

    <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:choose>
      <xsl:when test="$target = $starters/nb">
        <!--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($starters/nb)"/>
          <xsl:with-param name="target" select="$target"/>
          <xsl:with-param name="toskip" select="$toskip union $starters"/>
        </xsl:call-template>
      </xsl:otherwise>
    </xsl:choose>

    </xsl:if>

  </xsl:template>

</xsl:stylesheet>

---