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.
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.
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.
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()
41 const list<int> &GraphSort::GetSortedList()
46 void GraphSort::Sort()
48 m_UseTestSort?TestSort():OrigSort();
51 void GraphSort::TestSort()
57 #ifdef GRAPHSORT_TRACE
58 cerr<<"finding seed candidates"<<endl;
61 for (map<int,Node>::iterator i=m_Graph.begin();
62 i!=m_Graph.end(); i++)
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)
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;
80 i->second.IsCandidate = false;
84 while (!Candidates.empty())
87 bool FoundNodeToSort=false;
89 // look for an ideal candidate
90 for (list<int>::iterator i = Candidates.begin();
91 i!=Candidates.end() && !FoundNodeToSort; i++)
93 if (!m_Graph[*i].UnsatisfiedOutputs)
98 #ifdef GRAPHSORT_TRACE
99 cerr<<"sorted "<<NodeToSort<<" (ideal)"<<endl;
104 if (!FoundNodeToSort)
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;
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;
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++)
126 // ...have another satisfied output...
127 m_Graph[*i].UnsatisfiedOutputs--;
129 if(!m_Graph[*i].IsCandidate && !m_Graph[*i].IsSorted)
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;
142 #ifdef GRAPHSORT_TRACE
143 for(list<int>::iterator i=m_Sorted.begin();
144 i!=m_Sorted.end(); i++)
152 void GraphSort::OrigSort()
154 // walk back from all the roots
157 bool FoundRoot=false;
159 for (map<int,Node>::iterator i=m_Graph.begin();
160 i!=m_Graph.end(); i++)
162 // if there are no outputs, this must be a root
163 if (i->second.Outputs.empty())
166 RecursiveWalk(i->first);
170 // no roots found - try looking for a terminal node and recursing from
171 // there, this makes circular graphs work.
174 for (map<int,Node>::iterator i=m_Graph.begin();
175 i!=m_Graph.end(); i++)
177 // if there are no outputs, this must be a root
178 if (i->second.IsTerminal)
180 RecursiveWalk(i->first);
185 #ifdef GRAPHSORT_TRACE
186 for(list<int>::iterator i=m_Sorted.begin();
187 i!=m_Sorted.end(); i++)
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())
201 #ifdef GRAPHSORT_TRACE
202 //cerr<<"adding "<<node<<" to list"<<endl;
204 m_Sorted.push_back(node);
208 #ifdef GRAPHSORT_TRACE
209 //cerr<<"Node "<<node<<" already logged, ending this path"<<endl;
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++)
223 void GraphSort::Dump()
225 for (map<int,Node>::iterator i=m_Graph.begin();
226 i!=m_Graph.end(); i++)
228 cerr<<"Node "<<i->first<<endl;
230 for (list<int>::iterator ii=i->second.Inputs.begin();
231 ii!=i->second.Inputs.end(); ii++)
238 for (list<int>::iterator oi=i->second.Outputs.begin();
239 oi!=i->second.Outputs.end(); oi++)
244 cerr<<endl;cerr<<endl;
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())
254 newnode.IsTerminal = STerminal;
255 m_Graph[SID]=newnode;
256 #ifdef GRAPHSORT_TRACE
257 cerr<<"added "<<SID<<endl;
261 map<int,Node>::iterator di=m_Graph.find(DID);
262 if (di==m_Graph.end())
265 newnode.IsTerminal = DTerminal;
266 m_Graph[DID]=newnode;
267 #ifdef GRAPHSORT_TRACE
268 cerr<<"added "<<DID<<endl;
272 m_Graph[SID].Outputs.push_back(DID);
273 m_Graph[DID].Inputs.push_back(SID);
278 void GraphSort::RemoveConnection(int SID, int DID)
280 map<int,Node>::iterator si=m_Graph.find(SID);
281 if (si==m_Graph.end())
283 cerr<<"GraphSort::RemoveConnection - can't find source node"<<endl;
286 map<int,Node>::iterator di=m_Graph.find(DID);
287 if (di==m_Graph.end())
289 cerr<<"GraphSort::RemoveConnection - can't find dest node"<<endl;
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);
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);
300 // check to remove the nodes
301 if (si->second.Outputs.empty() && si->second.Inputs.empty())
304 #ifdef GRAPHSORT_TRACE
305 cerr<<"removed "<<SID<<endl;
309 if (di->second.Outputs.empty() && di->second.Inputs.empty())
312 #ifdef GRAPHSORT_TRACE
313 cerr<<"removed "<<DID<<endl;