I just took a look at the SSM GraphSort code (from 0.2.1rc2). Its a neat encapsulation but the sort algorithmOn Fri, 28 Feb 2003 19:05:19 +0100 David Olofson <[EMAIL PROTECTED]> wrote:
On Friday 28 February 2003 09.20, [EMAIL PROTECTED] wrote:
[...]
random latency ? how do you mean that ?Latency depends on how you happen to construct the net (order of instantiation, connections etc) and/or the actual layout of the net, in "non-obvious" ways.
In ssm I sort the network each time a connection is made/destroyed, and generate a ordered list of modules to process from the root up to the leaves. It has to cope with circular sections, which unavoidably introduce latency, but it works. It also automatically means unconnected modules don't get processed, which is nice.
seems to mess up on an important case:
GraphSort MySort; MySort.AddConnection( 1, false, 2, false ); MySort.AddConnection( 1, false, 3, false ); MySort.AddConnection( 2, false, 4, false ); MySort.AddConnection( 3, false, 4, false ); MySort.Sort();
In other words 1feeds both 2 and 3, and then 2 and 3 both feed 4.
GraphSort gives the ordering 4,2,1,3 for this graph (ie execution order 3,1,2,4)
introducing latency into what could have been evaluated straight through:
Execution order 1,2,3,4 OR execution order 1,3,2,4 would have done the trick.
Well, maybe this isn't an important case in ssm (I haven't looked) but its certainly
important to the more general issue of sorting graphs.
My amble demo contains a correct (AFAIK) graph ordering algorithm but its
poorly encapsulated, the code is a bit of a mess, and it has a slightly different
underlying model of a graph: More general in some ways (one output can feed
many inputs) and less general in others (there's only one "root" node, there's no
separate notion of a "terminal" node).
SSM and amble both ignore unconnected nodes which is nice if that's what you
want, but not if its not. A general solution to the graph sorting problem would
need to at least allow for the possibility that an unconnected node might need
to be processed.
That's easily solved... but here's a problem that's not:
A general solution to the graph sorting problem would have to know about the
I/O dependencies *inside* the nodes. This isn't usually a problem on the scale
where a node represents, for example, a simple filter or oscillator. But what about
the scale where a node represents a quad noise gate or a reasonably well-featured
mixer (ie with inserts etc)? Nodes like that aren't just difficult to place correctly
in the execution order... they can be *impossible* to place correctly in a very large
number of perfectly reasonable graphs: Different parts of their internals need to
be executed at different times!
Simon Jenkins (Bristol, UK)
