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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 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}
|
