report/ass2.tex

   1 \subsection{Implementation of the hitting-set algorithm}
   2 \subsubsection{Task 12: Generate conflict}
   3 \begin{listing}[H]
   4         \caption{Generating conflict sets}
   5         \prologcode{./src/task12.pl}
   6 \end{listing}
   7
   8 \subsubsection{Task 13: Define your data structure}
   9 \begin{listing}[H]
  10         \caption{Hitting set datastructure}
  11         \prologcode{./src/hs.pl}
  12 \end{listing}
  13
  14 \tikzstyle{level 1}=[level distance=1cm, sibling distance=1cm]
  15 \tikzstyle{level 2}=[level distance=1cm, sibling distance=1cm]
  16 \tikzstyle{bag} = [text width=4em, text centered]
  17 \tikzstyle{end} = [minimum width=3pt, inner sep=0pt]
  18 \begin{figure}[H]
  19         \caption{Examples of good hitting set trees}
  20         \begin{tikzpicture}     [grow=down]
  21         \node[bag] {\{$a, b\}$}
  22                 child {
  23                         node[end, label=below:$\checkmark$]{}
  24                         edge from parent
  25                         node[left] {$a$}
  26                 }
  27                 child {
  28                         node[end, label=below:$\checkmark$]{}
  29                         edge from parent
  30                         node[right] {$b$}
  31                 };
  32         \end{tikzpicture}
  33         \begin{tikzpicture}     [grow=down]
  34         \node[bag] {\{$a, b\}$}
  35                 child {
  36                         node[bag] {$\{c, d\}$}
  37                         child {
  38                                 node[end, label=below:$\checkmark$]{}
  39                                 edge from parent
  40                                 node[left] {$c$}
  41                         }
  42                         child {
  43                                 node[end, label=below:$\checkmark$]{}
  44                                 edge from parent
  45                                 node[left] {$d$}
  46                         }
  47                         edge from parent
  48                         node[left] {$a$}
  49                 }
  50                 child {
  51                         node[end, label=below:$\checkmark$]{}
  52                         edge from parent
  53                         node[right] {$b$}
  54                 };
  55         \end{tikzpicture}
  56 \end{figure}
  57
  58 \begin{figure}[H]
  59         \caption{Examples of bad hitting set trees due to duplicate edge labels}
  60         \begin{tikzpicture}     [grow=down]
  61         \node[bag] {\{$a, b\}$}
  62                 child {
  63                         node[bag] {$\{c, a\}$}
  64                         child {
  65                                 node[end, label=below:$\checkmark$]{}
  66                                 edge from parent
  67                                 node[left] {$c$}
  68                         }
  69                         child {
  70                                 node[end, label=below:$\checkmark$]{}
  71                                 edge from parent
  72                                 node[left] {$a$}
  73                         }
  74                         edge from parent
  75                         node[left] {$a$}
  76                 }
  77                 child {
  78                         node[end, label=below:$\checkmark$]{}
  79                         edge from parent
  80                         node[right] {$b$}
  81                 };
  82         \end{tikzpicture}
  83 \end{figure}
  84
  85 \subsubsection{Task 14: Implementation}
  86 \begin{listing}[H]
  87         \caption{Code for generating a hitting set tree}
  88         \prologcode{./src/task14.pl}
  89 \end{listing}