Strong Connectivity(DAGs)¶
A graph is strongly connected if there is a path from any node to all other nodes in the graph
The strongly connected components of a graph divide the graph into strongly connected parts that are as large as possible.
The strongly connected components form an acyclic component graph that represents deep structure of original graph.
A component graph is a cyclic, directed graph, so it is easior to process than the original graph. Since the graph does not contain cycles, we can always construct a topological sort and use dynamic programming techniques.
Kosaraju's algorithm¶
Kosaraju's algorithm is an efficient method for finding the strongly connected components of a directed graph.
The algorithm performs two depthfirst search
the first search constructs a list of nodes according to the structure of the graph the second search forms the strongly connected components.
1. Search 1¶
The first phase of Kosaraju's algorithm constructs a list of nodes in the order in which a depthfirst search processes them. The algorithm goes through the nodes, and begins a depthfirst search at each unprocessed node. Each node will be added to the list after it has been processed.
2. Search 2¶
The second phase of the algorithm forms the strongly connected components of the graph. First, the algorithm reverses every edge in the graph. This guarantees that during second search, we will always find strongly connected components that do not have extra nodes.
After this, the algorithm goes through the list of nodes created by the first search, in reverse order. if a node does not belong to a component, the algorithm creates a new component and starts a depthfirst search that adds all new nodes found durin g the search to the new component
leak
Note that since all edges are reversed, the component does not leak "leak" to other pars in the graph.
Implementation¶
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 

Time complexity¶
$\Omicron(n+m)$ because the algorithm performs two depthfirst searches.
2SAT problem¶
Strong connectivity is also linked with the 2SAT problem. In this problem, we are given a logical formula for example
$$ L_1 = (x_2 \lor \neg x_1) \land (\neg x_1 \lor \neg x_2) \land (x_1 \lor x_3) \land (\neg x_2 \lor \neg x_3) \land (x_1 \lor x_4) $$
is true when the variables are assigned as follows
$$ \begin{aligned} x_1 & = false \\ x_2 & = false \\ x_3 & = true \\ x_4 & = true \\ \end{aligned} $$
The 2SAT problem can be represented as a graph whose nodes correspond to variable $x_i$ and negations $\neg x_i$, and edges determine the connections between the variables.
Each pair $(a_i \lor b_i)$ generates two edges: $\neg a_i \rarr b_i$ and $\neg b_i \rarr a_i$. This means that if $a_i$ does not hold, $b_i$ must hold, and vice versa.
The structure of the graph tells us whether it is possible to assign the values of the variables so that the formula is true.
It turns out that this can be done exactly when there are no nodes $x_i$ and $\neg x_i$ such that both nodes belong to the same strongly connected component.
If there are such nodes, the graph contains a path from $x_i$ to $\neg x_i$ and also a path from $\neg x_i$ to $x_i$, so both $x_i$ and $\neg x_i$ should be true which is not possible.
In the graph of the formula $L_1$ there are no nodes $x_i$ and $\neg x_i$ such that both nodes belong to the same strongly connected component, so solution exists.
If a solution exists, the values for the variables can be found by going through the nodes of the component graph in a reverse topological sort order.
at each step, we process a component that does not contain edges that lead to an unprocessed component. If the variables in the component have not been assigned values, their values will be determined accoring to the values in the component, and if they already have values, they remain unchanged. The process continues until each variable has been assigned a value.
this method works
because the graph has a special structure: if there are paths from node $x_i$ to node $x_j$ and from node $x_j$ to node $\neg x_j$, then node $x_i$ never becomes true. The reason for this is that there is also a path from node $\neg x_j$ to node $\neg x_j$, and both $x_i$ and $x_j$ become false.
Info
A more difficult problem is 3SAT problem, where each part of the formula is form $(a_i \lor b_i \lor c_i)$. This problem is NPhard, so no efficient algorithm for solving the problem is known.
Implementation¶
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 
