From 190240fc1bda361a45ad3c629ba3bb2fcdfeed00 Mon Sep 17 00:00:00 2001
From: Yigit Sever
Date: Sun, 15 Nov 2020 19:54:57 +0300
Subject: Expand question 2, include tikz diagram

---
 main.pdf      | Bin 199456 -> 204681 bytes
 main.tex      |  86 ++++++++++++++++++++++++++++++++++++++++++++++++++++------
 structure.tex |   1 +
 3 files changed, 78 insertions(+), 9 deletions(-)

diff --git a/main.pdf b/main.pdf
index 6fc1345..90b5044 100644
Binary files a/main.pdf and b/main.pdf differ
diff --git a/main.tex b/main.tex
index ceb8e92..96c5d5b 100644
--- a/main.tex
+++ b/main.tex
@@ -85,13 +85,79 @@ With the assumption that accessing the labels $(u, w)$ takes $\mathcal{O}(1)$ ti
 \section{Reachability}%
 \label{sec:reachability}
 
-First, compute all strongly connected components (SCCs) of $G$ by using~\parencite{tarjanDepthFirst1972} per \emph{page 72} of the \nth{3} lecture notes in $\mathcal{O}(E+V)$ time. Instead of labelling the SCCs with the root node, we will initially label all nodes of the SCC $F'$ with the $min(u)$ of the connected component.
+The intuition for this question can be illustrated as follows;
 
-Then, by ignoring the tree edges, shrink the graph $G$ such that $E' = {(v, w)~|~v \in F', w \in F''}$, leaving only cross links behind. This step takes another $\mathcal{O}(E+V)$ time.
+If $G$ is strongly connected then the answer is trivial; every vertex have the same $\min(u) = 1$.
 
-Now run the topological sort algorithm presented in \emph{page 84} of the \nth{3} lecture notes this operation is yet again $\mathcal{O}(E+V)$.
+For a directed acyclic graph, consider the scenario below;
 
-Finally, reverse the direction of the edges on the graph that have been output by the topological sort and starting from the new root node, traverse the graph downwards and update the $min(u)$ of every SCC as follows;
+\begin{tikzpicture}
+    [vertex/.style={circle,draw,thick,minimum size=6mm,inner sep=10pt},
+    edge/.style={->,>=stealth',line width=1pt]}]
+
+    \node[vertex] (0) {$a$};
+    \node[vertex] (1) [right=of 0] {$b$};
+    \node[vertex] (2) [right=of 1] {$c$};
+    \node[vertex] (3) [right=of 2] {$d$};
+
+    \node [above,xshift=-5mm] at (0.north west) {$L(u) = 4$};
+    \node [above] at (1.north) {$L(u) = 1$};
+    \node [above] at (2.north) {$L(u) = 3$};
+    \node [above,xshift=5mm] at (3.north east) {$L(u) = 2$};
+
+    % \node [red,below] at (0.south) {$\min(u) = 1$};
+    % \node [red,below] at (1.south) {$\min(u) = 1$};
+    % \node [red,below] at (2.south) {$\min(u) = 2$};
+    % \node [red,below] at (3.south) {$\min(u) = 3$};
+
+    \draw [edge] (0) to (1);
+    \draw [edge,bend left=45] (0) to (3);
+    \draw [edge] (1) to (2);
+    \draw [edge] (2) to (3);
+\end{tikzpicture}
+
+We can assign the $\min(u)$ values on this directed acyclic graph by reversing the direction of the edges and traversing the graph, keeping a minimum $\min(u)$ encountered so far for the nodes;
+
+\begin{tikzpicture}
+    [vertex/.style={circle,draw,thick,minimum size=6mm,inner sep=10pt},
+    edge/.style={<-,>=stealth',line width=1pt]}]
+
+    \node[vertex] (0) {$a$};
+    \node[vertex] (1) [right=of 0] {$b$};
+    \node[vertex] (2) [right=of 1] {$c$};
+    \node[vertex] (3) [right=of 2] {$d$};
+
+    \node [above,xshift=-5mm] at (0.north west) {$L(u) = 4$};
+    \node [above] at (1.north) {$L(u) = 1$};
+    \node [above] at (2.north) {$L(u) = 3$};
+    \node [above,xshift=5mm] at (3.north east) {$L(u) = 2$};
+
+    \node [red,below] at (0.south) {$\min(u) = 1$};
+    \node [red,below] at (1.south) {$\min(u) = 1$};
+    \node [red,below] at (2.south) {$\min(u) = 2$};
+    \node [red,below] at (3.south) {$\min(u) = 2$};
+
+    \draw [edge] (0) to (1);
+    \draw [edge,bend left=45] (0) to (3);
+    \draw [edge] (1) to (2);
+    \draw [edge] (2) to (3);
+\end{tikzpicture}
+
+Starting from the \enquote{root} \texttt{d}, the $\min(u)$ is $2$, which is assigned to the immediate neighbours of \texttt{d}, \texttt{c} and \texttt{a}.
+When the traversal \emph{reaches} \texttt{b}, \texttt{b} sets the current $\min(u)$ to $1$ and \texttt{a}'s $\min(u)$ value is updated to $1$ as well.
+
+With the intuition out of the way, we will generalize the problem.
+First, compute all strongly connected components (SCCs) of $G$ by using~\parencite{tarjanDepthFirst1972} per \emph{page 72} of the \nth{3} lecture notes in $\mathcal{O}(E+V)$ time.
+Instead of labelling the SCCs with their root node, we will initially label all nodes of the SCC $F'$ with the $\min(u)$ of the connected component; $\min(a) ~ \text{of} ~ a \in F' = \min{\{L(w) : w \in F'\}}$.
+
+Then, by ignoring the tree edges, \emph{shrink} the graph $G$ such that $E' = \{(v, w)~|~v \in F', w \in F''\}$, leaving only cross links behind.
+This step takes another $\mathcal{O}(E+V)$ time.
+
+Now run the topological sort algorithm presented in \emph{page 84} of the \nth{3} lecture notes.
+This operation is yet again $\mathcal{O}(E+V)$.
+
+We now have a scenario like the one illustrated above.
+Reverse the direction of the edges on the graph that have been output by the topological sort and starting from the new root node, traverse the graph downwards and update the $\min(u)$ of every SCC in $\mathcal{O}(m+n)$ time as follows;
 
 {\centering
     \begin{minipage}{.7\linewidth}
@@ -100,13 +166,13 @@ Finally, reverse the direction of the edges on the graph that have been output b
             \SetAlgoLongEnd{}
             \KwData{$G'$ = topological sorted G with reversed edges}
             \KwResult{$\min(u)$ for all vertices $u \in V$}
-            $\text{mostmin} \longleftarrow \min(\text{root})$\;
-            \While{traversing $G'$ downwards with current node $v$}{
-                \uIf{$\min(v) < mostmin$}{
-                    $\text{mostmin} \longleftarrow \min(v)$\;
+            $\text{minnest} \longleftarrow \min(\text{root})$\;
+            \While(\tcp*[f]{$m+n$}){traversing $G'$ downwards with current node $v$}{
+                \uIf{$\min(v) < minnest$}{
+                    $\text{minnest} \longleftarrow \min(v)$\;
                 }
                 \Else{
-                    label $v$ as $mostmin$
+                    label $v$ as $minnest$
                 }
             }
             \caption{Updating $\min(u)$ of the SCCs}%
@@ -116,6 +182,8 @@ Finally, reverse the direction of the edges on the graph that have been output b
     \par
 }
 
+Finally, update the $\min(u)$ of every node $w \in G$ to match the cross link edges of the SCC they belong to. This operation is yet another $\mathcal{O}(m+n)$ traversal.
+
 \printbibliography
 
 \end{document}
diff --git a/structure.tex b/structure.tex
index c504c76..3d039b4 100644
--- a/structure.tex
+++ b/structure.tex
@@ -35,6 +35,7 @@
 \usepackage[super]{nth}
 \usepackage{caption}
 \usepackage{tikz}
+\usetikzlibrary{arrows,fit,positioning}
 \usepackage[style=authoryear]{biblatex}
 
 
-- 
cgit v1.2.3-70-g09d2