First version practical 1 (garbage collection)

1 files changed, 80 insertions, 0 deletions

diff --git a/Practical1/src/nl/camilstaps/cs/GarbageCollectionMap.java b/Practical1/src/nl/camilstaps/cs/GarbageCollectionMap.java
new file mode 100644
index 0000000..e700cb0
--- /dev/null
+++ b/Practical1/src/nl/camilstaps/cs/GarbageCollectionMap.java
@@ -0,0 +1,80 @@
+package nl.camilstaps.cs;
+
+import nl.camilstaps.cs.graphs.Graph;
+import nl.camilstaps.cs.graphs.Node;
+
+import java.util.*;
+import java.util.stream.Collectors;
+
+/**
+ * The garbage collection map is simply a Graph with extended functionality.
+ *
+ * @author Camil Staps
+ */
+class GarbageCollectionMap extends Graph {
+
+    public GarbageCollectionMap() {
+        super();
+    }
+
+    private GarbageCollectionMap(Graph g) {
+        super(g);
+    }
+
+    /**
+     * We want to choose a node with few neighbours, to minimise the branching factor at each reduction step.
+     * @return the node with the fewest neighbours
+     */
+    protected Node bestNode() {
+        Node best = null;
+        for (Node n : nodes)
+            if (best == null || best.getNeighbours().size() > n.getNeighbours().size())
+                best = n;
+        return best;
+    }
+
+    /**
+     * Check if we can place N bins in this map.
+     *
+     *  - Choose the {@link #bestNode} and try if we can place N-1 bins if we remove this node and all its neighbours
+     *  - If not, remove the node and try for all its neighbours the same thing.
+     *  - If it doesn't work for the best node or for one of its neighbours, it is impossible to place N bins.
+     *
+     * @param bins the number of bins we want to place
+     * @return whether this is possible
+     */
+    protected boolean canPlaceNBins(int bins) {
+        if (this.nodes.size() < bins)
+            return false;
+        if (bins < 1)
+            return true;
+
+        // A queue with the nodes we want to check
+        Queue<Node> q = new LinkedList<>();
+        boolean first_go = true;
+
+        q.add(bestNode());
+        while (!q.isEmpty()) {
+            Node n = q.remove();
+            removeNode(n);
+
+            // Recursively check the subgraph without the node we're checking and its children
+            GarbageCollectionMap gcm = new GarbageCollectionMap(this);
+            gcm.removeNodes(n.getNeighbours());
+            if (gcm.canPlaceNBins(bins - 1))
+                return true;
+
+            // Check children
+            if (first_go)
+                q.addAll(n.getNeighbours().stream().filter(nodes::contains).collect(Collectors.toList()));
+
+            // Restore graph
+            addNode(n);
+            nodes.remove(n);
+            first_go = false;
+        }
+
+        return false;
+    }
+
+}