13 VuoDirectedAcyclicGraph::Vertex::~Vertex(
void)
22 cycleVerticesCacheReady =
false;
30 for (map<
Vertex *, vector<Vertex *> >::iterator i = edges.begin(); i != edges.end(); ++i)
49 for (map<
Vertex *, vector<Vertex *> >::iterator i = edges.begin(); i != edges.end(); ++i)
51 for (vector<Vertex *>::iterator j = i->second.begin(); j != i->second.end(); )
54 j = i->second.erase(j);
60 for (map<
Vertex *, vector<Vertex *> >::iterator i = edges.begin(); i != edges.end(); )
62 if (i->first == vertex)
70 downstreamVerticesCache.clear();
71 upstreamVerticesCache.clear();
72 cycleVerticesCacheReady =
false;
80 for (map<
Vertex *, vector<Vertex *> >::iterator i = edges.begin(); i != edges.end(); ++i)
81 if (i->first->key() == key)
95 if (find(edges[fromVertex].begin(), edges[fromVertex].end(), toVertex) == edges[fromVertex].end())
97 edges[fromVertex].push_back(toVertex);
101 downstreamVerticesCache.clear();
102 upstreamVerticesCache.clear();
103 cycleVerticesCacheReady =
false;
114 map< Vertex *, vector<Vertex *> >::iterator iter = downstreamVerticesCache.find(vertex);
115 if (iter != downstreamVerticesCache.end())
118 set<Vertex *> unused;
119 vector<Vertex *> downstreamVertices = getReachableVertices(vertex, edges, unused);
121 downstreamVerticesCache[vertex] = downstreamVertices;
123 return downstreamVertices;
134 map< Vertex *, vector<Vertex *> >::iterator iter = upstreamVerticesCache.find(vertex);
135 if (iter != upstreamVerticesCache.end())
138 map<
Vertex *, vector<Vertex *> > backEdges;
139 for (map<
Vertex *, vector<Vertex *> >::iterator i = edges.begin(); i != edges.end(); ++i)
141 for (vector<Vertex *>::iterator j = i->second.begin(); j != i->second.end(); ++j)
142 if (find(backEdges[*j].begin(), backEdges[*j].end(), i->first) == backEdges[*j].end())
143 backEdges[*j].push_back(i->first);
148 set<Vertex *> unused;
149 vector<Vertex *> upstreamVertices = getReachableVertices(vertex, backEdges, unused);
151 upstreamVerticesCache[vertex] = upstreamVertices;
153 return upstreamVertices;
161 if (cycleVerticesCacheReady)
162 return cycleVerticesCache;
164 set<Vertex *> cycleVertices;
165 for (map<
Vertex *, vector<Vertex *> >::iterator i = edges.begin(); i != edges.end(); ++i)
168 getReachableVertices(i->first, edges, c);
169 cycleVertices.insert(c.begin(), c.end());
172 cycleVerticesCacheReady =
true;
173 cycleVerticesCache = cycleVertices;
175 return cycleVertices;
181 vector<VuoDirectedAcyclicGraph::Vertex *> VuoDirectedAcyclicGraph::getReachableVertices(Vertex *vertex,
182 const map< Vertex *, vector<Vertex *> > &edges,
183 set<Vertex *> &cycleVertices)
185 map<Vertex *, vector<Vertex *> > reachableVertices;
187 if (edges.find(vertex) == edges.end())
188 return vector<Vertex *>();
190 list<Vertex *> toVisit;
191 toVisit.push_back(vertex);
193 while (! toVisit.empty())
196 Vertex *currVertex = toVisit.back();
198 set<Vertex *> nextVertices;
199 bool areCurrVerticesComplete =
true;
202 map< Vertex *, vector<Vertex *> >::const_iterator edgesIter = edges.find(currVertex);
203 if (edgesIter != edges.end())
205 for (vector<Vertex *>::const_iterator j = edgesIter->second.begin(); j != edgesIter->second.end(); ++j)
207 Vertex *nextVertex = *j;
208 nextVertices.insert(nextVertex);
210 map<Vertex *, vector<Vertex *> >::iterator nextNextVerticesIter = reachableVertices.find(nextVertex);
211 if (nextNextVerticesIter != reachableVertices.end())
214 nextVertices.insert( nextNextVerticesIter->second.begin(), nextNextVerticesIter->second.end() );
218 if (find(toVisit.begin(), toVisit.end(), nextVertex) != toVisit.end())
221 cycleVertices.insert(nextVertex);
226 toVisit.push_back(nextVertex);
227 areCurrVerticesComplete =
false;
233 if (areCurrVerticesComplete)
235 reachableVertices[currVertex].insert(reachableVertices[currVertex].end(), nextVertices.begin(), nextVertices.end());
240 return reachableVertices[vertex];
250 for (map<
Vertex *, vector<Vertex *> >::iterator i = edges.begin(); i != edges.end(); ++i)
252 ss << i->first->key();
253 if (showVertexPointers)
254 ss <<
" (" << i->first <<
")";
257 for (
Vertex *vertex : i->second)
259 ss <<
" " << vertex->
key();
260 if (showVertexPointers)
261 ss <<
" (" << vertex <<
")";
275 vector<VuoDirectedAcyclicGraph::Vertex *> foundVertices;
277 for (map<
VuoDirectedAcyclicGraph *, vector<VuoDirectedAcyclicGraph *> >::const_iterator i = edges.begin(); i != edges.end(); ++i)
281 foundVertices.push_back(vertex);
284 return foundVertices;
294 if (find(edges[fromGraph].begin(), edges[fromGraph].end(), toGraph) == edges[fromGraph].end())
296 edges[fromGraph].push_back(toGraph);
313 return getReachableVertices(vertex, edges,
true);
328 map< VuoDirectedAcyclicGraph *, vector<VuoDirectedAcyclicGraph *> > backEdges;
329 for (map<
VuoDirectedAcyclicGraph *, vector<VuoDirectedAcyclicGraph *> >::iterator i = edges.begin(); i != edges.end(); ++i)
331 for (vector<VuoDirectedAcyclicGraph *>::iterator j = i->second.begin(); j != i->second.end(); ++j)
332 if (find(backEdges[*j].begin(), backEdges[*j].end(), i->first) == backEdges[*j].end())
333 backEdges[*j].push_back(i->first);
338 return getReachableVertices(vertex, backEdges,
false);
348 vector<VuoDirectedAcyclicGraph::Vertex *> reachableVertices;
351 for (map<
VuoDirectedAcyclicGraph *, vector<VuoDirectedAcyclicGraph *> >::const_iterator i = edges.begin(); i != edges.end(); ++i)
353 if (i->first->edges.find(vertex) != i->first->edges.end())
355 containingGraph = i->first;
360 if (! containingGraph)
361 return reachableVertices;
363 list< pair< VuoDirectedAcyclicGraph *, vector<VuoDirectedAcyclicGraph::Vertex *> > > toVisit;
364 toVisit.push_back( make_pair(containingGraph, vector<VuoDirectedAcyclicGraph::Vertex *>(1, vertex)) );
366 while (! toVisit.empty())
369 vector<VuoDirectedAcyclicGraph::Vertex *> currVertices = toVisit.front().second;
372 map< VuoDirectedAcyclicGraph *, vector<VuoDirectedAcyclicGraph *> >::const_iterator edgesIter = edges.find(currGraph);
373 if (edgesIter != edges.end())
375 map< VuoDirectedAcyclicGraph *, vector<VuoDirectedAcyclicGraph::Vertex *> > moreToVisit;
377 for (vector<VuoDirectedAcyclicGraph::Vertex *>::iterator i = currVertices.begin(); i != currVertices.end(); ++i)
380 vector<VuoDirectedAcyclicGraph::Vertex *> currReachableVertices = (isDownstream ?
384 for (vector<VuoDirectedAcyclicGraph::Vertex *>::iterator j = currReachableVertices.begin(); j != currReachableVertices.end(); ++j)
388 if (find(reachableVertices.begin(), reachableVertices.end(), currReachableVertex) == reachableVertices.end())
389 reachableVertices.push_back(currReachableVertex);
392 vector<VuoDirectedAcyclicGraph::Vertex *> candidateVertices;
393 candidateVertices.push_back(currVertex);
394 candidateVertices.insert(candidateVertices.end(), currReachableVertices.begin(), currReachableVertices.end());
396 for (vector<VuoDirectedAcyclicGraph::Vertex *>::iterator j = candidateVertices.begin(); j != candidateVertices.end(); ++j)
400 for (vector<VuoDirectedAcyclicGraph *>::const_iterator k = edgesIter->second.begin(); k != edgesIter->second.end(); ++k)
405 if (matchingVertexInOtherGraph)
407 moreToVisit[otherGraph].push_back(matchingVertexInOtherGraph);
409 if (find(reachableVertices.begin(), reachableVertices.end(), matchingVertexInOtherGraph) == reachableVertices.end())
410 reachableVertices.push_back(matchingVertexInOtherGraph);
416 for (map<
VuoDirectedAcyclicGraph *, vector<VuoDirectedAcyclicGraph::Vertex *> >::iterator i = moreToVisit.begin(); i != moreToVisit.end(); ++i)
417 toVisit.push_back( make_pair(i->first, i->second) );
421 return reachableVertices;
431 for (map<
VuoDirectedAcyclicGraph *, vector<VuoDirectedAcyclicGraph *> >::iterator i = edges.begin(); i != edges.end(); ++i)
433 ss << i->first <<
" ->";
439 for (map<
VuoDirectedAcyclicGraph *, vector<VuoDirectedAcyclicGraph *> >::iterator i = edges.begin(); i != edges.end(); ++i)
441 string graphString = i->first->
toString(showVertexAddresses);
442 if (! graphString.empty())
443 ss <<
"\n" << i->first <<
":\n" << graphString <<
"\n";