1 /*=========================================================================
2
3 Library: CTK
4
5 Copyright (c) Kitware Inc.
6
7 Licensed under the Apache License, Version 2.0 (the "License");
8 you may not use this file except in compliance with the License.
9 You may obtain a copy of the License at
10
11 http://www.apache.org/licenses/LICENSE-2.0.txt
12
13 Unless required by applicable law or agreed to in writing, software
14 distributed under the License is distributed on an "AS IS" BASIS,
15 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
16 See the License for the specific language governing permissions and
17 limitations under the License.
18
19 =========================================================================*/
20
21 // CTK includes
22 #include "ctkDependencyGraph.h"
23
24 // STD includes
25 #include <iostream>
26 #include <sstream>
27 #include <algorithm>
28 #include <vector>
29 #include <set>
30 #include <map>
31 #include <list>
32 #include <queue>
33 #include <cassert>
34
35 #define MAXV 100
36 #define MAXDEGREE 2000
37
38 //----------------------------------------------------------------------------
39 class ctkDependencyGraphPrivate
40 {
41
42 public:
43
44 ctkDependencyGraph* const q_ptr;
45
46 ctkDependencyGraphPrivate(ctkDependencyGraph& p);
47 ~ctkDependencyGraphPrivate();
48
49 /// Compute outdegree
50 void computeOutdegrees(std::vector<int>& computedOutdegrees);
51
52 /// Traverse tree using Depth-first_search
53 void traverseUsingDFS(int v);
54
55 /// Called each time an edge is visited
56 void processEdge(int from, int to);
57
58 /// Called each time a vertex is processed
59 void processVertex(int v);
60
61 /// Retrieve the path between two vertices
62 void findPathDFS(int from, int to, std::list<int>& path);
63
64 /// Recursive function used by findPaths to retrieve the path between two vertices
65 void findPathsRec(int from, int to, std::list<int>* path, std::list<std::list<int>* >& paths);
66
67 void setEdge(int vertice, int degree, int value);
68 int edge(int vertice, int degree)const;
69
70 void verticesWithIndegree(int indegree, std::list<int>& list);
71
72 int subgraphSize(int rootId);
73 void subgraphSizeRec(int rootId, std::set<int>& uniqueVertices);
74
75 void subgraphInsert(ctkDependencyGraph& subgraph, int rootId,
76 std::map<int,int>& subgraphIdToGlobal, std::map<int,int>& globalIdToSubgraph);
77
78 int getOrGenerateSubgraphId(std::map<int, int>& subgraphIdToGlobal,
79 std::map<int, int>& globalIdToSubgraph,
80 int globalId);
81
82 /// See http://en.wikipedia.org/wiki/Adjacency_list
83 std::vector<std::vector<int>* > Edges;
84 std::vector<int> OutDegree;
85 std::vector<int> InDegree;
86 int NVertices;
87 int NEdges;
88
89 /// Structure used by DFS
90 /// See http://en.wikipedia.org/wiki/Depth-first_search
91 std::vector<bool> Processed; // processed vertices
92 std::vector<bool> Discovered; // discovered vertices
93 std::vector<int> Parent; // relation discovered
94
95 bool Abort; // Flag indicating if traverse should be aborted
96 bool Verbose;
97 bool CycleDetected;
98 int CycleOrigin;
99 int CycleEnd;
100
101 std::list<int> ListOfEdgeToExclude;
102
103 };
104
105 //----------------------------------------------------------------------------
106 // Returns a space separated string of T.
107 template<class T>
listToString(const std::list<T> & list)108 std::string listToString(const std::list<T>& list)
109 {
110 std::stringstream outputString;
111
112 typename std::list<T>::const_iterator iter;
113 for (iter = list.begin(); iter != list.end(); iter++)
114 {
115 outputString << *iter << " ";
116 }
117
118 return outputString.str();
119 }
120
121 //----------------------------------------------------------------------------
122 // Returns true if the map contains the key and false otherwise.
123 template<class T1, class T2>
mapContainsKey(const std::map<T1,T2> & map,const T1 & key)124 bool mapContainsKey(const std::map<T1, T2>& map, const T1& key)
125 {
126 bool result = false;
127
128 if (map.find(key) != map.end())
129 {
130 result = true;
131 }
132
133 return result;
134 }
135
136 //----------------------------------------------------------------------------
137 // Returns true if the list contains the value and false otherwise.
138 template<class T>
listContainsValue(const std::list<T> & list,const T & value)139 bool listContainsValue(const std::list<T>& list, const T& value)
140 {
141 bool result = false;
142
143 typename std::list<T>::const_iterator iter;
144 for (iter = list.begin(); iter != list.end(); iter++)
145 {
146 if ((*iter) == value)
147 {
148 result = true;
149 break;
150 }
151 }
152 return result;
153 }
154
155 //----------------------------------------------------------------------------
156 // ctkInternal methods
157
158 //----------------------------------------------------------------------------
ctkDependencyGraphPrivate(ctkDependencyGraph & object)159 ctkDependencyGraphPrivate::ctkDependencyGraphPrivate(ctkDependencyGraph& object)
160 :q_ptr(&object)
161 {
162 this->NVertices = 0;
163 this->NEdges = 0;
164 this->Abort = false;
165 this->Verbose = false;
166 this->CycleDetected = false;
167 this->CycleOrigin = 0;
168 this->CycleEnd = 0;
169 }
170
~ctkDependencyGraphPrivate()171 ctkDependencyGraphPrivate::~ctkDependencyGraphPrivate()
172 {
173 std::vector<std::vector<int>* >::iterator edgesIterator;
174 for (edgesIterator = this->Edges.begin(); edgesIterator != this->Edges.end(); edgesIterator++)
175 {
176 if (*edgesIterator != NULL)
177 {
178 delete *edgesIterator;
179 }
180 }
181 }
182
183 //----------------------------------------------------------------------------
computeOutdegrees(std::vector<int> & computedOutdegrees)184 void ctkDependencyGraphPrivate::computeOutdegrees(std::vector<int>& computedOutdegrees)
185 {
186 for (int i=1; i <= this->NVertices; i++)
187 {
188 computedOutdegrees[i] = 0;
189 }
190
191 for (int i=1; i <= this->NVertices; i++)
192 {
193 for (int j=0; j < this->OutDegree[i]; j++)
194 {
195 computedOutdegrees[ this->edge(i,j) ] ++;
196 }
197 }
198 }
199
200 //----------------------------------------------------------------------------
traverseUsingDFS(int v)201 void ctkDependencyGraphPrivate::traverseUsingDFS(int v)
202 {
203 // allow for search termination
204 if (this->Abort)
205 {
206 return;
207 }
208
209 this->Discovered[v] = true;
210 this->processVertex(v);
211
212 int y; // successor vertex
213 for (int i=0; i<this->OutDegree[v]; i++)
214 {
215 y = this->edge(v, i);
216 if (q_ptr->shouldExcludeEdge(this->edge(v, i)) == false)
217 {
218 this->Parent[y] = v;
219 if (this->Discovered[y] == false)
220 {
221 this->traverseUsingDFS(y);
222 }
223 else
224 {
225 if (this->Processed[y] == false)
226 {
227 this->processEdge(v,y);
228 }
229 }
230 }
231 if (this->Abort)
232 {
233 return;
234 }
235 }
236
237 this->Processed[v] = true;
238 }
239
240 //----------------------------------------------------------------------------
processEdge(int from,int to)241 void ctkDependencyGraphPrivate::processEdge(int from, int to)
242 {
243 if (this->Discovered[to] == true)
244 {
245 this->CycleDetected = true;
246 this->CycleOrigin = to;
247 this->CycleEnd = from;
248 if (this->Verbose)
249 {
250 std::list<int> path;
251 this->findPathDFS(from, to, path);
252 std::cerr << "ERROR: Cycle detected from " << to << " to " << from << std::endl;
253 std::cerr << " " << listToString<int>(path) << std::endl;
254 path.clear();
255 this->findPathDFS(to, from, path);
256 std::cerr << " " << listToString<int>(path) << std::endl;
257 }
258 this->Abort = true;
259 }
260 }
261
262 //----------------------------------------------------------------------------
processVertex(int v)263 void ctkDependencyGraphPrivate::processVertex(int v)
264 {
265 if (this->Verbose)
266 {
267 std::cout << "processed vertex " << v << std::endl;
268 }
269 }
270
271 //----------------------------------------------------------------------------
setEdge(int vertice,int degree,int value)272 void ctkDependencyGraphPrivate::setEdge(int vertice, int degree, int value)
273 {
274 assert(vertice <= this->NVertices);
275 assert(degree < MAXDEGREE);
276 (*this->Edges[vertice])[degree] = value;
277 }
278
279 //----------------------------------------------------------------------------
edge(int vertice,int degree) const280 int ctkDependencyGraphPrivate::edge(int vertice, int degree)const
281 {
282 assert(vertice <= this->NVertices);
283 assert(degree < MAXDEGREE);
284 return (*this->Edges[vertice])[degree];
285 }
286
287 //----------------------------------------------------------------------------
findPathDFS(int from,int to,std::list<int> & path)288 void ctkDependencyGraphPrivate::findPathDFS(int from, int to, std::list<int>& path)
289 {
290 if ((from == to) || (to == -1))
291 {
292 path.push_back(from);
293 }
294 else
295 {
296 this->findPathDFS(from, this->Parent[to], path);
297 path.push_back(to);
298 }
299 }
300
301 //----------------------------------------------------------------------------
findPathsRec(int from,int to,std::list<int> * path,std::list<std::list<int> * > & paths)302 void ctkDependencyGraphPrivate::findPathsRec(
303 int from, int to, std::list<int>* path, std::list<std::list<int>* >& paths)
304 {
305 if (from == to)
306 {
307 return;
308 }
309
310 std::list<int> branch;
311 branch = *path;
312
313 int child = from;
314 for (int j=0; j < this->OutDegree[child]; j++)
315 {
316 if (j == 0)
317 {
318 int parent = this->edge(child, j);
319 (*path).push_back(parent);
320 this->findPathsRec(parent, to, path, paths);
321 }
322 else
323 {
324 int parent = this->edge(child, j);
325 // Copy path and add it to the list
326 std::list<int>* pathCopy = new std::list<int>();
327 *pathCopy = branch;
328 paths.push_back(pathCopy);
329 (*pathCopy).push_back(parent);
330 this->findPathsRec(parent, to, pathCopy, paths);
331 }
332 }
333 }
334
335 //----------------------------------------------------------------------------
verticesWithIndegree(int indegree,std::list<int> & list)336 void ctkDependencyGraphPrivate::verticesWithIndegree(int indegree, std::list<int>& list)
337 {
338 assert(indegree >= 0);
339
340 for (int i=1; i <= this->NVertices; i++)
341 {
342 if (this->InDegree[i] == indegree)
343 {
344 list.push_back(i);
345 }
346 }
347 }
348
349 //----------------------------------------------------------------------------
subgraphSizeRec(int rootId,std::set<int> & uniqueVertices)350 void ctkDependencyGraphPrivate::subgraphSizeRec(int rootId, std::set<int>& uniqueVertices)
351 {
352 assert(rootId > 0);
353
354 for (int i = 0; i < this->OutDegree[rootId]; ++i)
355 {
356 int child = this->edge(rootId, i);
357 uniqueVertices.insert(child);
358 subgraphSizeRec(child, uniqueVertices);
359 }
360 }
361
362 //----------------------------------------------------------------------------
subgraphSize(int rootId)363 int ctkDependencyGraphPrivate::subgraphSize(int rootId)
364 {
365 assert(rootId > 0);
366
367 std::set<int> vertices;
368 vertices.insert(rootId);
369 this->subgraphSizeRec(rootId, vertices);
370 return static_cast<int>(vertices.size());
371 }
372
subgraphInsert(ctkDependencyGraph & subgraph,int rootId,std::map<int,int> & subgraphIdToGlobal,std::map<int,int> & globalIdToSubgraph)373 void ctkDependencyGraphPrivate::subgraphInsert(
374 ctkDependencyGraph& subgraph, int rootId,
375 std::map<int,int>& subgraphIdToGlobal, std::map<int,int>& globalIdToSubgraph)
376 {
377 int from = this->getOrGenerateSubgraphId(subgraphIdToGlobal, globalIdToSubgraph, rootId);
378 for (int i = 0; i < this->OutDegree[rootId]; ++i)
379 {
380 int childId = this->edge(rootId, i);
381 int to = this->getOrGenerateSubgraphId(subgraphIdToGlobal, globalIdToSubgraph,
382 childId);
383
384 subgraph.insertEdge(from, to);
385 this->subgraphInsert(subgraph, childId, subgraphIdToGlobal, globalIdToSubgraph);
386 }
387 }
388
389 //----------------------------------------------------------------------------
getOrGenerateSubgraphId(std::map<int,int> & subgraphIdToGlobal,std::map<int,int> & globalIdToSubgraph,int globalId)390 int ctkDependencyGraphPrivate::getOrGenerateSubgraphId(
391 std::map<int, int>& subgraphIdToGlobal,
392 std::map<int, int>& globalIdToSubgraph,
393 int globalId)
394 {
395 // If needed, generate vertex id
396 int subgraphId = -1;
397 if (!mapContainsKey<int, int>(globalIdToSubgraph,globalId))
398 {
399 subgraphId = static_cast<int>(globalIdToSubgraph.size()) + 1;
400 globalIdToSubgraph[globalId] = subgraphId;
401 subgraphIdToGlobal[subgraphId] = globalId;
402 }
403 else
404 {
405 subgraphId = globalIdToSubgraph[globalId];
406 }
407 return subgraphId;
408 }
409
410 //----------------------------------------------------------------------------
411 // ctkDependencyGraph methods
412
413 //----------------------------------------------------------------------------
ctkDependencyGraph(int nvertices)414 ctkDependencyGraph::ctkDependencyGraph(int nvertices)
415 :d_ptr(new ctkDependencyGraphPrivate(*this))
416 {
417 d_ptr->NVertices = nvertices;
418
419 // Resize internal array
420 d_ptr->Processed.resize(nvertices + 1);
421 d_ptr->Discovered.resize(nvertices + 1);
422 d_ptr->Parent.resize(nvertices + 1);
423 d_ptr->Edges.resize(nvertices + 1);
424 d_ptr->OutDegree.resize(nvertices + 1);
425 d_ptr->InDegree.resize(nvertices + 1);
426
427 for (int i=1; i <= nvertices; i++)
428 {
429 d_ptr->OutDegree[i] = 0;
430 d_ptr->InDegree[i] = 0;
431 }
432
433 // initialize Edge adjacency list
434 for (int i=0; i <= nvertices; i++)
435 {
436 d_ptr->Edges[i] = new std::vector<int>();
437 d_ptr->Edges[i]->resize(MAXDEGREE);
438 }
439
440 // initialize search
441 for (int i=1; i <= nvertices; i++)
442 {
443 d_ptr->Processed[i] = false;
444 d_ptr->Discovered[i] = false;
445 d_ptr->Parent[i] = -1;
446 }
447 }
448
449 //----------------------------------------------------------------------------
~ctkDependencyGraph()450 ctkDependencyGraph::~ctkDependencyGraph()
451 {
452 if (d_ptr != NULL)
453 {
454 delete d_ptr;
455 }
456 }
457
458 //----------------------------------------------------------------------------
printAdditionalInfo() const459 void ctkDependencyGraph::printAdditionalInfo()const
460 {
461 std::cout << "ctkDependencyGraph (" << this << ")" << std::endl
462 << " NVertices:" << this->numberOfVertices() << std::endl
463 << " NEdges:" << this->numberOfEdges() << std::endl
464 << " Abort:" << d_ptr->Abort << std::endl;
465
466 std::cout << " [Processed]" << std::endl;
467 for(unsigned int i=1; i < d_ptr->Processed.size(); i++)
468 {
469 std::cout << i << "->" << d_ptr->Processed[i] << std::endl;
470 }
471 std::cout << " [Discovered]" << std::endl;
472 for(unsigned int i=1; i < d_ptr->Discovered.size(); i++)
473 {
474 std::cout << i << "->" << d_ptr->Discovered[i] << std::endl;
475 }
476 std::cout << " [Parent]" << std::endl;
477 for(unsigned int i=1; i < d_ptr->Parent.size(); i++)
478 {
479 std::cout << i << "->" << d_ptr->Parent[i] << std::endl;
480 }
481 std::cout << " [Graph]" << std::endl;
482 this->printGraph();
483 }
484
485 //----------------------------------------------------------------------------
printGraph() const486 void ctkDependencyGraph::printGraph()const
487 {
488 for(int i=1; i <= d_ptr->NVertices; i++)
489 {
490 std::cout << i << ":";
491 for (int j=0; j < d_ptr->OutDegree[i]; j++)
492 {
493 std::cout << " " << d_ptr->edge(i, j);
494 }
495 std::cout << std::endl;
496 }
497 }
498
499 //----------------------------------------------------------------------------
numberOfVertices() const500 int ctkDependencyGraph::numberOfVertices()const
501 {
502 return d_ptr->NVertices;
503 }
504
505 //----------------------------------------------------------------------------
numberOfEdges() const506 int ctkDependencyGraph::numberOfEdges()const
507 {
508 return d_ptr->NEdges;
509 }
510
511 //----------------------------------------------------------------------------
setVerbose(bool verbose)512 void ctkDependencyGraph::setVerbose(bool verbose)
513 {
514 d_ptr->Verbose = verbose;
515 }
516
517 //----------------------------------------------------------------------------
setEdgeListToExclude(const std::list<int> & list)518 void ctkDependencyGraph::setEdgeListToExclude(const std::list<int>& list)
519 {
520 d_ptr->ListOfEdgeToExclude = list;
521 }
522
523 //----------------------------------------------------------------------------
shouldExcludeEdge(int edge) const524 bool ctkDependencyGraph::shouldExcludeEdge(int edge)const
525 {
526 return listContainsValue(d_ptr->ListOfEdgeToExclude, edge);
527 }
528
529 //----------------------------------------------------------------------------
checkForCycle()530 bool ctkDependencyGraph::checkForCycle()
531 {
532 if (d_ptr->NEdges > 0)
533 {
534 // Store unprocessed vertex ids
535 std::list<int> uncheckedVertices;
536 for (int i = 1; i <= d_ptr->NVertices; ++i)
537 {
538 uncheckedVertices.push_back(i);
539 }
540
541 // Start the cycle detection on the source vertices
542 std::list<int> sources;
543 this->sourceVertices(sources);
544 std::list<int>::const_iterator sourcesIterator;
545 for (sourcesIterator = sources.begin(); sourcesIterator != sources.end(); sourcesIterator++)
546 {
547 d_ptr->traverseUsingDFS(*sourcesIterator);
548 if (this->cycleDetected()) return true;
549
550 for (unsigned int i=0; i < d_ptr->Processed.size(); i++)
551 {
552 if (d_ptr->Processed[i] == true)
553 {
554 uncheckedVertices.remove(i);
555 }
556
557 d_ptr->Discovered[i] = false;
558 d_ptr->Processed[i] = false;
559 }
560 }
561
562 // If a component does not have a source vertex,
563 // i.e. it is a cycle a -> b -> a, check all non
564 // processed vertices.
565 while (!uncheckedVertices.empty())
566 {
567 d_ptr->traverseUsingDFS((*uncheckedVertices.rbegin()));
568 if (this->cycleDetected()) return true;
569
570 for (unsigned int i=0; i < d_ptr->Processed.size(); i++)
571 {
572 if (d_ptr->Processed[i] == true)
573 {
574 uncheckedVertices.remove(i);
575 }
576
577 d_ptr->Discovered[i] = false;
578 d_ptr->Processed[i] = false;
579 }
580 }
581 }
582 return this->cycleDetected();
583 }
584
585 //----------------------------------------------------------------------------
cycleDetected() const586 bool ctkDependencyGraph::cycleDetected()const
587 {
588 return d_ptr->CycleDetected;
589 }
590
591 //----------------------------------------------------------------------------
cycleOrigin() const592 int ctkDependencyGraph::cycleOrigin()const
593 {
594 return d_ptr->CycleOrigin;
595 }
596
597 //----------------------------------------------------------------------------
cycleEnd() const598 int ctkDependencyGraph::cycleEnd()const
599 {
600 return d_ptr->CycleEnd;
601 }
602
603 //----------------------------------------------------------------------------
insertEdge(int from,int to)604 void ctkDependencyGraph::insertEdge(int from, int to)
605 {
606 assert(from > 0 && from <= d_ptr->NVertices);
607 assert(to > 0 && to <= d_ptr->NVertices);
608
609 // resize if needed
610 size_t capacity = d_ptr->Edges[from]->capacity();
611 if (d_ptr->OutDegree[from] > static_cast<int>(capacity))
612 {
613 d_ptr->Edges[from]->resize(capacity + capacity * 0.3);
614 }
615
616 d_ptr->setEdge(from, d_ptr->OutDegree[from], to);
617 d_ptr->OutDegree[from]++;
618 d_ptr->InDegree[to]++;
619
620 d_ptr->NEdges++;
621 }
622
623 //----------------------------------------------------------------------------
findPaths(int from,int to,std::list<std::list<int> * > & paths)624 void ctkDependencyGraph::findPaths(int from, int to, std::list<std::list<int>* >& paths)
625 {
626 std::list<int>* path = new std::list<int>;
627 (*path).push_back(from);
628 (paths).push_back(path);
629 d_ptr->findPathsRec(from, to, path, paths);
630
631 // Remove lists not ending with the requested element
632 std::list<std::list<int>* >::iterator pathsIterator;
633 pathsIterator = paths.begin();
634
635 while (paths.size() > 0 && pathsIterator != paths.end())
636 {
637 std::list<int>* pathToCheck = (*pathsIterator);
638 assert(pathToCheck);
639
640 if (*(pathToCheck->rbegin()) != to)
641 {
642 pathsIterator = paths.erase(pathsIterator);
643 }
644 else
645 {
646 pathsIterator++;
647 }
648 }
649 }
650
651 //----------------------------------------------------------------------------
findPath(int from,int to,std::list<int> & path)652 void ctkDependencyGraph::findPath(int from, int to, std::list<int>& path)
653 {
654 std::list<std::list<int>* > paths;
655 this->findPaths(from, to, paths);
656
657 if (!paths.empty())
658 {
659 std::list<int>::iterator pathIterator;
660 for (pathIterator = (*(paths.begin()))->begin(); pathIterator != (*(paths.begin()))->end(); pathIterator++)
661 {
662 path.push_back(*pathIterator);
663 }
664 }
665
666 std::list<std::list<int>* >::iterator pathsIterator;
667 for(pathsIterator = paths.begin(); pathsIterator != paths.end(); pathsIterator++)
668 {
669 if (*pathsIterator != NULL)
670 {
671 delete *pathsIterator;
672 }
673 }
674 }
675
676 //----------------------------------------------------------------------------
topologicalSort(std::list<int> & sorted,int rootId)677 bool ctkDependencyGraph::topologicalSort(std::list<int>& sorted, int rootId)
678 {
679 if (rootId > 0)
680 {
681 ctkDependencyGraph subgraph(d_ptr->subgraphSize(rootId));
682 std::map<int,int> subgraphIdToGlobal;
683 std::map<int,int> globalIdToSubgraph;
684 d_ptr->subgraphInsert(subgraph, rootId, subgraphIdToGlobal, globalIdToSubgraph);
685
686 std::list<int> subgraphSorted;
687 bool result = subgraph.topologicalSort(subgraphSorted);
688 std::list<int>::const_iterator subgraphSortedIterator;
689 for (subgraphSortedIterator = subgraphSorted.begin(); subgraphSortedIterator != subgraphSorted.end(); subgraphSortedIterator++)
690 {
691 sorted.push_back(subgraphIdToGlobal[*subgraphSortedIterator]);
692 }
693 return result;
694 }
695
696 std::vector<int> outdegree; // outdegree of each vertex
697 outdegree.resize(MAXV);
698 std::queue<int> zeroout; // vertices of outdegree 0
699 int x, y; // current and next vertex
700
701 outdegree.resize(d_ptr->NVertices + 1);
702
703 // resize if needed
704 if (d_ptr->NVertices > MAXV)
705 {
706 outdegree.resize(d_ptr->NVertices);
707 }
708
709 d_ptr->computeOutdegrees(outdegree);
710
711 for (int i=1; i <= d_ptr->NVertices; i++)
712 {
713 if (outdegree[i] == 0)
714 {
715 zeroout.push(i);
716 }
717 }
718
719 int j=0;
720 while (zeroout.empty() == false)
721 {
722 j = j+1;
723 x = zeroout.front();
724 zeroout.pop();
725 sorted.push_back(x);
726 for (int i=0; i < d_ptr->OutDegree[x]; i++)
727 {
728 y = d_ptr->edge(x, i);
729 outdegree[y] --;
730 if (outdegree[y] == 0)
731 {
732 zeroout.push(y);
733 }
734 }
735 }
736
737 if (j != d_ptr->NVertices)
738 {
739 return false;
740 }
741
742 return true;
743 }
744
745 //----------------------------------------------------------------------------
sourceVertices(std::list<int> & sources)746 void ctkDependencyGraph::sourceVertices(std::list<int>& sources)
747 {
748 d_ptr->verticesWithIndegree(0, sources);
749 }
750