Using a type variable for a Node's content

3 files changed, 49 insertions, 47 deletions

diff --git a/Practical1/src/nl/camilstaps/cs/GarbageCollectionHelper.java b/Practical1/src/nl/camilstaps/cs/GarbageCollectionHelper.java
index 0da2dc5..ec1506d 100644
--- a/Practical1/src/nl/camilstaps/cs/GarbageCollectionHelper.java
+++ b/Practical1/src/nl/camilstaps/cs/GarbageCollectionHelper.java
@@ -17,7 +17,7 @@ class GarbageCollectionHelper {
      * @param args Command line arguments (are ignored)
      */
     public static void main(String[] args) {
-        Graph graph = new Graph();
+        Graph graph = new Graph<Integer>();
         int n_bins = readGraph(new Scanner(System.in), graph);
         System.out.println(graph.maximumIndependentSetSize() >= n_bins ? "possible" : "impossible");
     }
@@ -35,13 +35,13 @@ class GarbageCollectionHelper {
      * @param graph the Graph to build
      * @return the number of bins
      */
-    private static int readGraph(Scanner sc, Graph graph) {
+    private static int readGraph(Scanner sc, Graph<Integer> graph) {
         int n_edges = sc.nextInt();
         int n_nodes = sc.nextInt();
         int n_bins  = sc.nextInt();
 
         for (int i = 1; i <= n_nodes; i++) {
-            graph.addNode(new Node(i));
+            graph.addNode(new Node<>(i));
         }
 
         for (int i = 0; i < n_edges; i++) {
diff --git a/Practical1/src/nl/camilstaps/cs/graphs/Graph.java b/Practical1/src/nl/camilstaps/cs/graphs/Graph.java
index f1bf946..72cd87e 100644
--- a/Practical1/src/nl/camilstaps/cs/graphs/Graph.java
+++ b/Practical1/src/nl/camilstaps/cs/graphs/Graph.java
@@ -8,17 +8,17 @@ import java.util.stream.Collectors;
  *
  * @author Camil Staps
  */
-public class Graph {
-    private final List<Node> nodes;
+public class Graph<T> {
+    private final List<Node<T>> nodes;
     // When removing nodes, it's possible to create restore points to add them back later on.
-    private final Stack<List<Node>> restorePoints = new Stack<>();
+    private final Stack<List<Node<T>>> restorePoints = new Stack<>();
 
     public Graph() {
         this.nodes = new ArrayList<>();
         restorePoint();
     }
 
-    public Graph(List<Node> nodes) {
+    public Graph(List<Node<T>> nodes) {
         this.nodes = nodes;
         restorePoint();
     }
@@ -38,13 +38,13 @@ public class Graph {
         int miss;
         restorePoint();
 
-        Graph stronglyConnectedComponent = findStronglyConnectedComponent();
+        Graph<T> stronglyConnectedComponent = findStronglyConnectedComponent();
         if (stronglyConnectedComponent.size() == size()) {
             // Case: connected graph. Pick a nice Node A (low degree) and a neighbour B with high degree.
             Collections.sort(nodes);
-            Node A = nodes.get(0);
+            Node<T> A = nodes.get(0);
             Collections.sort(A.getNeighbourhood(), Collections.reverseOrder());
-            Node B = A.getNeighbourhood().get(0);
+            Node<T> B = A.getNeighbourhood().get(0);
 
             int try_1, try_2;
             switch (A.getDegree()) {
@@ -56,7 +56,7 @@ public class Graph {
                 case 2:
                     // Two neighbours: if they are connected pick A and continue with the rest of the Graph. If not,
                     // try both picking the neighbours and picking A with two of its second order neighbours.
-                    Node B_ = A.getNeighbourhood().get(1);
+                    Node<T> B_ = A.getNeighbourhood().get(1);
                     if (B.getNeighbourhood().contains(B_)) {
                         removeNodes(A.getInclusiveNeighbourhood());
                         miss = 1 + maximumIndependentSetSize();
@@ -115,7 +115,7 @@ public class Graph {
      * @param s_2 The second node
      * @return the maximum independent set size
      */
-    private int maximumIndependentSetSizeWith1From(Node s_1, Node s_2) {
+    private int maximumIndependentSetSizeWith1From(Node<T> s_1, Node<T> s_2) {
         assert s_1.getDegree() <= s_2.getDegree();
 
         int miss;
@@ -140,7 +140,7 @@ public class Graph {
             removeNodes(s_1.neighbourhoodIntersection(s_2));
             miss = maximumIndependentSetSizeWith1From(s_1, s_2);
         } else if (s_2.getDegree() == 2) {
-            Node E = s_1.getNeighbourhood().get(0), F = s_1.getNeighbourhood().get(1);
+            Node<T> E = s_1.getNeighbourhood().get(0), F = s_1.getNeighbourhood().get(1);
             if (E.getNeighbourhood().contains(F)) {
                 removeNodes(s_1.getInclusiveNeighbourhood());
                 miss = 1 + maximumIndependentSetSize();
@@ -193,8 +193,8 @@ public class Graph {
      * @param Scol the set of which two Nodes should be in the maximum independent set
      * @return the size of the maximum independent set
      */
-    private int maximumIndependentSetSizeWith2From(Collection<Node> Scol) {
-        List<Node> S = new ArrayList<>(Scol);
+    private int maximumIndependentSetSizeWith2From(Collection<Node<T>> Scol) {
+        List<Node<T>> S = new ArrayList<>(Scol);
         int miss;
         restorePoint();
 
@@ -212,7 +212,7 @@ public class Graph {
             }
         } else if (S.size() == 3) {
             // Three Nodes to pick from. An ugly case distinction.
-            Node s_1 = S.get(0), s_2 = S.get(1), s_3 = S.get(2);
+            Node<T> s_1 = S.get(0), s_2 = S.get(1), s_3 = S.get(2);
 
             // If there is a Node with degree 0, we add it to the independent set and choose 1 Node from the other two
             if (s_1.getDegree() == 0) {
@@ -233,7 +233,7 @@ public class Graph {
             }
             // If there is at least one edge from s_1
             else if (s_1.getNeighbourhood().contains(s_2) || s_1.getNeighbourhood().contains(s_3)){
-                Node s_i, s_j, s_k;
+                Node<T> s_i, s_j, s_k;
                 s_i = s_j = s_k = null;
 
                 // If there are two edges among S, say si-sj-sk, we pick si and sk.
@@ -303,7 +303,7 @@ public class Graph {
             if (nodes.get(0).getDegree() <= 3) {
                 miss = maximumIndependentSetSize();
             } else {
-                Node s_1 = S.get(0);
+                Node<T> s_1 = S.get(0);
                 int try_1, try_2;
                 removeNode(s_1);
                 S.remove(s_1);
@@ -327,27 +327,27 @@ public class Graph {
      *
      * @return some strongly connected component
      */
-    private Graph findStronglyConnectedComponent() {
+    private Graph<T> findStronglyConnectedComponent() {
         if (nodes.isEmpty())
             return this;
 
-        List<Node> seen = new ArrayList<>();
-        Queue<Node> queue = new LinkedList<>();
+        List<Node<T>> seen = new ArrayList<>();
+        Queue<Node<T>> queue = new LinkedList<>();
         queue.add(nodes.get(0));
         while (!queue.isEmpty()) {
-            Node n = queue.remove();
+            Node<T> n = queue.remove();
             queue.addAll(n.getNeighbourhood().stream().filter(x -> !seen.contains(x)).collect(Collectors.toList()));
             seen.add(n);
         }
 
-        return new Graph(seen);
+        return new Graph<>(seen);
     }
 
     /**
      * Add a Node, and update its neighbours to include it as a neighbour.
      * @param node the Node to add
      */
-    public void addNode(Node node) {
+    public void addNode(Node<T> node) {
         this.nodes.add(node);
         node.getNeighbourhood().stream()
                 .filter(nodes::contains)
@@ -362,7 +362,7 @@ public class Graph {
      * @param i the index in the list
      * @return the Node
      */
-    public Node getNode(int i) {
+    public Node<T> getNode(int i) {
         return this.nodes.get(i);
     }
 
@@ -373,7 +373,7 @@ public class Graph {
      *
      * @param node the Node
      */
-    private void removeNode(Node node) {
+    private void removeNode(Node<T> node) {
         nodes.remove(node);
         node.getNeighbourhood().stream()
                 .filter(nodes::contains)
@@ -388,9 +388,9 @@ public class Graph {
      *
      * @param ns the Nodes to remove
      */
-    private void removeNodes(Collection<Node> ns) {
+    private void removeNodes(Collection<Node<T>> ns) {
         nodes.removeAll(ns);
-        for (Node n : nodes)
+        for (Node<T> n : nodes)
             n.getNeighbourhood().removeAll(ns);
         restorePoints.peek().addAll(ns);
     }
@@ -412,9 +412,9 @@ public class Graph {
      * @see #restorePoints
      */
     private void restore() {
-        List<Node> removed = restorePoints.pop();
+        List<Node<T>> removed = restorePoints.pop();
         Collections.reverse(removed);
-        for (Node node : removed) {
+        for (Node<T> node : removed) {
             this.nodes.add(node);
             node.getNeighbourhood().stream()
                     .filter(nodes::contains)
@@ -440,7 +440,7 @@ public class Graph {
         StringBuilder sb = new StringBuilder("Graph:");
         for (Node n : nodes) {
             sb.append("\n  ").append(n).append(":   ");
-            for (Node n2 : n.getNeighbourhood()) sb.append(" - ").append(n2);
+            for (Object n2 : n.getNeighbourhood()) sb.append(" - ").append(n2);
         }
         return sb.toString();
     }
diff --git a/Practical1/src/nl/camilstaps/cs/graphs/Node.java b/Practical1/src/nl/camilstaps/cs/graphs/Node.java
index b9d078e..ccdbd4a 100644
--- a/Practical1/src/nl/camilstaps/cs/graphs/Node.java
+++ b/Practical1/src/nl/camilstaps/cs/graphs/Node.java
@@ -10,11 +10,11 @@ import java.util.stream.Collectors;
  *
  * @author Camil Staps
  */
-public class Node implements Comparable<Node> {
-    private final int content;
-    private final List<Node> neighbours = new ArrayList<>();
+public class Node<T> implements Comparable<Node<T>> {
+    private final T content;
+    private final List<Node<T>> neighbours = new ArrayList<>();
 
-    public Node(int content) {
+    public Node(T content) {
         this.content = content;
     }
 
@@ -28,15 +28,15 @@ public class Node implements Comparable<Node> {
     /**
      * @return the neighbours
      */
-    public List<Node> getNeighbourhood() {
+    public List<Node<T>> getNeighbourhood() {
         return neighbours;
     }
 
     /**
      * @return the neighbours with the Node itself
      */
-    public List<Node> getInclusiveNeighbourhood() {
-        List<Node> nb = new ArrayList<>();
+    public List<Node<T>> getInclusiveNeighbourhood() {
+        List<Node<T>> nb = new ArrayList<>();
         nb.add(this);
         nb.addAll(neighbours);
         return nb;
@@ -45,10 +45,12 @@ public class Node implements Comparable<Node> {
     /**
      * @return the neighbours of the neighbours, without this Node itself
      */
-    public List<Node> getSecondNeighbourhood() {
-        List<Node> nb = new ArrayList<>();
-        for (Node n : getNeighbourhood())
-            n.getNeighbourhood().stream().filter(n2 -> !nb.contains(n2)).forEach(nb::add);
+    public List<Node<T>> getSecondNeighbourhood() {
+        List<Node<T>> nb = new ArrayList<>();
+        for (Node<T> n : getNeighbourhood())
+            for (Node<T> n2 : n.getNeighbourhood())
+                if (!nb.contains(n2))
+                    nb.add(n2);
         nb.remove(this);
         return nb;
     }
@@ -58,8 +60,8 @@ public class Node implements Comparable<Node> {
      * @param b the Node to compare to
      * @return true iff this Node dominates Node b
      */
-    public boolean dominates(Node b) {
-        for (Node nb : getInclusiveNeighbourhood())
+    public boolean dominates(Node<T> b) {
+        for (Node<T> nb : getInclusiveNeighbourhood())
             if (!b.getInclusiveNeighbourhood().contains(nb))
                 return false;
         return true;
@@ -69,7 +71,7 @@ public class Node implements Comparable<Node> {
      * @param b the Node to compare to
      * @return true iff the neighbourhood of this Node is disjoint with the neighbourhood of Node b
      */
-    public boolean neighbourhoodsDisjoint(Node b) {
+    public boolean neighbourhoodsDisjoint(Node<T> b) {
         return neighbourhoodIntersection(b).isEmpty();
     }
 
@@ -77,7 +79,7 @@ public class Node implements Comparable<Node> {
      * @param b another Node
      * @return the intersection of the neighbourhood of this Node and the neighbourhood of Node b
      */
-    public List<Node> neighbourhoodIntersection(Node b) {
+    public List<Node<T>> neighbourhoodIntersection(Node<T> b) {
         return neighbours.stream().filter(n -> b.getNeighbourhood().contains(n)).collect(Collectors.toList());
     }
 
@@ -105,7 +107,7 @@ public class Node implements Comparable<Node> {
      */
     @Override
     @SuppressWarnings("NullableProblems")
-    public int compareTo(Node b) {
+    public int compareTo(Node<T> b) {
         return Integer.compare(neighbours.size(), b.neighbours.size());
     }
 }