On Tue, Aug 11, 2015 at 2:33 PM, Fons Adriaensen <f...@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. * */ _______________________________________________ Linux-audio-dev mailing list Linux-audio-dev@lists.linuxaudio.org http://lists.linuxaudio.org/listinfo/linux-audio-dev