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