strongconnect is the strongconnect function described in the wikipedia article.
(v int)
| 152 | // strongconnect is the strongconnect function described in the |
| 153 | // wikipedia article. |
| 154 | func (t *tarjan) strongconnect(v int) { |
| 155 | // Set the depth index for v to the smallest unused index. |
| 156 | t.index++ |
| 157 | t.indexTable[v] = t.index |
| 158 | t.lowLink[v] = t.index |
| 159 | t.stack = append(t.stack, v) |
| 160 | t.onStack[v] = true |
| 161 | |
| 162 | // Consider successors of v. |
| 163 | for w := range t.g[v] { |
| 164 | if t.indexTable[w] == 0 { |
| 165 | // Successor w has not yet been visited; recur on it. |
| 166 | t.strongconnect(w) |
| 167 | t.lowLink[v] = min(t.lowLink[v], t.lowLink[w]) |
| 168 | } else if t.onStack[w] { |
| 169 | // Successor w is in stack s and hence in the current SCC. |
| 170 | t.lowLink[v] = min(t.lowLink[v], t.indexTable[w]) |
| 171 | } |
| 172 | } |
| 173 | |
| 174 | // If v is a root node, pop the stack and generate an SCC. |
| 175 | if t.lowLink[v] == t.indexTable[v] { |
| 176 | // Start a new strongly connected component. |
| 177 | var ( |
| 178 | scc []int |
| 179 | w int |
| 180 | ) |
| 181 | for { |
| 182 | w, t.stack = t.stack[len(t.stack)-1], t.stack[:len(t.stack)-1] |
| 183 | t.onStack[w] = false |
| 184 | // Add w to current strongly connected component. |
| 185 | scc = append(scc, w) |
| 186 | if w == v { |
| 187 | break |
| 188 | } |
| 189 | } |
| 190 | // Output the current strongly connected component. |
| 191 | t.sccs = append(t.sccs, scc) |
| 192 | } |
| 193 | } |
| 194 | |
| 195 | // sccSubGraph returns the graph of the tarjan's strongly connected |
| 196 | // components with each SCC containing at least min vertices. |