xsl-list
[Top] [All Lists]

Re: Spotting "cousin marriages" in a tree

2004-07-29 04:43:37
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.