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(_dot_)laun(_at_)gmail(_dot_)com> 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(_at_)gmail(_dot_)com>
wrote:
Any feedback about this implementation and suggestions for further
optimization are welcome.
--~------------------------------------------------------------------
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>
--~--