Subject: Re: [xsl] Ordering of Blocks based on Input/Output From: Francis Norton <francis@xxxxxxxxxxx> Date: Thu, 10 May 2001 11:03:18 +0100 |
Dave Gomboc wrote: > > [snip] > > I'm not sure if you're aware that you're asking for what's known as a > "topological sort" (a web search on this will find you a lot of stuff on > it). I'll leave the XSLT implementation to others :-) but you should > know that an efficient solution has linear complexity: O(m+n) where m is > the number of edges and n is the number of nodes in the graph. In > English :-), if the problem size doubles, the time to find a topological > sort should only double as well. > Thanks for the efficiency info. It's nice to know one dimension of what we're aiming for. The suggested search for "topological sort" reveals that, well, there ain't nothing new under the sun. And apparently xsl-list can have a slightly short memory... There's a solution by Joerg Pietschmann at http://www.biglist.com/lists/xsl-list/archives/200101/msg00161.html followed by a most interesting discussion between him and one Jeni Tennison about how best to optimise it ... Francis. XSL-List info and archive: http://www.mulberrytech.com/xsl/xsl-list
Current Thread |
---|
|
<- Previous | Index | Next -> |
---|---|---|
Re: [xsl] Ordering of Blocks based , Dave Gomboc | Thread | Re: [xsl] Ordering of Blocks based , Dan Diebolt |
Re: AW: [xsl] import/include and ap, Jeni Tennison | Date | RE: [xsl] [XSL] Declaring datatypes, Bernard Granier |
Month |