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

[Chris Maloney <voldrani@xxxxxxxxx>]

That sounds a little bit like a breadth-first tree search I just did
recently in XQuery.  I haven't looked at Dimitre's example in detail,
so apologies if this is way off-base.  My routine examined a DTD, and,
given a set of elements that could be document root elements, found
all of the xml elements in the DTD that were reachable:
https://github.com/NCBITools/DtdAnalyzer/blob/master/test/find-unreachable.xqy.
 It turned out to be surprisingly short, and worked quite well over a
set on the order of 10^2.  Not sure if it would hold up processing a
long word list, but actually, I don't see why not.

On Wed, Nov 28, 2012 at 7:44 AM, 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.