| 51 | } |
| 52 | |
| 53 | void cmComputeComponentGraph::TarjanVisit(size_t i) |
| 54 | { |
| 55 | // We are now visiting this node. |
| 56 | this->TarjanVisited[i] = this->TarjanWalkId; |
| 57 | |
| 58 | // Initialize the entry. |
| 59 | this->TarjanEntries[i].Root = i; |
| 60 | this->TarjanComponents[i] = INVALID_COMPONENT; |
| 61 | this->TarjanEntries[i].VisitIndex = ++this->TarjanIndex; |
| 62 | this->TarjanStack.push(i); |
| 63 | |
| 64 | // Follow outgoing edges. |
| 65 | EdgeList const& nl = this->InputGraph[i]; |
| 66 | for (cmGraphEdge const& ni : nl) { |
| 67 | size_t j = ni; |
| 68 | |
| 69 | // Ignore edges to nodes that have been reached by a previous DFS |
| 70 | // walk. Since we did not reach the current node from that walk |
| 71 | // it must not belong to the same component and it has already |
| 72 | // been assigned to a component. |
| 73 | if (this->TarjanVisited[j] > 0 && |
| 74 | this->TarjanVisited[j] < this->TarjanWalkId) { |
| 75 | continue; |
| 76 | } |
| 77 | |
| 78 | // Visit the destination if it has not yet been visited. |
| 79 | if (!this->TarjanVisited[j]) { |
| 80 | this->TarjanVisit(j); |
| 81 | } |
| 82 | |
| 83 | // If the destination has not yet been assigned to a component, |
| 84 | // check if it has a better root for the current object. |
| 85 | if (this->TarjanComponents[j] == INVALID_COMPONENT) { |
| 86 | if (this->TarjanEntries[this->TarjanEntries[j].Root].VisitIndex < |
| 87 | this->TarjanEntries[this->TarjanEntries[i].Root].VisitIndex) { |
| 88 | this->TarjanEntries[i].Root = this->TarjanEntries[j].Root; |
| 89 | } |
| 90 | } |
| 91 | } |
| 92 | |
| 93 | // Check if we have found a component. |
| 94 | if (this->TarjanEntries[i].Root == i) { |
| 95 | // Yes. Create it. |
| 96 | size_t c = this->Components.size(); |
| 97 | this->Components.emplace_back(); |
| 98 | NodeList& component = this->Components[c]; |
| 99 | |
| 100 | // Populate the component list. |
| 101 | size_t j; |
| 102 | do { |
| 103 | // Get the next member of the component. |
| 104 | j = this->TarjanStack.top(); |
| 105 | this->TarjanStack.pop(); |
| 106 | |
| 107 | // Assign the member to the component. |
| 108 | this->TarjanComponents[j] = c; |
| 109 | this->TarjanEntries[j].Root = i; |
| 110 | |