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 \begin{figure}[H]
  15         \caption{Examples of good hitting set trees}
  16         \begin{tikzpicture}     [grow=down]
  17         \node[bag] {\{$a, b\}$}
  18                 child {
  19                         node[end, label=below:$\checkmark$]{}
  20                         edge from parent
  21                         node[left] {$a$}
  22                 }
  23                 child {
  24                         node[end, label=below:$\checkmark$]{}
  25                         edge from parent
  26                         node[right] {$b$}
  27                 };
  28         \end{tikzpicture}
  29         \begin{tikzpicture}     [grow=down]
  30         \node[bag] {\{$a, b\}$}
  31                 child {
  32                         node[bag] {$\{c, d\}$}
  33                         child {
  34                                 node[end, label=below:$\checkmark$]{}
  35                                 edge from parent
  36                                 node[left] {$c$}
  37                         }
  38                         child {
  39                                 node[end, label=below:$\checkmark$]{}
  40                                 edge from parent
  41                                 node[left] {$d$}
  42                         }
  43                         edge from parent
  44                         node[left] {$a$}
  45                 }
  46                 child {
  47                         node[end, label=below:$\checkmark$]{}
  48                         edge from parent
  49                         node[right] {$b$}
  50                 };
  51         \end{tikzpicture}
  52 \end{figure}
  53
  54 \begin{figure}[H]
  55         \caption{Examples of bad hitting set trees due to duplicate edge labels}
  56         \begin{tikzpicture}     [grow=down]
  57         \node[bag] {\{$a, b\}$}
  58                 child {
  59                         node[bag] {$\{c, a\}$}
  60                         child {
  61                                 node[end, label=below:$\checkmark$]{}
  62                                 edge from parent
  63                                 node[left] {$c$}
  64                         }
  65                         child {
  66                                 node[end, label=below:$\checkmark$]{}
  67                                 edge from parent
  68                                 node[left] {$a$}
  69                         }
  70                         edge from parent
  71                         node[left] {$a$}
  72                 }
  73                 child {
  74                         node[end, label=below:$\checkmark$]{}
  75                         edge from parent
  76                         node[right] {$b$}
  77                 };
  78         \end{tikzpicture}
  79 \end{figure}
  80
  81 \subsubsection{Task 14: Implementation}
  82 \begin{listing}[H]
  83         \caption{Code for generating a hitting set tree}
  84         \prologcode{./src/task14part1.pl}
  85 \end{listing}
  86
  87 \begin{listing}[H]
  88         \caption{Code for generating a minimal hitting sets}
  89         \prologcode{./src/task14part2.pl}
  90 \end{listing}