3 Mar
2003
3 Mar
'03
9:45 a.m.
On Mon, Mar 03, 2003 at 06:51:33AM +0000, Simon Jenkins wrote:
Dave Griffiths wrote:
>On Sat, 01 Mar 2003 03:03:37 +0000
>Simon Jenkins <sjenkins(a)blueyonder.co.uk> wrote:
>
>
>>I just took a look at the SSM GraphSort code (from 0.2.1rc2). Its a
>>neat encapsulation but the sort algorithm
>>seems to mess up on an important case:
>>
>>
>
>Nicely spotted, I hadn't noticed that one. The recursive sort algorithm
>won't explore branches until it finds a leaf node. I can't think of a
>elegant way to solve it, but I'm sure there is one.
>
void GraphSort::RecursiveWalk(int node)
{
// check it's not been logged already
// (don't want to execute the node twice)
if(find(m_Sorted.begin(),m_Sorted.end(),node)==m_Sorted.end())
{
#ifdef GRAPHSORT_TRACE
//cerr<<"adding "<<node<<" to list"<<endl;
#endif
m_Sorted.push_back(node);
}
else
{
#ifdef GRAPHSORT_TRACE
//cerr<<"Node "<<node<<" already logged, ending this
path"<<endl;
#endif
return;
}
// First add all children of this
// branch back into the inputs
map<int,Node>::iterator i=m_Graph.find(node);
for(list<int>::iterator ii=i->second.Inputs.begin();
ii!=i->second.Inputs.end(); ii++)
{
RecursiveWalk(*ii);
}
}
I wasn't completely sure if it was a bug or not (didn't know whether SSM
permitted the join at the end of a parallel chain). I was running your graph
sorting code in a harness not running SSM itself. The fact that it took me
about 2 minutes to get the harness up and running is what made me
a) impressed by the encapsulation, and
b) rudely interrupt your discussion.
For various reasons (not all of them audio related) I've got a bit of a
graph
sorting head on at the moment.
>I'll have to leave
>it for the moment though, as I'm trying to get a release ready and it's
>sensitive code to be changing right now.
>
what are your new features ?
I could have a quick go at fixing it up in the
harness, give you
something you
can drop in and try. Maybe code it so you can flip an alternative algorithm
in and out.
Would need to know...
1) the exact semantics of "Terminal"... which nodes are marked terminal
and why. I can see how/where they're marked, but haven't looked into
why. (Maybe I should just read the code).
Terminals are outputs...
there are input terminals but they are not used in 0.2.0...
2) any non-obvious requirements on the sort order.
3) how, if at all, the rest of the app is sensitive to the internal
implementation
of the GraphSort class.
Sort is only called from GraphSort.C seems to be ok for you....
--
torben Hohn
http://galan.sourceforge.net -- The graphical Audio language