%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Lachaise Assignment
% LaTeX Template
% Version 1.0 (26/6/2018)
%
% This template originates from:
% http://www.LaTeXTemplates.com
%
% Authors:
% Marion Lachaise & François Févotte
% Vel (vel@LaTeXTemplates.com)
%
% License:
% CC BY-NC-SA 3.0 (http://creativecommons.org/licenses/by-nc-sa/3.0/)
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\documentclass{article}
\input{structure.tex}

\title{CENG567: Homework \#2}
\author{Yiğit Sever}
\date{\today}

%----------------------------------------------------------------------------------------

\begin{document}

\maketitle

\section{Checking Consistency of Judgements}%
\label{sec:checking_consistency_of_judgements}

Given the collection of $n$ butterflies and a potential judgement between every pair (or not if the judgement is ambiguous), we have a graph $G = (V, E)$ with $n = |V|$ vertices and $|E| = m \le \frac{n(n-1)}{2}$ edges, with every edge $(i, j) \in E$ labelled either \enquote{same} or \enquote{different}. At the end of our algorithm, the vertices should be \emph{consistently} labelled as either \texttt{A} and \texttt{B} or our algorithm should be able to prove that $G$ cannot be labelled as so.

A modified graph traversal using either BFS or DFS (since a node can be discovered multiple times in both of them) will work. Here we will modify the graph traversal given on \emph{page 42} on our \nth{3} lecture slides that uses BFS. The input of the algorithm is a node $s \in E$. If, due to ambiguous (i.e.\ missing) nodes, the graph is not connected, the algorithm should be run until every connected component is discovered.
% TODO: run until every cc is discovered is handwavey <15-11-20, yigit> %

{\centering
    \begin{minipage}{.7\linewidth}
        \begin{algorithm}[H]
            \SetKwProg{Fn}{function}{}{end}
            \DontPrintSemicolon{}
            \SetAlgoLongEnd{}
            \Fn{consistency\_check(s: node)}{
                \KwData{$K$ = data structure of discovered nodes}
                \KwResult{boolean = whether $G$ is consistent or not}
                \textbf{label} $s$ as \texttt{A} \tcc*[r]{the opposite label is B}
                put $s$ in $K$\;
                \While{$K$ is not empty}{
                    take a node $v$ from $K$\;
                    \If{$v$ is not marked \enquote{explored}}{
                        mark $v$ \enquote{explored}\;
                        \For{each edge $(v, w)$ incident to $v$}{
                            \uIf{$w$ is labelled}{
                                \If{the label of $w$ is not consistent with the label of $v$ with respect to the judgement $(v,w$)}{
                                    terminate the algorithm; $G$ is \textbf{inconsistent}\;
                                }
                            }
                            \Else{
                                \uIf{$(v,w)$ is labelled \enquote{same}}{
                                    \textbf{label} $w$ with the label of $v$\;
                                }
                                \Else(\tcc*[f]{$(v,w)$ is labelled \enquote{different}}){
                                    \textbf{label} $w$ with the opposite label of $v$\;
                                }
                            }
                            put $w$ in $K$\;
                        }
                    }
                }
                the spanned connected component is \textbf{consistent}
            }
            \caption{Modified graph traversal algorithm so solve judgement consistency checking problem}%
            \label{alg:question_1}
        \end{algorithm}
    \end{minipage}
    \par
}

With the assumption that accessing the labels $(u, w)$ takes $\mathcal{O}(1)$ time this algorithm has the same running time as BFS; $\mathcal{O}(m+n)$.


\section{Reachability}%
\label{sec:reachability}

\end{document}