[linux-audio-dev] XAP spec - early scribbles

[torbenh at gmx.de]

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 at 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