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

[Wolfgang Laun <wolfgang.laun@xxxxxxxxx>]

I was encouraged to post my code, here it is, with some comments
inline.

-W

<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>



On 28/11/2012, Wolfgang Laun <wolfgang.laun@xxxxxxxxx> wrote:
> I've learned a lot from playing with this one, and thinking about
> alternative solutions. I finally came up with an algorithm that is
> based on calling templates recursively, using them to iterate through
> selections of /words/word according to the current "starter" set while
> keeping track of the arcs of the graph over which this BF search
> passes. The resulting flat temporary document tree is then used for an
> iterative search that is suitable reduced by decreasing "hop" numbers
> and the current set of target nodes. - Performance is surprisingly
> good.
>
> I know that some checks are missing, and I may have poor XSLT choices.
> (Please let me know if you see something.)
>
> Cheers
> -W
>
>> On Tue, Nov 27, 2012 at 6:08 AM, Dimitre Novatchev <dnovatchev@xxxxxxxxx>
>> wrote:
>
>> Any feedback about this implementation and suggestions for further
>> optimization are welcome.