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 <[EMAIL PROTECTED]> 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
