[LAD] Strange Jack1 problem

[Paul Davis]

That said, we became aware that a similar algorithm, implemented by
Torben Hohn when he parallelized Ardour, that forms part of the Ardour
"DSP engine" was also flawed and was replaced with topological sorting
within the last couple of years.

On Tue, Aug 11, 2015 at 2:39 PM, Paul Davis <paul at linuxaudiosystems.com> 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:
>  *
>  * Each client has a "sortfeeds" list of clients indicating which clients
>  * it should be considered as feeding for the purposes of sorting the
>  * graph. This list differs from the clients it /actually/ feeds in the
>  * following ways:
>  *
>  * 1. Connections from a client to itself are disregarded
>  *
>  * 2. Connections to a driver client are disregarded
>  *
>  * 3. If a connection from A to B is a feedback connection (ie there was
>  *    already a path from B to A when the connection was made) then instead
>  *    of B appearing on A's sortfeeds list, A will appear on B's sortfeeds
>  *    list.
>  *
>  * If client A is on client B's sortfeeds list, client A must come after
>  * client B in the execution order. The above 3 rules ensure that the
>  * sortfeeds relation is always acyclic so that all ordering constraints
>  * can actually be met.
>  *
>  * Each client also has a "truefeeds" list which is the same as sortfeeds
>  * except that feedback connections appear normally instead of reversed.
>  * This is used to detect whether the graph has become acyclic.
>  *
>  */