Fix scope error with newer GCC.
[spiralsynthmodular.git] / GraphSort.C
blobea8770e8cfd4fb80920d97f043adcc1900ac7213
1 /*  Graph Sort
2  *  Copyleft (C) 2002 David Griffiths <dave@pawfal.org>
4  *  This program is free software; you can redistribute it and/or modify
5  *  it under the terms of the GNU General Public License as published by
6  *  the Free Software Foundation; either version 2 of the License, or
7  *  (at your option) any later version.
8  *
9  *  This program is distributed in the hope that it will be useful,
10  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
11  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12  *  GNU General Public License for more details.
13  *
14  *  You should have received a copy of the GNU General Public License
15  *  along with this program; if not, write to the Free Software
16  *  Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
17 */ 
19 #include <iostream>
20 #include "GraphSort.h"
22 //#define GRAPHSORT_TRACE
24 //////////////////////////////////////////////////////////
26 GraphSort::GraphSort(bool UseTestSort)
28         m_UseTestSort=UseTestSort;
31 GraphSort::~GraphSort()
35 void GraphSort::Clear() 
36
37         //m_Sorted.clear();
38         m_Graph.clear(); 
41 const list<int> &GraphSort::GetSortedList()
43         return m_Sorted;
46 void GraphSort::Sort()
48         m_UseTestSort?TestSort():OrigSort();
51 void GraphSort::TestSort()
52 {       
53         m_Sorted.clear();
55         list<int> Candidates;
56         
57         #ifdef GRAPHSORT_TRACE
58         cerr<<"finding seed candidates"<<endl;
59         #endif
61         for (map<int,Node>::iterator i=m_Graph.begin();
62                  i!=m_Graph.end(); i++)
63         {
64                 // all nodes need these vars reset
65                 i->second.UnsatisfiedOutputs = i->second.Outputs.size();
66                 i->second.IsSorted = false;
68                 if (i->second.Outputs.empty() || i->second.IsTerminal)
69                 {
70                         // terminals and roots are seed candidates
71                         Candidates.push_back(i->first);
72                         i->second.IsCandidate=true;
74                         #ifdef GRAPHSORT_TRACE
75                         cerr<<i->first<<" is seed candidate"<<endl;
76                         #endif
77                 }
78                 else
79                 {
80                         i->second.IsCandidate = false;
81                 }
82         }
83                 
84         while (!Candidates.empty())
85         {
86                 int NodeToSort;
87                 bool FoundNodeToSort=false;
88                         
89                 // look for an ideal candidate
90                 for (list<int>::iterator i = Candidates.begin();
91                          i!=Candidates.end() && !FoundNodeToSort; i++)
92                 {
93                         if (!m_Graph[*i].UnsatisfiedOutputs)
94                         {
95                                 NodeToSort=*i;
96                                 FoundNodeToSort=true;
97                         
98                                 #ifdef GRAPHSORT_TRACE
99                                 cerr<<"sorted "<<NodeToSort<<" (ideal)"<<endl;
100                                 #endif
101                         }
102                 }
103                         
104                 if (!FoundNodeToSort)
105                 {
106                         // The latest, ie closest to the outputs, feedback source is
107                         // first on the candidate list. (There may be several equally
108                         // late candidates, but the first will do fine in that case).
109                         NodeToSort=*Candidates.begin();
111                         #ifdef GRAPHSORT_TRACE
112                         cerr<<"sorted "<<NodeToSort<<" (feedback)"<<endl;
113                         #endif
114                 }
115                         
116                 // put the chosen candidate on the sort list
117                 Candidates.remove(NodeToSort);
118                 m_Sorted.push_back(NodeToSort);
119                 m_Graph[NodeToSort].IsCandidate=false;
120                 m_Graph[NodeToSort].IsSorted=true;
121                         
122                 // all nodes which fed the candidate...
123                 for (list<int>::iterator i=m_Graph[NodeToSort].Inputs.begin();
124                          i!=m_Graph[NodeToSort].Inputs.end(); i++)
125                 {
126                         // ...have another satisfied output...
127                         m_Graph[*i].UnsatisfiedOutputs--;
129                         if(!m_Graph[*i].IsCandidate && !m_Graph[*i].IsSorted)
130                         {
131                                 // ..and are promoted to candidate if they haven't been already
132                                 Candidates.push_back(*i);
133                                 m_Graph[*i].IsCandidate=true;
135                                 #ifdef GRAPHSORT_TRACE
136                                 cerr<<*i<<" is now a candidate"<<endl;
137                                 #endif
138                         }
139                 }
140         }
142         #ifdef GRAPHSORT_TRACE
143         for(list<int>::iterator i=m_Sorted.begin();
144                 i!=m_Sorted.end(); i++) 
145         {
146                 cerr<<*i<<" ";
147         }
148         cerr<<endl;
149         #endif
152 void GraphSort::OrigSort()
153 {       
154         // walk back from all the roots
155         m_Sorted.clear();
156         list<int> RootNodes;
157         bool FoundRoot=false;
158         
159         for (map<int,Node>::iterator i=m_Graph.begin();
160                  i!=m_Graph.end(); i++)
161         {
162                 // if there are no outputs, this must be a root
163                 if (i->second.Outputs.empty())
164                 {
165                         FoundRoot=true;
166                         RecursiveWalk(i->first);
167                 }
168         }
169         
170         // no roots found - try looking for a terminal node and recursing from
171         // there, this makes circular graphs work.
172         if (!FoundRoot)
173         {
174                 for (map<int,Node>::iterator i=m_Graph.begin();
175                          i!=m_Graph.end(); i++)
176                 {
177                         // if there are no outputs, this must be a root
178                         if (i->second.IsTerminal)
179                         {       
180                                 RecursiveWalk(i->first);
181                         }
182                 }
183         }
184         
185         #ifdef GRAPHSORT_TRACE
186         for(list<int>::iterator i=m_Sorted.begin();
187                 i!=m_Sorted.end(); i++) 
188         {
189                 cerr<<*i<<" ";
190         }
191         cerr<<endl;
192         #endif
195 void GraphSort::RecursiveWalk(int node)
197         // check it's not been logged already 
198         // (don't want to execute the node twice)
199         if(find(m_Sorted.begin(),m_Sorted.end(),node)==m_Sorted.end())
200         {
201                 #ifdef GRAPHSORT_TRACE
202                 //cerr<<"adding "<<node<<" to list"<<endl;
203                 #endif
204                 m_Sorted.push_back(node);       
205         }
206         else
207         {       
208                 #ifdef GRAPHSORT_TRACE
209                 //cerr<<"Node "<<node<<" already logged, ending this path"<<endl;
210                 #endif
211                 return;
212         }
213         
214         // branch back into the inputs
215         map<int,Node>::iterator i=m_Graph.find(node);
216         for(list<int>::iterator ii=i->second.Inputs.begin();
217                          ii!=i->second.Inputs.end(); ii++)
218         {
219                 RecursiveWalk(*ii);
220         }
223 void GraphSort::Dump()
225         for (map<int,Node>::iterator i=m_Graph.begin();
226                  i!=m_Graph.end(); i++)
227         {
228                 cerr<<"Node "<<i->first<<endl;
229                 cerr<<"i=";
230                 for (list<int>::iterator ii=i->second.Inputs.begin();
231                          ii!=i->second.Inputs.end(); ii++)
232                 {
233                         cerr<<*ii<<" ";
234                 }
235                 
236                 cerr<<endl<<"o=";
237                 
238                 for (list<int>::iterator oi=i->second.Outputs.begin();
239                          oi!=i->second.Outputs.end(); oi++)
240                 {
241                         cerr<<*oi<<" ";
242                 }
243                 
244                 cerr<<endl;cerr<<endl;
245         }
248 void GraphSort::AddConnection(int SID, bool STerminal, int DID, bool DTerminal)
250         map<int,Node>::iterator si=m_Graph.find(SID);
251         if (si==m_Graph.end())
252         {
253                 Node newnode;
254                 newnode.IsTerminal = STerminal;
255                 m_Graph[SID]=newnode;
256                 #ifdef GRAPHSORT_TRACE          
257                 cerr<<"added "<<SID<<endl;
258                 #endif
259         }
261         map<int,Node>::iterator di=m_Graph.find(DID);
262         if (di==m_Graph.end())
263         {
264                 Node newnode;
265                 newnode.IsTerminal = DTerminal;
266                 m_Graph[DID]=newnode;
267                 #ifdef GRAPHSORT_TRACE
268                 cerr<<"added "<<DID<<endl;
269                 #endif
270         }
271         
272         m_Graph[SID].Outputs.push_back(DID);
273         m_Graph[DID].Inputs.push_back(SID);
274         
275         Sort();
278 void GraphSort::RemoveConnection(int SID, int DID)
280         map<int,Node>::iterator si=m_Graph.find(SID);
281         if (si==m_Graph.end())
282         {
283                 cerr<<"GraphSort::RemoveConnection - can't find source node"<<endl;
284         }
286         map<int,Node>::iterator di=m_Graph.find(DID);
287         if (di==m_Graph.end())
288         {
289                 cerr<<"GraphSort::RemoveConnection - can't find dest node"<<endl;
290         }
291         
292         list<int>::iterator soi = find(si->second.Outputs.begin(), si->second.Outputs.end(), DID);
293         if (soi==si->second.Outputs.end()) cerr<<"GraphSort::RemoveConnection - can't find soi"<<endl;
294         else si->second.Outputs.erase(soi);
295         
296         list<int>::iterator dii = find(di->second.Inputs.begin(), di->second.Inputs.end(), SID);
297         if (dii==di->second.Inputs.end()) cerr<<"GraphSort::RemoveConnection - can't find dii"<<endl;
298         else di->second.Inputs.erase(dii);
299         
300         // check to remove the nodes
301         if (si->second.Outputs.empty() && si->second.Inputs.empty())
302         {
303                 m_Graph.erase(si);
304                 #ifdef GRAPHSORT_TRACE
305                 cerr<<"removed "<<SID<<endl;
306                 #endif
307         }
309         if (di->second.Outputs.empty() && di->second.Inputs.empty())
310         {
311                 m_Graph.erase(di);
312                 #ifdef GRAPHSORT_TRACE
313                 cerr<<"removed "<<DID<<endl;
314                 #endif
315         }
317         Sort();
318 }