[LAD] Strange Jack1 problem

[Fons Adriaensen]

On Tue, Aug 11, 2015 at 02:39:50PM -0400, Paul Davis wrote:
> On Tue, Aug 11, 2015 at 2:33 PM, Fons Adriaensen <fons at linuxaudio.org> wrote:
> 
> > To find a linear sequence preserving the order of a
> > partially ordered set you need what is known as
> > 'topological sorting'. It's usually implemente using
> > depth-first search (DFS) with post-order output.
> 
> Simon (last name forgotten right now) added a variation on topological
> sort years ago, specifically to deal with some issues. His comment
> was:
> 
> /* How the sort works:
> ...

???

Amazed as I was, and convinced that the problem was the result of a recent
change, I tried to 'bisect' this on git. Result: this goes back to at least
2006. 

What is implemented is not a topological sort at all. And the classical
trick of inverting the dependency in case of a cycle has nothing to do
with it.

Ciao,

-- 
FA

A world of exhaustive, reliable metadata would be an utopia.
It's also a pipe-dream, founded on self-delusion, nerd hubris
and hysterically inflated market opportunities. (Cory Doctorow)