Robson's algorithm; added test outputs; more test cases; tester bugfix

2 files changed, 333 insertions, 22 deletions

diff --git a/Practical1/src/nl/camilstaps/cs/graphs/Graph.java b/Practical1/src/nl/camilstaps/cs/graphs/Graph.java
index ef89258..0da1924 100644
--- a/Practical1/src/nl/camilstaps/cs/graphs/Graph.java
+++ b/Practical1/src/nl/camilstaps/cs/graphs/Graph.java
@@ -9,19 +9,261 @@ import java.util.stream.Collectors;
  * @author Camil Staps
  */
 public class Graph {
-    protected final List<Node> nodes;
+    private final List<Node> nodes;
+    private final Stack<List<Node>> removedStack = new Stack<>();
 
     public Graph() {
         this.nodes = new ArrayList<>();
+        restorePoint();
     }
 
-    /**
-     * Create a copy of another Graph, also copying all the Nodes
-     * @param g
-     */
-    public Graph(Graph g) {
-        this();
-        this.nodes.addAll(g.nodes.stream().map(Node::new).collect(Collectors.toList()));
+    public Graph(List<Node> nodes) {
+        this.nodes = nodes;
+        restorePoint();
+    }
+
+    public int maximumIndependentSetSize() {
+        if (nodes.size() <= 1)
+            return nodes.size();
+
+        int mis = 0;
+        restorePoint();
+
+        Graph partition = findPartition();
+        if (partition.size() == size()) {
+            Collections.sort(nodes);
+            Node A = nodes.get(0);
+            Collections.sort(A.getNeighbourhood(), Collections.reverseOrder());
+            Node B = A.getNeighbourhood().get(0);
+
+            int try_1, try_2;
+            switch (A.getDegree()) {
+                case 1:
+                    removeNodes(A.getInclusiveNeighbourhood());
+                    mis = 1 + maximumIndependentSetSize();
+                    break;
+                case 2:
+                    Node B_ = A.getNeighbourhood().get(1);
+                    if (B.getNeighbourhood().contains(B_)) {
+                        removeNodes(A.getInclusiveNeighbourhood());
+                        mis = 1 + maximumIndependentSetSize();
+                    } else {
+                        restorePoint();
+                        removeNodes(B.getInclusiveNeighbourhood());
+                        removeNodes(B_.getInclusiveNeighbourhood());
+                        try_1 = 2 + maximumIndependentSetSize();
+                        restore();
+                        removeNodes(A.getInclusiveNeighbourhood());
+                        try_2 = 1 + maximumIndependentSetSizeWith2From(A.getSecondNeighbourhood());
+                        mis = Math.max(try_1, try_2);
+                    }
+                    break;
+                case 3:
+                    removeNode(A);
+                    try_1 = maximumIndependentSetSizeWith2From(A.getNeighbourhood());
+                    removeNodes(A.getNeighbourhood());
+                    try_2 = 1 + maximumIndependentSetSize();
+                    mis = Math.max(try_1, try_2);
+                    break;
+                default:
+                    if (A.dominates(B)) {
+                        removeNode(B);
+                        mis = maximumIndependentSetSize();
+                    } else {
+                        removeNode(B);
+                        try_1 = maximumIndependentSetSize();
+                        removeNodes(B.getNeighbourhood());
+                        try_2 = 1 + maximumIndependentSetSize();
+                        mis = Math.max(try_1, try_2);
+                    }
+                    break;
+            }
+        } else {
+            mis = partition.maximumIndependentSetSize();
+            removeNodes(partition.nodes);
+            mis += maximumIndependentSetSize();
+        }
+
+        restore();
+        return mis;
+    }
+
+    private int maximumIndependentSetSizeWith1From(Node s_1, Node s_2) {
+        assert s_1.getDegree() <= s_2.getDegree();
+
+        int mis = 0;
+        restorePoint();
+
+        if (s_1.getDegree() <= 1) {
+            mis = maximumIndependentSetSize();
+        } else if (s_1.getNeighbourhood().contains(s_2)) {
+            if (s_1.getDegree() <= 3) {
+                mis = maximumIndependentSetSize();
+            } else {
+                int try_1, try_2;
+                restorePoint();
+                removeNodes(s_1.getInclusiveNeighbourhood());
+                try_1 = maximumIndependentSetSize();
+                restore();
+                removeNodes(s_2.getInclusiveNeighbourhood());
+                try_2 = maximumIndependentSetSize();
+                mis = Math.max(try_1, try_2) + 1;
+            }
+        } else if (!s_1.neighbourhoodsDisjoint(s_2)) {
+            removeNodes(s_1.neighbourhoodIntersection(s_2));
+            mis = maximumIndependentSetSizeWith1From(s_1, s_2);
+        } else if (s_2.getDegree() == 2) {
+            Node E = s_1.getNeighbourhood().get(0), F = s_1.getNeighbourhood().get(1);
+            if (E.getNeighbourhood().contains(F)) {
+                removeNodes(s_1.getInclusiveNeighbourhood());
+                mis = 1 + maximumIndependentSetSize();
+            } else {
+                boolean subset = true;
+                for (Node n : E.getNeighbourhood())
+                    if (n != s_1 && !s_2.getNeighbourhood().contains(n))
+                        subset = false;
+                for (Node n : F.getNeighbourhood())
+                    if (n != s_1 && !s_2.getNeighbourhood().contains(n))
+                        subset = false;
+                if (subset) {
+                    removeNodes(s_1.getInclusiveNeighbourhood());
+                    removeNodes(s_2.getInclusiveNeighbourhood());
+                    mis = 3 + maximumIndependentSetSize();
+                } else {
+                    int try_1, try_2;
+                    removeNodes(s_1.getInclusiveNeighbourhood());
+                    try_1 = 1 + maximumIndependentSetSize();
+                    removeNodes(E.getInclusiveNeighbourhood());
+                    removeNodes(F.getInclusiveNeighbourhood());
+                    removeNodes(s_2.getInclusiveNeighbourhood());
+                    try_2 = 3 + maximumIndependentSetSize();
+                    mis = Math.max(try_1, try_2);
+                }
+            }
+        } else {
+            int try_1, try_2;
+            restorePoint();
+            removeNodes(s_2.getInclusiveNeighbourhood());
+            try_1 = maximumIndependentSetSize();
+            restore();
+            removeNodes(s_1.getInclusiveNeighbourhood());
+            removeNode(s_2);
+            try_2 = maximumIndependentSetSizeWith2From(s_2.getNeighbourhood());
+            mis = Math.max(try_1, try_2);
+        }
+
+        restore();
+        return mis;
+    }
+
+    private int maximumIndependentSetSizeWith2From(Collection<Node> Scol) {
+        List<Node> S = new ArrayList<>(Scol);
+        int mis = 0;
+        restorePoint();
+
+        if (S.size() < 2) {
+            mis = 0;
+        } else if (S.size() == 2) {
+            if (S.get(0).getNeighbourhood().contains(S.get(1)))
+                mis = 0;
+            else {
+                removeNodes(S.get(0).getInclusiveNeighbourhood());
+                removeNodes(S.get(1).getInclusiveNeighbourhood());
+                mis = 2 + maximumIndependentSetSize();
+            }
+        } else if (S.size() == 3) {
+            Node s_1 = S.get(0), s_2 = S.get(1), s_3 = S.get(2);
+            if (s_1.getDegree() == 0) {
+                removeNode(s_1);
+                mis = maximumIndependentSetSizeWith1From(s_2, s_3);
+            } else if (s_1.getNeighbourhood().contains(s_2) &&
+                    s_2.getNeighbourhood().contains(s_3) &&
+                    s_3.getNeighbourhood().contains(s_1)) {
+                mis = 0;
+            } else if (s_1.getNeighbourhood().contains(s_2) || s_1.getNeighbourhood().contains(s_3)){
+                Node s_i, s_j, s_k;
+                s_i = s_j = s_k = null;
+                if (s_1.getNeighbourhood().contains(s_2) && s_1.getNeighbourhood().contains(s_3)) {
+                    s_i = s_1; s_j = s_2; s_k = s_3;
+                } else if (s_2.getNeighbourhood().contains(s_1) && s_2.getNeighbourhood().contains(s_3)) {
+                    s_i = s_2; s_j = s_1; s_k = s_3;
+                }  else if (s_3.getNeighbourhood().contains(s_1) && s_3.getNeighbourhood().contains(s_2)) {
+                    s_i = s_3; s_j = s_1; s_k = s_2;
+                }
+
+                if (s_i != null) { // Case two edges
+                    removeNodes(s_j.getInclusiveNeighbourhood());
+                    removeNodes(s_k.getInclusiveNeighbourhood());
+                    mis = 2 + maximumIndependentSetSize();
+                } else if (s_1.getNeighbourhood().contains(s_2)) { // Case one edge
+                    removeNodes(s_3.getInclusiveNeighbourhood());
+                    mis = 1 + maximumIndependentSetSizeWith1From(s_1, s_2);
+                } else if (s_1.getNeighbourhood().contains(s_3)) { // Case one edge
+                    removeNodes(s_2.getInclusiveNeighbourhood());
+                    mis = 1 + maximumIndependentSetSizeWith1From(s_1, s_3);
+                }
+            } else if (s_2.getNeighbourhood().contains(s_3)) {
+                // Case si-sj with i=2, j=3
+                removeNodes(s_1.getInclusiveNeighbourhood());
+                mis = 1 + maximumIndependentSetSizeWith1From(s_2, s_3);
+            } else if (!s_1.neighbourhoodsDisjoint(s_2)) {
+                removeNode(s_1.neighbourhoodIntersection(s_2).get(0));
+                mis = maximumIndependentSetSizeWith2From(Scol);
+            } else if (!s_1.neighbourhoodsDisjoint(s_3)) {
+                removeNode(s_1.neighbourhoodIntersection(s_3).get(0));
+                mis = maximumIndependentSetSizeWith2From(Scol);
+            } else if (!s_2.neighbourhoodsDisjoint(s_3)) {
+                removeNode(s_2.neighbourhoodIntersection(s_3).get(0));
+                mis = maximumIndependentSetSizeWith2From(Scol);
+            } else if (s_1.getDegree() == 1) {
+                removeNodes(s_1.getInclusiveNeighbourhood());
+                mis = 1 + maximumIndependentSetSizeWith1From(s_2, s_3);
+            } else {
+                int try_1, try_2;
+                restorePoint();
+                removeNodes(s_1.getInclusiveNeighbourhood());
+                try_1 = 1 + maximumIndependentSetSizeWith1From(s_2, s_3);
+                restore();
+                removeNodes(s_2.getInclusiveNeighbourhood());
+                removeNodes(s_3.getInclusiveNeighbourhood());
+                removeNode(s_1);
+                try_2 = maximumIndependentSetSizeWith2From(s_1.getNeighbourhood());
+                mis = Math.max(try_1, try_2);
+            }
+        } else if (S.size() == 4) {
+            Collections.sort(nodes);
+            if (nodes.get(0).getDegree() <= 3) {
+                mis = maximumIndependentSetSize();
+            } else {
+                Node s_1 = S.get(0);
+                int try_1, try_2;
+                removeNode(s_1);
+                S.remove(s_1);
+                try_1 = maximumIndependentSetSizeWith2From(S);
+                removeNodes(s_1.getNeighbourhood());
+                try_2 = 1 + maximumIndependentSetSize();
+                mis = Math.max(try_1, try_2);
+            }
+        }
+
+        restore();
+        return mis;
+    }
+
+    private Graph findPartition() {
+        if (nodes.isEmpty())
+            return this;
+
+        List<Node> seen = new ArrayList<>();
+        Queue<Node> queue = new LinkedList<>();
+        queue.add(nodes.get(0));
+        while (!queue.isEmpty()) {
+            Node n = queue.remove();
+            queue.addAll(n.getNeighbourhood().stream().filter(x -> !seen.contains(x)).collect(Collectors.toList()));
+            seen.add(n);
+        }
+
+        return new Graph(seen);
     }
 
     /**
@@ -30,6 +272,11 @@ public class Graph {
      */
     public void addNode(Node node) {
         this.nodes.add(node);
+        for (Node n : node.getNeighbourhood())
+            if (nodes.contains(n))
+                if (!n.getNeighbourhood().contains(node))
+                    n.getNeighbourhood().add(node);
+        removedStack.peek().remove(node);
     }
 
     /**
@@ -43,25 +290,53 @@ public class Graph {
 
     /**
      * Remove a node
-     * @param n
+     * @param node
      */
-    public void removeNode(Node n) {
-        nodes.remove(n);
+    private void removeNode(Node node) {
+        nodes.remove(node);
+        for (Node n : node.getNeighbourhood())
+            if (nodes.contains(n))
+                n.getNeighbourhood().remove(node);
+        removedStack.peek().add(node);
     }
 
     /**
      * Remove a list of nodes, and update all references
      * @param ns
      */
-    public void removeNodes(Collection<Node> ns) {
+    private void removeNodes(Collection<Node> ns) {
         nodes.removeAll(ns);
+        for (Node n : nodes)
+            n.getNeighbourhood().removeAll(ns);
+        removedStack.peek().addAll(ns);
+    }
+
+    private void restorePoint() {
+        removedStack.push(new ArrayList<>());
+    }
+
+    private void restore() {
+        List<Node> removed = removedStack.pop();
+        Collections.reverse(removed);
+        for (Node node : removed) {
+            this.nodes.add(node);
+            for (Node n : node.getNeighbourhood())
+                if (nodes.contains(n))
+                    if (!n.getNeighbourhood().contains(node))
+                        n.getNeighbourhood().add(node);
+        }
+        removed.clear();
+    }
+
+    public int size() {
+        return nodes.size();
     }
 
     public String toString() {
         StringBuilder sb = new StringBuilder("Graph:");
         for (Node n : nodes) {
             sb.append("\n  ").append(n).append(":   ");
-            for (Node n2 : n.getNeighbours()) sb.append(" - ").append(n2);
+            for (Node 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 87471e8..4edc666 100644
--- a/Practical1/src/nl/camilstaps/cs/graphs/Node.java
+++ b/Practical1/src/nl/camilstaps/cs/graphs/Node.java
@@ -9,7 +9,7 @@ import java.util.List;
  *
  * @author Camil Staps
  */
-public class Node {
+public class Node implements Comparable<Node> {
     private final int content;
     private final List<Node> neighbours = new ArrayList<>();
 
@@ -17,19 +17,50 @@ public class Node {
         this.content = content;
     }
 
-    /**
-     * Create a copy of another Node
-     * @param copy
-     */
-    public Node(Node copy) {
-        this.content = copy.content;
-        this.neighbours.addAll(copy.neighbours);
+    public int getDegree() {
+        return neighbours.size();
     }
 
-    public List<Node> getNeighbours() {
+    public List<Node> getNeighbourhood() {
         return neighbours;
     }
 
+    public List<Node> getInclusiveNeighbourhood() {
+        List<Node> nb = new ArrayList<>();
+        nb.add(this);
+        nb.addAll(neighbours);
+        return nb;
+    }
+
+    public List<Node> getSecondNeighbourhood() {
+        List<Node> nb = new ArrayList<>();
+        for (Node n : getNeighbourhood())
+            for (Node n2 : n.getNeighbourhood())
+                if (!nb.contains(n2))
+                    nb.add(n2);
+        nb.remove(this);
+        return nb;
+    }
+
+    public boolean dominates(Node b) {
+        for (Node nb : getInclusiveNeighbourhood())
+            if (!b.getInclusiveNeighbourhood().contains(nb))
+                return false;
+        return true;
+    }
+
+    public boolean neighbourhoodsDisjoint(Node b) {
+        return neighbourhoodIntersection(b).isEmpty();
+    }
+
+    public List<Node> neighbourhoodIntersection(Node b) {
+        List<Node> intersection = new ArrayList<>();
+        for (Node n : neighbours)
+            if (b.getNeighbourhood().contains(n))
+                intersection.add(n);
+        return intersection;
+    }
+
     public String toString() {
         return "<" + content + ">";
     }
@@ -43,4 +74,9 @@ public class Node {
         return !(another == null || another.getClass() != this.getClass()) &&
                 content == (((Node) another).content);
     }
+
+    @Override
+    public int compareTo(Node node) {
+        return node == null ? 1 : Integer.compare(neighbours.size(), node.neighbours.size());
+    }
 }