report/ass2.tex

   1 \subsection{Implementation of the hitting-set algorithm}
   2 \subsubsection{Task 12: Generate conflict}
   3 Can be found in \textit{./src/task12.pl} or in Listing~\ref{task12}.
   4
   5 \subsubsection{Task 13: Define your data structure}
   6 Can be found in \textit{./src/hs.pl} or in Listing~\ref{hs}.
   7 \begin{figure}[H]
   8         \caption{Examples of good hitting set trees}
   9         \begin{tikzpicture}     [grow=down]
  10         \node[bag] {\{$a, b\}$}
  11                 child {
  12                         node[end, label=below:$\checkmark$]{}
  13                         edge from parent
  14                         node[left] {$a$}
  15                 }
  16                 child {
  17                         node[end, label=below:$\checkmark$]{}
  18                         edge from parent
  19                         node[right] {$b$}
  20                 };
  21         \end{tikzpicture}
  22         \begin{tikzpicture}     [grow=down]
  23         \node[bag] {\{$a, b\}$}
  24                 child {
  25                         node[bag] {$\{c, d\}$}
  26                         child {
  27                                 node[end, label=below:$\checkmark$]{}
  28                                 edge from parent
  29                                 node[left] {$c$}
  30                         }
  31                         child {
  32                                 node[end, label=below:$\checkmark$]{}
  33                                 edge from parent
  34                                 node[left] {$d$}
  35                         }
  36                         edge from parent
  37                         node[left] {$a$}
  38                 }
  39                 child {
  40                         node[end, label=below:$\checkmark$]{}
  41                         edge from parent
  42                         node[right] {$b$}
  43                 };
  44         \end{tikzpicture}
  45 \end{figure}
  46
  47 \begin{figure}[H]
  48         \caption{Examples of bad hitting set trees due to duplicate edge labels}
  49         \begin{tikzpicture}     [grow=down]
  50         \node[bag] {\{$a, b\}$}
  51                 child {
  52                         node[bag] {$\{c, a\}$}
  53                         child {
  54                                 node[end, label=below:$\checkmark$]{}
  55                                 edge from parent
  56                                 node[left] {$c$}
  57                         }
  58                         child {
  59                                 node[end, label=below:$\checkmark$]{}
  60                                 edge from parent
  61                                 node[left] {$a$}
  62                         }
  63                         edge from parent
  64                         node[left] {$a$}
  65                 }
  66                 child {
  67                         node[end, label=below:$\checkmark$]{}
  68                         edge from parent
  69                         node[right] {$b$}
  70                 };
  71         \end{tikzpicture}
  72 \end{figure}
  73
  74 \subsubsection{Task 14: Implementation}
  75 Can be found in \textit{./src/task14part1.pl} or in Listing~\ref{task14part1}.
  76 Can be found in \textit{./src/task14part2.pl} or in Listing~\ref{task14part2}.