§ 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