This is the mail archive of the xsl-list@mulberrytech.com mailing list .


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]

Re: Ordering of Blocks based on Input/Output




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


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]