\section{Implementation}
\label{sec:implementation}

A Java application accompanies this report. I have chosen for a simple implementation of a vertex:

\begin{minted}[fontsize=\footnotesize,linenos,tabsize=0]{java}
	class Node<T> implements Comparable<Node<T>> {
	    private final T content;
	    private final List<Node<T>> neighbours = new ArrayList<>();
	
	    public Node(T content);
	
	    public int getDegree();
	    public List<Node<T>> getNeigbourhood();
	    public List<Node<T>> getInclusiveNeighbourhood();
	    public List<Node<T>> getSecondNeighbourhood();
	
	    public boolean dominates(Node<T> b);
	    public boolean neighbourhoodsDisjoint(Node<T> b);
	    public List<Node<T>> neighbourhoodIntersection(Node<T> b);
	}
\end{minted}

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 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. 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 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 and restores the nodes in that list, putting them back in the graph.

That gives us the signature of the \texttt{Graph} class:

\begin{minted}[fontsize=\footnotesize,linenos,tabsize=0]{java}
	class Graph<T> {
	    private final List<Node<T>> nodes;
	    private final Stack<List<Node<T>>> restorePoints = new Stack<>();
	    
	    public Graph();
	    public Graph(List<Node<T>> nodes);
	
	    public int maximumIndependentSetSize();
	    private int maximumIndependentSetSizeWith1From(Node<T> s_1, Node<T> s_2);
	    private int maximumIndependentSetSizeWith2From(Collection<Node<T>> Scol);
	
	    private Graph<T> findStronglyConnectedComponent();
	    
	    public void addNode(Node<T> node);
	    public Node<T> getNode(int i);
	    private void removeNode(Node<T> node);
	    private void removeNodes(Collection<Node<T>> ns);
	
	    private void restorePoint();
	    private void restore();
	
	    public int size();
	}
\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. 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.

Using these two classes in the problem at hand turns out to be as simple as:

\begin{minted}[fontsize=\footnotesize,linenos,tabsize=0]{java}
	Graph graph = new Graph<Integer>();
	int n_bins = readGraph(new Scanner(System.in), graph);
	int miss = graph.maximumIndependentSetSize();
	System.out.println(miss >= n_bins ? "possible" : "impossible");
\end{minted}

A suitable implementation of \texttt{readGraph} is outside the scope of this report.