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