11 Aug
2015
11 Aug
'15
8:39 p.m.
On Tue, Aug 11, 2015 at 2:33 PM, Fons Adriaensen <fons(a)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.
*
*/