§ Strongly Connected Components via Kosaraju's algorithm
We know that a directed graph can be written as two-levels, a top-level dag,
with each node in the DAG being a condensation of the original graph. So
we wish to discover the DAG, and then each condensation. We wish to
view Kosaraju's algorithm as a "stronger topological sort" that works
for general graphs, and not just DAGs.
§ Step 1: Discover the tree/DAG
Run a bog standard DFS on the graph and record entry and exit times,
because that tell us everything we need to know about the DFS. Let's decide
what to keep and throw away next.
§ Step 2: Think
If we had a DAG, then we would be done; We sort the nodes according
to descending order of exit times, and we get the topological order
of the DAG. However, this is incorrect for our purposes, as this
only gives us the components if we don't have cycles.
§ Step 3: Mix in cycle detection/single SSC
Pick the first node according the topological sort heurstic --- the node
that's earliest according to exit time. We now need to discover cycles.
Recall that we built the DAG according to DFS order, so if we run a DFS
again, we'll get the entire subtree in the DAG! Rather, we want the
"anti DFS": whatever can reach the 'root' of the 'DAG'. To find this,
we reverse the DAG and find the component reachable from here.
§ SCC's as adjunction
I learnt this from Benjamin Pierce's "Category theory for computer scientists":
The strong components of a graph themselves form an acyclic graph that is a quotient of the original graph-that is, each node corresponds to an equivalence class of strongly connected nodes in the original. The mapping taking a graph to the acyclic graph of its strongly connected components may be expressed as a left adjoint to the inclusion functor from AcyclicGraph to Graph
§ References