Final version report practical 1

1 files changed, 6 insertions, 11 deletions

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<T> b);
 	    public boolean neighbourhoodsDisjoint(Node<T> b);
 	    public List<Node<T>> neighbourhoodIntersection(Node<T> b);
-	
-	    public String toString();
-	    public boolean equals(Object b);
-	    public int compareTo(Node<T> b);
 	}
 \end{minted}
 
-The \texttt{Node} class implements \texttt{Comparable<Node<T>>} 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.