From 21c80bcf9c0541dff03783bc76ef75fe3b4f3d00 Mon Sep 17 00:00:00 2001
From: Camil Staps
Date: Thu, 22 Oct 2015 17:56:45 +0200
Subject: Robson's algorithm; added test outputs; more test cases; tester
 bugfix

---
 .../src/nl/camilstaps/cs/GarbageCollectionMap.java | 80 ----------------------
 1 file changed, 80 deletions(-)
 delete mode 100644 Practical1/src/nl/camilstaps/cs/GarbageCollectionMap.java

(limited to 'Practical1/src/nl/camilstaps/cs/GarbageCollectionMap.java')

diff --git a/Practical1/src/nl/camilstaps/cs/GarbageCollectionMap.java b/Practical1/src/nl/camilstaps/cs/GarbageCollectionMap.java
deleted file mode 100644
index e700cb0..0000000
--- a/Practical1/src/nl/camilstaps/cs/GarbageCollectionMap.java
+++ /dev/null
@@ -1,80 +0,0 @@
-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;
-    }
-
-}
-- 
cgit v1.2.3