| 29 | } |
| 30 | |
| 31 | void cmComputeComponentGraph::Tarjan() |
| 32 | { |
| 33 | size_t n = this->InputGraph.size(); |
| 34 | TarjanEntry entry = { 0, 0 }; |
| 35 | this->TarjanEntries.resize(0); |
| 36 | this->TarjanEntries.resize(n, entry); |
| 37 | this->TarjanComponents.resize(0); |
| 38 | this->TarjanComponents.resize(n, INVALID_COMPONENT); |
| 39 | this->TarjanWalkId = 0; |
| 40 | this->TarjanVisited.resize(0); |
| 41 | this->TarjanVisited.resize(n, 0); |
| 42 | for (size_t i = 0; i < n; ++i) { |
| 43 | // Start a new DFS from this node if it has never been visited. |
| 44 | if (!this->TarjanVisited[i]) { |
| 45 | assert(this->TarjanStack.empty()); |
| 46 | ++this->TarjanWalkId; |
| 47 | this->TarjanIndex = 0; |
| 48 | this->TarjanVisit(i); |
| 49 | } |
| 50 | } |
| 51 | } |
| 52 | |
| 53 | void cmComputeComponentGraph::TarjanVisit(size_t i) |
| 54 | { |
no test coverage detected