From 4cc0cb8ea0db1d21ab3107bc2110d69471d24acb Mon Sep 17 00:00:00 2001 From: Camil Staps Date: Wed, 4 Nov 2015 12:24:47 +0100 Subject: Final version report practical 1 --- Practical1/report/algorithm.tex | 71 ++++++++++++++++++++---------------- Practical1/report/analysis.tex | 24 ++++++------ Practical1/report/discussion.tex | 10 +++++ Practical1/report/implementation.tex | 17 +++------ Practical1/report/notation.tex | 6 +-- Practical1/report/report.tex | 9 +++-- 6 files changed, 75 insertions(+), 62 deletions(-) create mode 100644 Practical1/report/discussion.tex (limited to 'Practical1/report') diff --git a/Practical1/report/algorithm.tex b/Practical1/report/algorithm.tex index f6272e4..8ed3ccf 100644 --- a/Practical1/report/algorithm.tex +++ b/Practical1/report/algorithm.tex @@ -3,21 +3,25 @@ \subsection{Basic structure} \label{sec:algorithm:basic-structure} -The basic structure of the algorithm is fairly simple. For any graph $G=(V,E)$, we pick a vertex $v\in V$. Either that vertex is in an m.i.s. (and none of its neighbours), or it is not. This gives the recurrence: \refeq[basic-structure]{\ms(G) = \max(1 + \ms(G\ex \iN(v)), \ms(G\ex v)).} The rest of the algorithm will be optimising this basic structure by cleverly choosing $v$ and pruning the search tree. +The basic structure of the algorithm is fairly simple. For any graph $G=(V,E)$, we pick a vertex $v\in V$. Either that vertex is in an m.i.s. (and none of its neighbours), or it is not. This gives the recurrence: \refeq[basic-structure]{\ms(G) = \max(1 + \ms(G\ex \iN(v)), \ms(G\ex v)).} + +Every recursive algorithm needs a base case. \begin{thmproof}[base-case]{lemma}{For a graph $G$ with $|G|\leq1$, we have $\ms(G)=|G|$.} For both the cases $|G|=0$ and $|G|=1$, $G$ is an m.i.s. of itself. \end{thmproof} +The rest of this section is devoted to optimising this basic structure by cleverly choosing $v$ and pruning the search tree. + \begin{thmproof}[one-neighbour]{lemma}{For a graph $G=(V,E)$ and vertex $v\in V$, if $v$ is not in an m.i.s. there is a neighbour $w\in N(v)$ which is in an m.i.s.} By contradiction. Suppose there were an m.i.s. $ms_1$ that does not contain $v$ or one of its neighbours. Then we may create a new m.i.s. $ms_2=ms_1\with v$. We then have $|ms_2| = |ms_1|+1 > |ms_1|$. Therefore, $ms_1$ was not maximal. \end{thmproof} \begin{thmproof}[two-neighbours]{lemma}{For a graph $G=(V,E)$ and vertex $v\in V$, there is an m.i.s. with $v$, or there is an m.i.s. with two distinct elements $w_1,w_2\in N(v)$.} - By contradiction. If $v$ is in an m.i.s., we're done. If $v$ is not in an m.i.s., we know by \autoref{lem:one-neighbour} that there is a $w_1\in N(v)$ that is, say in m.i.s. $ms$. Suppose there were no other neighbour $w_2\in N(v), w_2\neq w_1$ with $w_2\in ms$. Then $ms\ex w_1\with v$ is also an m.i.s., and it does contain $v$. + By contradiction. If $v$ is in an m.i.s., we're done. If $v$ is not in an m.i.s., we know by \autoref{lem:one-neighbour} that there is a $w_1\in N(v)$ that is in an m.i.s., say $ms$. Suppose there were no other neighbour $w_2\in N(v), w_2\neq w_1$ with $w_2\in ms$. Then $ms\ex w_1\with v$ is also an m.i.s., and it does contain $v$. \end{thmproof} -At this point we define, as Robson \cite{robson}, the function $\ms^n(G,S)$ which is the $\ms(G)$ given that the m.i.s. should contain at least $n$ elements of $S$. +At this point we define, as Robson \cite{robson}, the function $\ms^n(G,S)$ as the $\ms(G)$ given that the m.i.s. should contain at least $n$ elements of $S$. Based on \autoref{lem:one-neighbour} and \ref{lem:two-neighbours} we may then rewrite \autoref{eq:basic-structure} to \refeq[with-two-neighbours]{\ms(G) = \max(1+\ms(G\ex\iN(v)), \ms^2(G\ex v, N(v))).} @@ -33,15 +37,15 @@ Until now, we have assumed that we have some vertex $v$. Let us now discuss how A straightforward implementation of $\ms^2(G\ex v,N(v))$ will consider all pairs of vertices in $N(v)$, which is quadratic. In the left-hand side, $\ms(G\ex\iN(v))$ is only linearly faster with large $d(v)$. Therefore, we should prefer small $d(v)$. \end{thmproof} -In general, we'd like to use \autoref{eq:with-two-neighbours}, because the right-hand side of the $\max$ is more restricted than in \autoref{eq:basic-structure}. However, if we have a $v$ with large $d(v)$, this may not be the case. +In general, we'd like to use \autoref{eq:with-two-neighbours}, because the right-hand side of the $\max$ is more restricted than in \autoref{eq:basic-structure}. However, if we have a $v$ with large $d(v)$, \ref{eq:basic-structure} may be more efficient. So, we should try to pick a $v$ with small $d(v)$. We apply \autoref{eq:with-two-neighbours} if $d(v)$ is small enough. If $d(v)$ is too large to ensure efficient usage of \autoref{eq:with-two-neighbours}, we apply \autoref{eq:basic-structure}. -But this latter recurrence is clearly more efficient for \emph{large} $d(v)$. Therefore, if $d(v)$ is too large to use $v$ in \autoref{eq:with-two-neighbours}, we find one of its neighbours, say $w\in N(v)$, with the largest $d(w)$, and apply \autoref{eq:basic-structure} with that vertex. In the next recurrence, $d(v)$ will be at least one smaller, because $w$ has been removed, but in the case of a graph with many three-cycles, $d(v)$ may be much smaller. So, after at most a few applications of \autoref{eq:basic-structure} we may use the more efficient \autoref{eq:with-two-neighbours} again. +But this latter recurrence is clearly more efficient for \emph{large} $d(v)$. Therefore, if $d(v)$ is too large to use $v$ in \autoref{eq:with-two-neighbours}, we find one of its neighbours, say $w\in N(v)$, with the largest $d(w)$, and apply \autoref{eq:basic-structure} to that vertex. In the next recurrence, $d(v)$ will be at least one smaller, because $w$ has been removed, but in the case of a graph with many three-cycles, $d(v)$ may be much smaller. So, after at most a few applications of \autoref{eq:basic-structure} we may use the more efficient \autoref{eq:with-two-neighbours} again. \subsubsection{Dominance} \label{sec:algorithm:good-v:dominance} -\begin{thmproof}[dominance]{lemma}{If in graph $G$ with vertices $v,w$ we have $v>w$, we know that $\ms(G)=\ms(G\ex w)$.} +\begin{thmproof}[dominance]{lemma}{If for a graph $G=(V,E)$ with vertices $v,w\in V$ we know $v>w$, we have $\ms(G)=\ms(G\ex w)$.} If there is an m.i.s. $ms$ with $w\in ms$, $ms\ex w\with v$ is an m.i.s. as well. \end{thmproof} @@ -54,13 +58,13 @@ This gives us \autoref{alg:with-best-vertex}, which combines \autoref{eq:basic-s \label{alg:with-best-vertex} \begin{algorithmic}[1] \REQUIRE $G=(V,E)$ - \IF{$|G|=1$} + \IF{$|G|\le1$} \RETURN $|G|$ \COMMENT{\autoref{lem:base-case}} \ELSE \STATE $v\gets v\in V$ with minimal $d(v)$ \IF{$d(v)$ is small enough} \RETURN $\max(1+\ms(G\ex\iN(v)), \ms^2(G\ex v,N(v)))$ \COMMENT{\autoref{eq:with-two-neighbours}} - \ELSIF{$v$ dominates $w$} + \ELSIF{$v>w$} \RETURN $\ms(G\ex w)$ \COMMENT{\autoref{lem:dominance}} \ELSE \STATE $w\gets w\in N(v)$ with maximal $d(w)$ @@ -82,24 +86,24 @@ This gives us \autoref{alg:with-best-vertex}, which combines \autoref{eq:basic-s If there were a larger m.i.s. in the graph, there has to be a $v$ in a strongly connected component $C$ in that m.i.s. which is not in the m.i.s. of $C$. If we can add $v$ to the m.i.s. of $C$, that m.i.s. wasn't maximal. If we cannot, then the larger m.i.s. of the whole graph cannot be an independent set. \end{thmproof} -Based on \autoref{lem:components} we may write \refeq[with-components]{\ms(G)=\sum_{c\in C} \ms(c),} where $C$ is the set of strongly connected components of $G$. It is not difficult to see that in case a graph has multiple strongly connected components, this recurrence is more efficient than \autoref{alg:with-best-vertex}. +It is not difficult to see that in case a graph has multiple strongly connected components, this recurrence is more efficient than \autoref{alg:with-best-vertex}. \subsection{Further optimisations} \label{sec:algorithm:further-optimisations} -Although I have referred to Robson \cite{robson} and used his notation throughout this report, this is how far I got without his help. Robson then introduces a number of further optimisations. In this section, we use $G$ for the graph at hand and $v,w$ for the vertex with the lowest degree, and its neighbour with the highest degree, respectively. +Although I have referred to Robson \cite{robson} and used his notation already, this is how far I got without his help. Robson then introduces a number of further optimisations. In this section, we use $G$ for the graph at hand and $v,w$ for the vertex with the lowest degree, and its neighbour with the highest degree, respectively. -\begin{thmproof}[robson-ms-d1]{lemma}{If $d(v)=1$, we know $\ms(G)=1+\ms(G\ex\iN(v))$.} +\begin{thmproof}[robson-ms-d1]{lemma}{If $d(v)=1$, we have $\ms(G)=1+\ms(G\ex\iN(v))$.} By contradiction. By \autoref{lem:one-neighbour} we know that if $v$ is not in any m.i.s., then $w$ is in an m.i.s., say $ms$. But then $ms\ex w\with v$ is also independent, and has the same size. \end{thmproof} For the case that $d(v)=2$ we write $w,w'$ for the neighbours of $v$. -\begin{thmproof}[robson-ms-d2-edge]{lemma}{If $d(v)=2$ and $e(w,w')$, we know $\ms(G)=1+\ms(G\ex\iN(v))$.} +\begin{thmproof}[robson-ms-d2-edge]{lemma}{If $d(v)=2$ and $e(w,w')$, we have $\ms(G)=1+\ms(G\ex\iN(v))$.} By \autoref{lem:two-neighbours} we know that an m.i.s. will either contain $v$ or both $w$ and $w'$. But since $e(w,w')$, the latter cannot happen. Therefore, it must contain $v$ and neither of its neighbours. \end{thmproof} \begin{thmproof}[robson-ms-d2-noedge]{lemma}{If $d(v)=2$ and $\lnot e(w,w')$, we know $$\ms(G) = \max(2+\ms(G\ex\iN(w)\ex\iN(w')), 1 + \ms^2(G\ex\iN(v), N^2(v))).$$} - By \autoref{lem:two-neighbours}, an m.i.s. contains either $v$ or both $w,w'$. In the second case, we remove $w$ and $w'$ and their neighbourhoods from the graph (the left-hand side of $\max$). In the first case, the m.i.s. cannot contain $w$ or $w'$ but must contain two of their neighbours other than $v$. If not, and there is an m.i.s. $ms$ with at most one such neighbour, $u$, then $ms\ex v\ex u\with w\with w'$ is also independent, and has the same size. This gives the right-hand side. + By \autoref{lem:two-neighbours}, an m.i.s. contains either $v$ or both $w$ and $w'$. In the second case, we remove $w$ and $w'$ and their neighbourhoods from the graph (the left-hand side of $\max$). In the first case, the m.i.s. cannot contain $w$ or $w'$ but must contain two of their neighbours other than $v$. If not, and there is an m.i.s. $ms$ with at most one such neighbour, $u$, then $ms\ex v\ex u\with w\with w'$ is also independent, and has the same size. This gives the right-hand side. \end{thmproof} \autoref{alg:with-best-vertex} combined with \autoref{lem:components}, \ref{lem:robson-ms-d1}, \ref{lem:robson-ms-d2-edge} and \ref{lem:robson-ms-d2-noedge} gives us \autoref{alg:with-robsons-optimisations}. @@ -120,7 +124,7 @@ For the case that $d(v)=2$ we write $w,w'$ for the neighbours of $v$. \IF{$d(v)=1$} \RETURN $1+\ms(G\ex\iN(v))$ \COMMENT{\autoref{lem:robson-ms-d1}}\label{alg:ms:case-d1} \ELSIF{$d(v)=2$} - \STATE $w'\gets$ the other neighbour of $v$ + \STATE $\{w'\}\gets N(v)\ex w$ \IF{$e(w,w')$} \RETURN $1+\ms(G\ex\iN(v))$ \COMMENT{\autoref{lem:robson-ms-d2-edge}}\label{alg:ms:case-d2-edge} \ELSE @@ -142,11 +146,11 @@ For the case that $d(v)=2$ we write $w,w'$ for the neighbours of $v$. \end{thmproof} \begin{thmproof}[ms-efficiency]{theorem}{\autoref{alg:ms} is more efficient than \autoref{alg:with-best-vertex}, assuming that conditions are evaluated efficiently.} - The algorithm follows the same basic structure. In any case that \autoref{alg:ms} is different, it considers less cases (yet it is still correct by \autoref{thm:ms-correct}). Therefore, it can only be more efficient. + The algorithm follows the same basic structure. In any case that \autoref{alg:ms} is different, it considers less cases or smaller graphs (yet it is still correct by \autoref{thm:ms-correct}). Therefore, it can only be more efficient. \end{thmproof} \begin{thmproof}[ms-terminates]{theorem}{\autoref{alg:ms} terminates with every input, if $\ms^2$ terminates with a smaller input.} - There is a base case on line \ref{alg:ms:case-g1} which is not recursive and handles the graphs with the lowest $k$ possible orders ($k=2$). In every other case, the same algorithm is run on a smaller input (or $\ms^2$ on a smaller input), so inductively the algorithm terminates with any input. + There is a base case on line \ref{alg:ms:case-g1} which is not recursive that handles the graphs with the lowest $k$ possible orders ($k=2$). In every other case, the same algorithm or $\ms^2$ is run on a smaller input, so inductively the algorithm terminates with any input. \end{thmproof} \subsection{The helper function $\ms^n$} @@ -161,15 +165,15 @@ We will write $s_1,s_2,\dots$ for the elements of $S$. \autoref{lem:helper-general} may be used as a default case, when no clever optimisation can be found. -\begin{thmproof}[helper-1]{lemma}{If $|S|4$ is in line \ref{alg:ms:case-d2-noedge}. In \autoref{tab:analysis-ms} below we see that this particular case $3$ vertices were already removed from the graph. We will use this below in the analysis of \autoref{alg:ms}, line \ref{alg:ms:case-d2-noedge} in \autoref{tab:analysis-ms}. \begin{thmproof}[ms2-le-ms]{lemma}{There exists a $c$ for which for all graphs $G$ and subgraphs $S$ with $|S|\le4$, we have $T_{\ms^2}(|G|,|S|)\le T_{\ms}(n-2)$.} - Every case in \autoref{tab:analysis-ms2} suffices. Cases with complexity $T_{\ms^1}(n-x)$ suffice by \autoref{lem:ms1-le-ms}. + This holds for every case in \autoref{tab:analysis-ms2} with $c=3$. Cases with complexity $T_{\ms^1}(n-x)$ suffice by \autoref{lem:ms1-le-ms}. \end{thmproof} \subsection{$\ms$: \autoref{alg:ms}} @@ -161,20 +161,20 @@ Also this is a simple case distinction. Let's again put the different cases in a We saw already in \autoref{sec:algorithm:good-v:dominance} that after removing $w$ in the case of dominance of $v$ over $w$ on line \ref{alg:ms:case-dominance}, we will have a vertex with degree $3$. Therefore, the recurrence $T_{\ms}(n-1)$ in this case reduces to one of the above cases with $n:=n-1$. This is at most $T_{\ms}(n-3)+T_{\ms}(n-5)$. -We can do something similar in the `Otherwise' case. We can only be in this case if there is no vertex with degree less than $4$. Since all vertices have a maximum degree of $4$, this means that every vertex has degree $4$. In both subcases that are considered in line \ref{alg:ms:case-otherwise} of \autoref{alg:ms}, vertices are removed from the graph, leaving a graph with a vertex of maximum degree $3$. If we use that knowledge, we see from the other cases in \ref{tab:analysis-ms} that the time complexity of the `Otherwise' case can be rewritten as $T_{\ms}(n-3)+T_{\ms}(n-5)+T_{\ms}(n-7)+T_{\ms}(n-9)$. +We can do something similar in the `Otherwise' case of line \ref{alg:ms:case-otherwise}. We can only be in this case if there is no vertex with degree less than $4$. Since all vertices have a maximum degree of $4$, this means that every vertex has degree $4$. In both subcases that are considered in line \ref{alg:ms:case-otherwise} of \autoref{alg:ms}, vertices are removed from the graph, leaving a graph with a vertex of maximum degree $3$. If we use that knowledge, we see from the other cases in \ref{tab:analysis-ms} that the time complexity of the `Otherwise' case can be rewritten as $T_{\ms}(n-3)+T_{\ms}(n-5)+T_{\ms}(n-7)+T_{\ms}(n-9)$. -\begin{thmproof}[otherwise-half-of-cases]{lemma}{Of any $k$ consequent applications of $\ms$, at most $\frac k2$ will be using the inefficient `Otherwise' case.} +\begin{thmproof}[otherwise-half-of-cases]{lemma}{Of any $k$ successive applications of $\ms$, at most $\lceil\frac k2\rceil$ will be using the inefficient `Otherwise' case.} After applying the `Otherwise' case, there will be at least one vertex with degree lower than $4$. In the iteration directly after applying the `Otherwise' case, we don't need to apply it. \end{thmproof} \begin{thmproof}[ms-complexity]{theorem}{\autoref{alg:ms} runs in $\pazocal O\left(2^{n/2}\right)$.} - We see that the time complexity of $\ms(n)$ depends on $\ms(n-c)$ with $c\ge2$. Furthermore, if $c=2$, we have $\ms(n)=\ms(n-2)$, so if $\ms(n)$ depends on $\ms(n-2)$, it depends on that \emph{alone}, giving a branching factor of $1$. Branching only occurs when $c\ge3$. Only in the `Otherwise' case, the branching factor is $4$, in the other cases it is $2$. + We see that the time complexity of $\ms(n)$ depends on $\ms(n-c)$ with $c\ge2$. Furthermore, if $c=2$, we have $\ms(n)=\ms(n-2)$, so if $\ms(n)$ depends on $\ms(n-2)$, it depends on that \emph{alone}, giving a branching factor of $1$ in the search tree. Branching only occurs when $c\ge3$. Only in the `Otherwise' case, the branching factor is $4$, in the other cases it is $2$. - We then consider the search tree $T$ where we compress nodes with branching factor $1$. By \autoref{lem:otherwise-half-of-cases}, only on one of two consecutive levels can we have a branching factor of $4$ (and in the worst case this will happen as much as possible). If we then combine the levels with branching factor $4$ with the levels directly below them (having branching factor $2$), we find a search tree $T'$ with in the worst case a constant branching factor of $8$. + We then consider the search tree $T$ where we compress directly related nodes with branching factor $1$ into one node. By \autoref{lem:otherwise-half-of-cases}, only on one of two consecutive levels can we have a branching factor of $4$ (and in the worst case this will happen as much as possible). If we then combine the levels with branching factor $4$ with the levels directly below them (having branching factor $2$), we find a search tree $T'$ with in the worst case a constant branching factor of $8$. - The original search tree $T$ has at most $\frac n3$ levels, since branching only occurs when $c\ge3$. Therefore, the compressed tree $T'$ has, in the worst case, $\frac n6$ levels (note, that this case is worse than the case of a tree with constant branching factor $2$ and $\frac n3$ levels, and therefore also worse than any case in between). + The original search tree $T$ has at most $\frac n3$ levels, since branching only occurs when $c\ge3$. Therefore, the compressed tree $T'$ has, in the worst case, $\frac n6$ levels (note, that this case is worse than the case of a tree with constant branching factor $2$ and $\frac n3$ levels, and also worse than any case in between). - In every vertex of the search tree $T'$ we need polynomial time, since we assumed that basic graph operations run in polynomial time. Therefore, \autoref{alg:ms} runs in $$\pazocal O\left(\left(8\cdot\mathrm{polynomial}(n)\right)^{n/6}\right) = \pazocal O\left(\mathrm{polynomial}(n)^{n/2}\right) = \pazocal O\left(2^{n/2}\right).$$ + In every vertex of the search tree $T'$ we need polynomial time, since we assumed that basic graph operations run in polynomial time. Therefore, \autoref{alg:ms} runs in $$\pazocal O\left(\left(8\cdot\mathrm{polynomial}(n)\right)^{n/6}\right) = \pazocal O\left(\left(2\cdot\mathrm{polynomial}(n)\right)^{n/2}\right) = \pazocal O\left(2^{n/2}\right).$$ \end{thmproof} This result is, naturally, coherent with Robson's result that the algorithm runs in $\pazocal O\left(\mathrm{polynomial}(n)\cdot2^{cn}\right)$ with $c<0.296$ \cite{robson}. We have proven that the bound holds with $c\le\frac12$. diff --git a/Practical1/report/discussion.tex b/Practical1/report/discussion.tex new file mode 100644 index 0000000..e91c5d3 --- /dev/null +++ b/Practical1/report/discussion.tex @@ -0,0 +1,10 @@ +\section{Discussion} +\label{sec:discussion} +Using Robson's paper \cite{robson} perhaps wasn't the intention of this assignment. However, it shouldn't be considered cheating either. In this report I have on several points indicated what I found out myself, and where I needed Robson's help. The optimisations Robson adds to the basic structure are all argued in this report, so the correctness theorems are still totally proven in this paper. + +Furthermore, I didn't actively look for a ready-made solution to the problem. I abstracted the problem to a `colouring maximising problem', then searched and asked around if things were written about it. I didn't expect to find a paper that discussed the problem in such detail. + +After finding a paper that does have such an optimised solution, it would only be silly (and result in a slower algorithm) to \emph{not} use it. + +Therefore, I do not think using Robson's paper should be considered cheating in any way. + diff --git a/Practical1/report/implementation.tex b/Practical1/report/implementation.tex index 8a667f1..f43b6f1 100644 --- a/Practical1/report/implementation.tex +++ b/Practical1/report/implementation.tex @@ -18,24 +18,20 @@ A Java application accompanies this report. I have chosen for a simple implement public boolean dominates(Node b); public boolean neighbourhoodsDisjoint(Node b); public List> neighbourhoodIntersection(Node b); - - public String toString(); - public boolean equals(Object b); - public int compareTo(Node b); } \end{minted} -The \texttt{Node} class implements \texttt{Comparable>} to be able to sort on degree. +Some standard methods have been left out. The \texttt{Node} class implements \texttt{Comparable} to be able to sort on degree. -We only consider vertices with degree between $0$ and $4$ in this problem. Therefore, we may consider all these methods to run in constant time. Most of the methods run already in constant time. Some need to iterate over the list of neighbours (and possibly their neighbours), but if the degrees of all vertices is between $0$ and $4$ we're talking about at most $16$ vertices, which we can consider constant. +We only consider vertices with degree less than $5$ in this problem. Therefore, we may consider all these methods to run in constant time. Most of the methods already run in constant time. Some need to iterate over the list of neighbours (and possibly their neighbours), but if the degrees of all vertices is between $0$ and $4$ we're talking about at most $16$ vertices, which we can consider constant. The data structure of a graph is even simpler. It is implemented as a list of nodes. But some of the functions that we used in the algorithms in \autoref{sec:algorithm} above, give us a problem. Whenever $\max()$ is used in the algorithms, we consider different possibilities, which need to be investigated separately. -At first, I wrote a program that created a new graph for every recurrence, and then ran the $\ms$, $\ms^2$ or $\ms^1$ algorithm on that new graph. This approach has the advantage that it allows for multi-threading. Letting the graph class implement \texttt{Runnable} we can run different cases in different threads, taking the $\max()$ of their results when they finish. However, it turned out that copying the list of a graph's nodes \emph{leaving the references to each other intact} caused a lot of overhead, making it in practice an unusable approach. +At first, I wrote a program that created a new graph for every recurrence, and then ran the $\ms$, $\ms^2$ or $\ms^1$ algorithm on that new graph. This approach has the advantage that it allows for multi-threading. We could run different cases in different threads, taking the $\max()$ of their results when they finish. However, it turned out that copying the list of a graph's nodes \emph{leaving the references to each other intact} caused a lot of overhead, making it in practice an unusable approach. -The other approach is to, when investigating a subgraph, make some modifications to the graph object itself, running $\ms$ or $\ms^n$ on the same object, and reverting the modifications before moving on to the next case. This is slightly more difficult to implement, but has the big advantage of not needing exponential space. Also, it turned out to be faster in practice, as said above. +The other approach is to, when in need of investigating a subgraph, make some modifications to the graph object itself, running $\ms$ or $\ms^n$ on the same object, and reverting the modifications before moving on to the next case. This is slightly more difficult to implement, but has the big advantage of not needing exponential space. Also, it turned out to be faster in practice. -The graph therefore has a stack of lists of nodes as a private member. Every element on the stack is a restore point. There is a method to create a new restore point, which pushes an empty list to the stack. Whenever nodes are removed from the graph, they are added to the element at the top of the stack. Lastly, there is a method that pops the first element of the stack, restores the nodes in that list, putting them back in the graph. +The graph therefore has a stack of lists of nodes as a private member. Every element on the stack is a restore point. There is a method to create a new restore point, which pushes an empty list to the stack. Whenever nodes are removed from the graph, they are added to the element at the top of the stack. Lastly, there is a method that pops the first element of the stack and restores the nodes in that list, putting them back in the graph. That gives us the signature of the \texttt{Graph} class: @@ -62,13 +58,12 @@ That gives us the signature of the \texttt{Graph} class: private void restore(); public int size(); - public String toString(); } \end{minted} Only the method \texttt{findStronglyConnectedComponent} creates a new \texttt{Graph} object. We are talking about graphs of up to $100$ vertices, so we will create at most $100$ \texttt{Graph} objects, which is acceptable. -The \texttt{removeNode}(\texttt{s}) methods don't only remove their argument(s) from the graph, they also remove the references to their arguments from any node that is still in the graph. But because this means removing at most $4$ references per node removed, this runs in linear time relative to the number of nodes to be removed. +The \texttt{removeNode}(\texttt{s}) methods don't only remove their argument(s) from the graph, they also remove the references to their arguments from any node that is still in the graph. Otherwise, we wouldn't be able to find the vertex with minimal degree. But because this means removing at most $4$ references per node removed, this still runs in linear time relative to the number of nodes to be removed. The \texttt{addNode} and \texttt{getNode} methods are simply wrappers for the \texttt{nodes} member, which run in constant time, as do \texttt{size}, \texttt{toString} and \texttt{restorePoint}. The \texttt{restore} method needs to add earlier removed nodes (say $n$) back to the graph, and add their references back to their neighbours. However, since every node has at most $4$ neighbours, this runs in linear time relative to the number of nodes to restore. diff --git a/Practical1/report/notation.tex b/Practical1/report/notation.tex index 07f9a34..6d01d9b 100644 --- a/Practical1/report/notation.tex +++ b/Practical1/report/notation.tex @@ -1,8 +1,8 @@ \section{Notation} \label{sec:notation} -I'm largely following Robson's notation \cite{robson}. For a graph $G=(V,E)$ and vertex $v\in V$, and edge $e\in E$, we write $d(v)$ for the degree of the vertex. $N(v)$ is the set of $v$'s neighbours, and $\iN(v)=N(v)\cup\{v\}$, $v$'s `inclusive neighbourhood'. Then $N^2(v)$ is the set of second order neighbours of $v$, excluding $v$: $N^2(v)=\{v_2 \in N(v_1) \mid v_1\in N(v)\} \setminus \{v\}$. If $\iN(v)\subseteq\iN(w)$, $v$ is said to dominate $w$, notation: $v>w$. +I'm largely following Robson's notation \cite{robson}. For a graph $G=(V,E)$ and vertex $v\in V$, we write $d(v)$ for the degree of the vertex. $N(v)$ is the set of $v$'s neighbours, and $\iN(v)=N(v)\cup\{v\}$, $v$'s `inclusive neighbourhood'. Then $N^2(v)$ is the set of second order neighbours of $v$, excluding $v$: $N^2(v)=\{v_2 \in N(v_1) \mid v_1\in N(v)\} \setminus \{v\}$. If $\iN(v)\subseteq\iN(w)$, $v$ is said to dominate $w$, notation: $v>w$. -We write `subgraph' for `vertex-induced subgraph', and $G\ex U$ for the subgraph induced on $G$ by $U$. For $v\in V$, we write $G\ex v$ for $G\ex\{v\}$. We use $e(v,w)$ for the predicate $(v,w)\in E$. We're strictly talking about non-directed graphs, so this is equivalent with $(w,v)\in E$. +We write `subgraph' for `vertex-induced subgraph', and $G\ex U$ for the subgraph induced on $V\ex U$ by $G$. For $v\in V$, we write $G\ex v$ for $G\ex\{v\}$. We use $e(v,w)$ for the predicate $(v,w)\in E$. We're strictly talking about non-directed graphs, so this is equivalent with $(w,v)\in E$. -Finally, We write `m.i.s.' for `maximum independent set' and $\ms(\cdots)$ for its size, the graph's independence number. The size of a graph or an m.i.s. is defined as the number of vertices and is written as $|G|$. +Finally, We write `m.i.s.' for `maximum independent set' and $\ms(G)$ for its size in $G$, the graph's independence number. The size of a graph or an m.i.s. is defined as the number of its vertices and is written as $|G|$. diff --git a/Practical1/report/report.tex b/Practical1/report/report.tex index 4b24662..0be5a9a 100644 --- a/Practical1/report/report.tex +++ b/Practical1/report/report.tex @@ -51,7 +51,7 @@ \usepackage{minted} \title{Miss Algorithm} -\author{Camil Staps\\\small{s4498062}} +\author{Camil Staps} \begin{document} @@ -61,13 +61,13 @@ \begin{abstract} No, this report is not about a new beauty pageant. It is about the realisation and implementation of a maximum independent set size (miss) algorithm. - Garbage collectors and the local government of Nijmegen have agreed to place garbage bins on the at most 100 intersections of the at most 200 streets of the city, with the restriction that no two neighbouring intersections may both have a garbage bin. In this report we will discuss an algorithm that can check whether $k$ garbage bins can be placed following that rule. + Garbage collectors and the local government of Nijmegen have agreed to place garbage bins on the at most 100 intersections of the at most 200 streets of the city, with the restriction that no two neighbouring intersections may both have a garbage bin. It is given that on one intersection at most four streets come together. In this report we will discuss an algorithm that can check whether $k$ bins can be placed following that rule. - This problem is of course a fancy formulation of the maximum independent set problem. So to answer the question, we implement an algorithm that computes the size of the maximum independent set, and verify if $k$ is small enough. + This problem is of course just a fancy formulation of the maximum independent set problem. So to answer the question, we implement an algorithm that computes the size of the maximum independent set, and verify if $k$ is small enough. \end{abstract} \section{Report organisation} -\autoref{sec:notation} will define the notation used throughout this report. In \autoref{sec:algorithm} I will describe the algorithm and argue its correctness. First we will discuss the basic structure in \autoref{sec:algorithm:basic-structure} through \ref{sec:algorithm:further-optimisations}. After that, we will discuss some helper functions in \autoref{sec:algorithm:helper-function}. +\autoref{sec:notation} will define the notation used throughout this report. In \autoref{sec:algorithm} I will describe the algorithm and argue its correctness. First, we will discuss the basic structure in \autoref{sec:algorithm:basic-structure} through \ref{sec:algorithm:further-optimisations}. After that, we will discuss some helper functions in \autoref{sec:algorithm:helper-function}. When we have seen the algorithm, \autoref{sec:implementation} will go into details about its implementation in Java. \autoref{sec:analysis} will contain a complexity analysis, both time- and space-wise, of the algorithm and its Java implementation. @@ -75,6 +75,7 @@ When we have seen the algorithm, \autoref{sec:implementation} will go into detai \input{algorithm} \input{implementation} \input{analysis} +\input{discussion} \section{Acknowledgements} \label{sec:acknowledgements} -- cgit v1.2.3