Added Tarjan's SCC algorithm section to Strongly Connected Components article #1569
Conversation
adamant-pwn
left a comment
adamant-pwn
left a comment
There was a problem hiding this comment.
Thanks for the PR! I left some (mostly minor) suggestions to improve it before merging.
| ### Description of the algorithm | ||
| The described algorithm was first suggested by Tarjan in 1972. | ||
| It is based on performing a sequence of `dfs` calls, using information inherent to its structure to determine the strongly connected components (`SCC`), with a runtime of $O(n+m)$. |
There was a problem hiding this comment.
Here and further, I don't think we should use SCC, dfs as inline code blocks. Just use "DFS" / "SCC", unless you specifically refer to a function.
| Once we first call a `dfs` on a vertex from an `SCC`, all the vertices of its `SCC` will be visited before this call ends, since they are all reachable from each other. | ||
| In the `dfs` tree, this first vertex will be a common ancestor to all other vertices of the `SCC`; we define this vertex to be the **root of the `SCC`**. | ||
| **Theorem.** All vertices of an `SCC` induce a connected subgraph of the `dfs` tree. |
There was a problem hiding this comment.
What do you think about using admonitions for Theorem/Proof blocks, like in continued fractions? We could also mark the proof as a drop-down this way, so people who aren't very interested can skip it.
It would also be more clear where the proof has ended this way.
There was a problem hiding this comment.
I don't mind doing it that way, and it does become clearer where the proof ends.
| these vertices cannot reach an ancestor of $v$, since if they did, they would belong to the same `SCC` as $v$, which is impossible since their `SCC` has already been determined. | ||
| Since no ancestor of $v$ is reachable from its subtree, the root of $v$ must be $v$ itself. | ||
| Now, we must find the method that let's us determine if a vertex is a root or not, and the claiming process properties are necessary for its correctness. |
There was a problem hiding this comment.
| Now, we must find the method that let's us determine if a vertex is a root or not, and the claiming process properties are necessary for its correctness. | |
| Now, we must find the method that lets us determine if a vertex is a root or not, and the claiming process properties are necessary for its correctness. |
| } | ||
| } | ||
| ``` | ||
|
|
There was a problem hiding this comment.
Let's also make a submission with this algorithm on Library Checker, and add the link to it.
| dfs(u, adj); | ||
| t_low[v] = min(t_low[v], t_low[u]); | ||
| } else if (roots[u] == -1) { // back-edge, cross-edge or forward-edge to an unclaimed vertex | ||
| t_low[v] = min(t_low[v], t_in[u]); |
There was a problem hiding this comment.
What I really like about the standard version of t_in and t_low computation is that it works also for biconnected components and two-edge-connected components. The version above seems to only work for SCC and two-edge-connected components, but not for BCC (and articulation points?).
I think it's best to use this, consistently with the theory, unless we really have a reason not to.
There was a problem hiding this comment.
I will swap them then, I'll put the version that is consistent with the definition of t_low in the implementation block and add a note for the alternative version.
There are reference implementations that use it so I think it's worth mentioning it.
…compute SCCs in reversed topological order; added Library Checker submission; added admonitions to theorems and proofs; swapped `t_out` computation method with the one in remark
2 participants
Added Tarjan's SCC algorithm section to Strongly Connected Components article, as well as tests.
Fixed a bug in Kosaraju code, where the root of a component was the vertex with minimum value, instead of the first value as described.
The tests were updated to reflect the change.