13 VuoDirectedAcyclicGraph::Vertex::~Vertex(
void)
22 cycleVerticesCacheReady =
false;
30 for (map<
Vertex *, vector<Vertex *> >::iterator i = edges.begin(); i != edges.end(); ++i)
41 std::lock_guard<std::mutex> lock(graphMutex);
51 std::lock_guard<std::mutex> lock(graphMutex);
53 for (map<
Vertex *, vector<Vertex *> >::iterator i = edges.begin(); i != edges.end(); ++i)
55 for (vector<Vertex *>::iterator j = i->second.begin(); j != i->second.end(); )
58 j = i->second.erase(j);
64 for (map<
Vertex *, vector<Vertex *> >::iterator i = edges.begin(); i != edges.end(); )
66 if (i->first == vertex)
74 downstreamVerticesCache.clear();
75 upstreamVerticesCache.clear();
76 cycleVerticesCacheReady =
false;
77 longestDownstreamPathsCache.clear();
85 std::lock_guard<std::mutex> lock(graphMutex);
87 for (map<
Vertex *, vector<Vertex *> >::iterator i = edges.begin(); i != edges.end(); ++i)
88 if (i->first->key() == key)
102 std::lock_guard<std::mutex> lock(graphMutex);
104 if (find(edges[fromVertex].begin(), edges[fromVertex].end(), toVertex) == edges[fromVertex].end())
106 edges[fromVertex].push_back(toVertex);
110 downstreamVerticesCache.clear();
111 upstreamVerticesCache.clear();
112 cycleVerticesCacheReady =
false;
113 longestDownstreamPathsCache.clear();
124 std::lock_guard<std::mutex> lock(graphMutex);
126 return getDownstreamVerticesInternal(vertex);
132 vector<VuoDirectedAcyclicGraph::Vertex *> VuoDirectedAcyclicGraph::getDownstreamVerticesInternal(Vertex *vertex)
134 map< Vertex *, vector<Vertex *> >::iterator iter = downstreamVerticesCache.find(vertex);
135 if (iter != downstreamVerticesCache.end())
138 set<Vertex *> unused;
139 vector<Vertex *> downstreamVertices = getReachableVertices(vertex, edges, unused);
141 downstreamVerticesCache[vertex] = downstreamVertices;
143 return downstreamVertices;
154 std::lock_guard<std::mutex> lock(graphMutex);
156 map< Vertex *, vector<Vertex *> >::iterator iter = upstreamVerticesCache.find(vertex);
157 if (iter != upstreamVerticesCache.end())
160 map< Vertex *, vector<Vertex *> > backEdges;
161 for (map<
Vertex *, vector<Vertex *> >::iterator i = edges.begin(); i != edges.end(); ++i)
163 for (vector<Vertex *>::iterator j = i->second.begin(); j != i->second.end(); ++j)
164 if (find(backEdges[*j].begin(), backEdges[*j].end(), i->first) == backEdges[*j].end())
165 backEdges[*j].push_back(i->first);
170 set<Vertex *> unused;
171 vector<Vertex *> upstreamVertices = getReachableVertices(vertex, backEdges, unused);
173 upstreamVerticesCache[vertex] = upstreamVertices;
175 return upstreamVertices;
183 std::lock_guard<std::mutex> lock(graphMutex);
185 if (cycleVerticesCacheReady)
186 return cycleVerticesCache;
188 set<Vertex *> cycleVertices;
189 for (map<
Vertex *, vector<Vertex *> >::iterator i = edges.begin(); i != edges.end(); ++i)
192 getReachableVertices(i->first, edges, c);
193 cycleVertices.insert(c.begin(), c.end());
196 cycleVerticesCacheReady =
true;
197 cycleVerticesCache = cycleVertices;
199 return cycleVertices;
207 std::lock_guard<std::mutex> lock(graphMutex);
209 return getLongestDownstreamPathInternal(vertex);
215 int VuoDirectedAcyclicGraph::getLongestDownstreamPathInternal(Vertex *vertex)
217 auto iter = longestDownstreamPathsCache.find(vertex);
218 if (iter != longestDownstreamPathsCache.end())
222 for (Vertex *v : getDownstreamVerticesInternal(vertex))
224 int curr = getLongestDownstreamPathInternal(v);
225 longest = std::max(longest, curr);
234 vector<VuoDirectedAcyclicGraph::Vertex *> VuoDirectedAcyclicGraph::getReachableVertices(Vertex *vertex,
235 const map< Vertex *, vector<Vertex *> > &edges,
236 set<Vertex *> &cycleVertices)
238 map<Vertex *, vector<Vertex *> > reachableVertices;
240 if (edges.find(vertex) == edges.end())
241 return vector<Vertex *>();
243 list<Vertex *> toVisit;
244 toVisit.push_back(vertex);
246 while (! toVisit.empty())
249 Vertex *currVertex = toVisit.back();
251 set<Vertex *> nextVertices;
252 bool areCurrVerticesComplete =
true;
255 map< Vertex *, vector<Vertex *> >::const_iterator edgesIter = edges.find(currVertex);
256 if (edgesIter != edges.end())
258 for (vector<Vertex *>::const_iterator j = edgesIter->second.begin(); j != edgesIter->second.end(); ++j)
260 Vertex *nextVertex = *j;
261 nextVertices.insert(nextVertex);
263 map<Vertex *, vector<Vertex *> >::iterator nextNextVerticesIter = reachableVertices.find(nextVertex);
264 if (nextNextVerticesIter != reachableVertices.end())
267 nextVertices.insert( nextNextVerticesIter->second.begin(), nextNextVerticesIter->second.end() );
271 if (find(toVisit.begin(), toVisit.end(), nextVertex) != toVisit.end())
274 cycleVertices.insert(nextVertex);
279 toVisit.push_back(nextVertex);
280 areCurrVerticesComplete =
false;
286 if (areCurrVerticesComplete)
288 reachableVertices[currVertex].insert(reachableVertices[currVertex].end(), nextVertices.begin(), nextVertices.end());
293 return reachableVertices[vertex];
301 std::lock_guard<std::mutex> lock(graphMutex);
305 for (map<
Vertex *, vector<Vertex *> >::iterator i = edges.begin(); i != edges.end(); ++i)
307 ss << i->first->key();
308 if (showVertexPointers)
309 ss <<
" (" << i->first <<
")";
312 for (
Vertex *vertex : i->second)
314 ss <<
" " << vertex->
key();
315 if (showVertexPointers)
316 ss <<
" (" << vertex <<
")";
330 vector<VuoDirectedAcyclicGraph::Vertex *> foundVertices;
332 for (map<
VuoDirectedAcyclicGraph *, vector<VuoDirectedAcyclicGraph *> >::const_iterator i = edges.begin(); i != edges.end(); ++i)
336 foundVertices.push_back(vertex);
339 return foundVertices;
349 if (find(edges[fromGraph].begin(), edges[fromGraph].end(), toGraph) == edges[fromGraph].end())
351 edges[fromGraph].push_back(toGraph);
368 return getReachableVertices(vertex, edges,
true);
383 map< VuoDirectedAcyclicGraph *, vector<VuoDirectedAcyclicGraph *> > backEdges;
384 for (map<
VuoDirectedAcyclicGraph *, vector<VuoDirectedAcyclicGraph *> >::iterator i = edges.begin(); i != edges.end(); ++i)
386 for (vector<VuoDirectedAcyclicGraph *>::iterator j = i->second.begin(); j != i->second.end(); ++j)
387 if (find(backEdges[*j].begin(), backEdges[*j].end(), i->first) == backEdges[*j].end())
388 backEdges[*j].push_back(i->first);
393 return getReachableVertices(vertex, backEdges,
false);
403 vector<VuoDirectedAcyclicGraph::Vertex *> reachableVertices;
406 for (map<
VuoDirectedAcyclicGraph *, vector<VuoDirectedAcyclicGraph *> >::const_iterator i = edges.begin(); i != edges.end(); ++i)
408 if (i->first->edges.find(vertex) != i->first->edges.end())
410 containingGraph = i->first;
415 if (! containingGraph)
416 return reachableVertices;
418 list< pair< VuoDirectedAcyclicGraph *, vector<VuoDirectedAcyclicGraph::Vertex *> > > toVisit;
419 toVisit.push_back( make_pair(containingGraph, vector<VuoDirectedAcyclicGraph::Vertex *>(1, vertex)) );
421 while (! toVisit.empty())
424 vector<VuoDirectedAcyclicGraph::Vertex *> currVertices = toVisit.front().second;
427 map< VuoDirectedAcyclicGraph *, vector<VuoDirectedAcyclicGraph *> >::const_iterator edgesIter = edges.find(currGraph);
428 if (edgesIter != edges.end())
430 map< VuoDirectedAcyclicGraph *, vector<VuoDirectedAcyclicGraph::Vertex *> > moreToVisit;
432 for (vector<VuoDirectedAcyclicGraph::Vertex *>::iterator i = currVertices.begin(); i != currVertices.end(); ++i)
435 vector<VuoDirectedAcyclicGraph::Vertex *> currReachableVertices = (isDownstream ?
439 for (vector<VuoDirectedAcyclicGraph::Vertex *>::iterator j = currReachableVertices.begin(); j != currReachableVertices.end(); ++j)
443 if (find(reachableVertices.begin(), reachableVertices.end(), currReachableVertex) == reachableVertices.end())
444 reachableVertices.push_back(currReachableVertex);
447 vector<VuoDirectedAcyclicGraph::Vertex *> candidateVertices;
448 candidateVertices.push_back(currVertex);
449 candidateVertices.insert(candidateVertices.end(), currReachableVertices.begin(), currReachableVertices.end());
451 for (vector<VuoDirectedAcyclicGraph::Vertex *>::iterator j = candidateVertices.begin(); j != candidateVertices.end(); ++j)
455 for (vector<VuoDirectedAcyclicGraph *>::const_iterator k = edgesIter->second.begin(); k != edgesIter->second.end(); ++k)
460 if (matchingVertexInOtherGraph)
462 moreToVisit[otherGraph].push_back(matchingVertexInOtherGraph);
464 if (find(reachableVertices.begin(), reachableVertices.end(), matchingVertexInOtherGraph) == reachableVertices.end())
465 reachableVertices.push_back(matchingVertexInOtherGraph);
471 for (map<
VuoDirectedAcyclicGraph *, vector<VuoDirectedAcyclicGraph::Vertex *> >::iterator i = moreToVisit.begin(); i != moreToVisit.end(); ++i)
472 toVisit.push_back( make_pair(i->first, i->second) );
476 return reachableVertices;
486 for (map<
VuoDirectedAcyclicGraph *, vector<VuoDirectedAcyclicGraph *> >::iterator i = edges.begin(); i != edges.end(); ++i)
488 ss << i->first <<
" ->";
494 for (map<
VuoDirectedAcyclicGraph *, vector<VuoDirectedAcyclicGraph *> >::iterator i = edges.begin(); i != edges.end(); ++i)
496 string graphString = i->first->
toString(showVertexAddresses);
497 if (! graphString.empty())
498 ss <<
"\n" << i->first <<
":\n" << graphString <<
"\n";