Re: [xsl] Spotting "cousin marriages" in a tree

Subject: Re: [xsl] Spotting "cousin marriages" in a tree
From: Phil Endecott <spam_from_xslt_list@xxxxxxxxxxxx>
Date: Thu, 29 Jul 2004 12:43:37 +0100
Michael Kay wrote:
You may be hoping for too much. Graph algorithms such as looking for cycles
often have complexity of O(n^2) or worse, whatever language they are
implemented in.

Michael,


This can clearly be done in O(n log n) time using either of the aproaches I propose, i.e. checking if the thing has already been output or removing duplicates in a second phase using a key. All that is stopping me is that XSLT doesn't - as far as I know - allow for keys to be used on exsl:node-set()s, or for the already-generated partial result tree to be searched.

Come on, someone must have a clever idea! Please!

--Phil.

Current Thread