[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


Subject: Re: [xsl] Word Ladders as an example of a "Find shortest path between two nodes in a graph" problem
From: Wolfgang Laun <wolfgang.laun@xxxxxxxxx>
Date: Wed, 28 Nov 2012 13:44:23 +0100

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.


Current Thread
Keywords