11 Aug
2015
11 Aug
'15
8:48 p.m.
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(a)linuxaudio.org> wrote:
???
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)
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:
...