mooie boom gemaakt en jou lelijke boom weggehaald

[ker1415-1.git] / report / ass2.tex

diff --git a/report/ass2.tex b/report/ass2.tex
index 32f6adf..c0860d1 100644 (file)
--- a/report/ass2.tex
+++ b/report/ass2.tex
@@ -5,20 +5,85 @@
        \prologcode{./src/task12.pl}
 \end{listing}
 
-
 \subsubsection{Task 13: Define your data structure}
 \begin{listing}[H]
        \caption{Hitting set datastructure}
        \prologcode{./src/hs.pl}
 \end{listing}
-Our datastructure uses the predicate node to signify nodes and leaf for leaves. A node contains a list of edge labels and another list (with the same length as the amound of edge labels) that contains nodes or leaves. The edge label corresponds with its order in the list it is in.
-Examples:
-node([a,b],[leaf,leaf])
-node([a,b], [node([c,d], [leaf,leaf]), node([e,f], [leaf,leaf])])
-node([a,b], [node([c,d], [node([g,h,i], [leaf,leaf,leaf]),leaf]), node([a,f], [leaf,leaf])])
-%insert hittingsettrees.png
+
+\tikzstyle{level 1}=[level distance=1cm, sibling distance=1cm]
+\tikzstyle{level 2}=[level distance=1cm, sibling distance=1cm]
+\tikzstyle{bag} = [text width=4em, text centered]
+\tikzstyle{end} = [minimum width=3pt, inner sep=0pt]
+\begin{figure}[H]
+       \caption{Examples of good hitting set trees}
+       \begin{tikzpicture}     [grow=down]
+       \node[bag] {\{$a, b\}$}
+               child {
+                       node[end, label=below:$\checkmark$]{}
+                       edge from parent
+                       node[left] {$a$}
+               }
+               child {
+                       node[end, label=below:$\checkmark$]{}
+                       edge from parent
+                       node[right] {$b$}
+               };
+       \end{tikzpicture}
+       \begin{tikzpicture}     [grow=down]
+       \node[bag] {\{$a, b\}$}
+               child {
+                       node[bag] {$\{c, d\}$}
+                       child {
+                               node[end, label=below:$\checkmark$]{}
+                               edge from parent
+                               node[left] {$c$}
+                       }
+                       child {
+                               node[end, label=below:$\checkmark$]{}
+                               edge from parent
+                               node[left] {$d$}
+                       }
+                       edge from parent
+                       node[left] {$a$}
+               }
+               child {
+                       node[end, label=below:$\checkmark$]{}
+                       edge from parent
+                       node[right] {$b$}
+               };
+       \end{tikzpicture}
+\end{figure}
+
+\begin{figure}[H]
+       \caption{Examples of bad hitting set trees due to duplicate edge labels}
+       \begin{tikzpicture}     [grow=down]
+       \node[bag] {\{$a, b\}$}
+               child {
+                       node[bag] {$\{c, a\}$}
+                       child {
+                               node[end, label=below:$\checkmark$]{}
+                               edge from parent
+                               node[left] {$c$}
+                       }
+                       child {
+                               node[end, label=below:$\checkmark$]{}
+                               edge from parent
+                               node[left] {$a$}
+                       }
+                       edge from parent
+                       node[left] {$a$}
+               }
+               child {
+                       node[end, label=below:$\checkmark$]{}
+                       edge from parent
+                       node[right] {$b$}
+               };
+       \end{tikzpicture}
+\end{figure}
+
 \subsubsection{Task 14: Implementation}
 \begin{listing}[H]
        \caption{Code for generating a hitting set tree}
        \prologcode{./src/task14.pl}
-\end{listing}
\ No newline at end of file
+\end{listing}