Re: [LAD] Strange Jack1 problem

On Tue, Aug 11, 2015 at 2:33 PM, Fons Adriaensen <fons@email-addr-hidden> 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.
 *
 */
_______________________________________________
Linux-audio-dev mailing list
Linux-audio-dev@email-addr-hidden
http://lists.linuxaudio.org/listinfo/linux-audio-dev
Received on Wed Aug 12 00:15:02 2015