diff options
Diffstat (limited to 'Practical1')
| -rw-r--r-- | Practical1/src/nl/camilstaps/cs/GarbageCollectionHelper.java | 2 | ||||
| -rw-r--r-- | Practical1/src/nl/camilstaps/cs/graphs/Graph.java | 260 | ||||
| -rw-r--r-- | Practical1/src/nl/camilstaps/cs/graphs/Node.java | 59 | ||||
| -rwxr-xr-x | Practical1/tester/test.sh | 17 |
4 files changed, 235 insertions, 103 deletions
diff --git a/Practical1/src/nl/camilstaps/cs/GarbageCollectionHelper.java b/Practical1/src/nl/camilstaps/cs/GarbageCollectionHelper.java index 282cfb3..0da2dc5 100644 --- a/Practical1/src/nl/camilstaps/cs/GarbageCollectionHelper.java +++ b/Practical1/src/nl/camilstaps/cs/GarbageCollectionHelper.java @@ -14,7 +14,7 @@ class GarbageCollectionHelper { /** * Read in a Graph from stdin and print whether we can place N bins to stdout - * @param args + * @param args Command line arguments (are ignored) */ public static void main(String[] args) { Graph graph = new Graph(); diff --git a/Practical1/src/nl/camilstaps/cs/graphs/Graph.java b/Practical1/src/nl/camilstaps/cs/graphs/Graph.java index 0da1924..f1bf946 100644 --- a/Practical1/src/nl/camilstaps/cs/graphs/Graph.java +++ b/Practical1/src/nl/camilstaps/cs/graphs/Graph.java @@ -10,7 +10,8 @@ import java.util.stream.Collectors; */ public class Graph { private final List<Node> nodes; - private final Stack<List<Node>> removedStack = new Stack<>(); + // When removing nodes, it's possible to create restore points to add them back later on. + private final Stack<List<Node>> restorePoints = new Stack<>(); public Graph() { this.nodes = new ArrayList<>(); @@ -22,15 +23,24 @@ public class Graph { restorePoint(); } + /** + * Computes the size of the maximum independent set using Robson's algorithm. + * + * @see #maximumIndependentSetSizeWith1From(Node, Node) + * @see #maximumIndependentSetSizeWith2From(Collection) + * + * @return the size of the maximum independent set + */ public int maximumIndependentSetSize() { if (nodes.size() <= 1) return nodes.size(); - int mis = 0; + int miss; restorePoint(); - Graph partition = findPartition(); - if (partition.size() == size()) { + Graph 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); Collections.sort(A.getNeighbourhood(), Collections.reverseOrder()); @@ -39,14 +49,17 @@ public class Graph { int try_1, try_2; switch (A.getDegree()) { case 1: + // One neighbour; pick A and continue with the rest of the Graph. removeNodes(A.getInclusiveNeighbourhood()); - mis = 1 + maximumIndependentSetSize(); + miss = 1 + maximumIndependentSetSize(); break; 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); if (B.getNeighbourhood().contains(B_)) { removeNodes(A.getInclusiveNeighbourhood()); - mis = 1 + maximumIndependentSetSize(); + miss = 1 + maximumIndependentSetSize(); } else { restorePoint(); removeNodes(B.getInclusiveNeighbourhood()); @@ -55,50 +68,64 @@ public class Graph { restore(); removeNodes(A.getInclusiveNeighbourhood()); try_2 = 1 + maximumIndependentSetSizeWith2From(A.getSecondNeighbourhood()); - mis = Math.max(try_1, try_2); + miss = Math.max(try_1, try_2); } break; case 3: + // Three neighbours: either we pick two of the neighbours, or we pick A. removeNode(A); try_1 = maximumIndependentSetSizeWith2From(A.getNeighbourhood()); removeNodes(A.getNeighbourhood()); try_2 = 1 + maximumIndependentSetSize(); - mis = Math.max(try_1, try_2); + miss = Math.max(try_1, try_2); break; default: + // If A dominates his neighbour we may safely remove that neighbour. Otherwise, we try both with + // and without the neighbour. if (A.dominates(B)) { removeNode(B); - mis = maximumIndependentSetSize(); + miss = maximumIndependentSetSize(); } else { removeNode(B); try_1 = maximumIndependentSetSize(); removeNodes(B.getNeighbourhood()); try_2 = 1 + maximumIndependentSetSize(); - mis = Math.max(try_1, try_2); + miss = Math.max(try_1, try_2); } break; } } else { - mis = partition.maximumIndependentSetSize(); - removeNodes(partition.nodes); - mis += maximumIndependentSetSize(); + // Case: at least two strongly connected components. Compute for the first component, and for the rest. + miss = stronglyConnectedComponent.maximumIndependentSetSize(); + removeNodes(stronglyConnectedComponent.nodes); + miss += maximumIndependentSetSize(); } restore(); - return mis; + return miss; } + /** + * Compute the maximum independent set size if it should contain (at least) one of two nodes. + * + * This is a helper function for {@link #maximumIndependentSetSizeWith2From(Collection)}, which is a helper + * function for {@link #maximumIndependentSetSize()}, which uses Robson's algorithm. + * + * @param s_1 The first node + * @param s_2 The second node + * @return the maximum independent set size + */ private int maximumIndependentSetSizeWith1From(Node s_1, Node s_2) { assert s_1.getDegree() <= s_2.getDegree(); - int mis = 0; + int miss; restorePoint(); if (s_1.getDegree() <= 1) { - mis = maximumIndependentSetSize(); + miss = maximumIndependentSetSize(); } else if (s_1.getNeighbourhood().contains(s_2)) { if (s_1.getDegree() <= 3) { - mis = maximumIndependentSetSize(); + miss = maximumIndependentSetSize(); } else { int try_1, try_2; restorePoint(); @@ -107,16 +134,16 @@ public class Graph { restore(); removeNodes(s_2.getInclusiveNeighbourhood()); try_2 = maximumIndependentSetSize(); - mis = Math.max(try_1, try_2) + 1; + miss = 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); + 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); if (E.getNeighbourhood().contains(F)) { removeNodes(s_1.getInclusiveNeighbourhood()); - mis = 1 + maximumIndependentSetSize(); + miss = 1 + maximumIndependentSetSize(); } else { boolean subset = true; for (Node n : E.getNeighbourhood()) @@ -128,7 +155,7 @@ public class Graph { if (subset) { removeNodes(s_1.getInclusiveNeighbourhood()); removeNodes(s_2.getInclusiveNeighbourhood()); - mis = 3 + maximumIndependentSetSize(); + miss = 3 + maximumIndependentSetSize(); } else { int try_1, try_2; removeNodes(s_1.getInclusiveNeighbourhood()); @@ -137,7 +164,7 @@ public class Graph { removeNodes(F.getInclusiveNeighbourhood()); removeNodes(s_2.getInclusiveNeighbourhood()); try_2 = 3 + maximumIndependentSetSize(); - mis = Math.max(try_1, try_2); + miss = Math.max(try_1, try_2); } } } else { @@ -149,40 +176,67 @@ public class Graph { removeNodes(s_1.getInclusiveNeighbourhood()); removeNode(s_2); try_2 = maximumIndependentSetSizeWith2From(s_2.getNeighbourhood()); - mis = Math.max(try_1, try_2); + miss = Math.max(try_1, try_2); } restore(); - return mis; + return miss; } + /** + * Compute the maximum independent set size if at least two Nodes of some set should be in it. + * + * This is a helper function for {@link #maximumIndependentSetSize()}, which uses Robson's algorithm. + * + * @see #maximumIndependentSetSizeWith1From(Node, Node) + * + * @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); - int mis = 0; + int miss; restorePoint(); if (S.size() < 2) { - mis = 0; + // Less than two Nodes to pick from; this is impossible + miss = 0; } else if (S.size() == 2) { + // Two Nodes to pick from; try to pick both and fail otherwise. if (S.get(0).getNeighbourhood().contains(S.get(1))) - mis = 0; + miss = 0; else { removeNodes(S.get(0).getInclusiveNeighbourhood()); removeNodes(S.get(1).getInclusiveNeighbourhood()); - mis = 2 + maximumIndependentSetSize(); + miss = 2 + maximumIndependentSetSize(); } } 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); + + // 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) { removeNode(s_1); - mis = maximumIndependentSetSizeWith1From(s_2, s_3); - } else if (s_1.getNeighbourhood().contains(s_2) && + miss = 1 + maximumIndependentSetSizeWith1From(s_2, s_3); + } else if (s_2.getDegree() == 0) { + removeNode(s_2); + miss = 1 + maximumIndependentSetSizeWith1From(s_1, s_3); + } else if (s_3.getDegree() == 0) { + removeNode(s_3); + miss = 1 + maximumIndependentSetSizeWith1From(s_1, s_2); + } + // If the Nodes are connected we can't choose two in an independent set. + 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)){ + miss = 0; + } + // 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; s_i = s_j = s_k = null; + + // If there are two edges among S, say si-sj-sk, we pick si and sk. 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)) { @@ -191,34 +245,46 @@ public class Graph { s_i = s_3; s_j = s_1; s_k = s_2; } - if (s_i != null) { // Case two edges + // Check if we managed to find two edges. If not, there must be at least one edge, say si-sj. We then + // choose sk and either si or sj. These are the cases that s_1 != sk. + 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 + miss = 2 + maximumIndependentSetSize(); + } else if (s_1.getNeighbourhood().contains(s_2)) { // Case one edge; s_1 - s_2 removeNodes(s_3.getInclusiveNeighbourhood()); - mis = 1 + maximumIndependentSetSizeWith1From(s_1, s_2); - } else if (s_1.getNeighbourhood().contains(s_3)) { // Case one edge + miss = 1 + maximumIndependentSetSizeWith1From(s_1, s_2); + } else { // Case one edge; s_1 - s_3 (implicit) removeNodes(s_2.getInclusiveNeighbourhood()); - mis = 1 + maximumIndependentSetSizeWith1From(s_1, s_3); + miss = 1 + maximumIndependentSetSizeWith1From(s_1, s_3); } - } else if (s_2.getNeighbourhood().contains(s_3)) { - // Case si-sj with i=2, j=3 + } + // Final case with one edge; between s_2 and s_3: pick s_1 and either s_2 or s_3. + else if (s_2.getNeighbourhood().contains(s_3)) { removeNodes(s_1.getInclusiveNeighbourhood()); - mis = 1 + maximumIndependentSetSizeWith1From(s_2, s_3); - } else if (!s_1.neighbourhoodsDisjoint(s_2)) { + miss = 1 + maximumIndependentSetSizeWith1From(s_2, s_3); + } + // When two neighbourhoods of two nodes si, sj aren't disjoint, we can remove the intersection, because + // either si or sj is in the independent set and so the intersection is not. The intersection has at most + // one member. + else if (!s_1.neighbourhoodsDisjoint(s_2)) { removeNode(s_1.neighbourhoodIntersection(s_2).get(0)); - mis = maximumIndependentSetSizeWith2From(Scol); + miss = maximumIndependentSetSizeWith2From(Scol); } else if (!s_1.neighbourhoodsDisjoint(s_3)) { removeNode(s_1.neighbourhoodIntersection(s_3).get(0)); - mis = maximumIndependentSetSizeWith2From(Scol); + miss = 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) { + miss = maximumIndependentSetSizeWith2From(Scol); + } + // If s_1 has degree 1, we pick it and either s_2 or s_3 + else if (s_1.getDegree() == 1) { removeNodes(s_1.getInclusiveNeighbourhood()); - mis = 1 + maximumIndependentSetSizeWith1From(s_2, s_3); - } else { + miss = 1 + maximumIndependentSetSizeWith1From(s_2, s_3); + } + // If all else fails, we try both picking s_1 with either s_2 or s_3, and picking s_1 and s_2 and at least + // one neighbour of s_1 (Note: Robson has forgotten to add 2 for s_2 and s_3 in this step). + else { int try_1, try_2; restorePoint(); removeNodes(s_1.getInclusiveNeighbourhood()); @@ -227,13 +293,15 @@ public class Graph { removeNodes(s_2.getInclusiveNeighbourhood()); removeNodes(s_3.getInclusiveNeighbourhood()); removeNode(s_1); - try_2 = maximumIndependentSetSizeWith2From(s_1.getNeighbourhood()); - mis = Math.max(try_1, try_2); + try_2 = 2 + maximumIndependentSetSizeWith2From(s_1.getNeighbourhood()); + miss = Math.max(try_1, try_2); } } else if (S.size() == 4) { + // Four Nodes to pick from. If there's a node with degree <= 3 in the Graph, it's more efficient to just + // compute normally. If not, we try recursively both with and without the first Node in S. Collections.sort(nodes); if (nodes.get(0).getDegree() <= 3) { - mis = maximumIndependentSetSize(); + miss = maximumIndependentSetSize(); } else { Node s_1 = S.get(0); int try_1, try_2; @@ -242,15 +310,24 @@ public class Graph { try_1 = maximumIndependentSetSizeWith2From(S); removeNodes(s_1.getNeighbourhood()); try_2 = 1 + maximumIndependentSetSize(); - mis = Math.max(try_1, try_2); + miss = Math.max(try_1, try_2); } + } else { + miss = maximumIndependentSetSize(); } restore(); - return mis; + return miss; } - private Graph findPartition() { + /** + * Find a strongly connected component of the graph. This may return itself, if the graph is empty or connected. + * It is not guaranteed that the smallest / largest strongly connected component is returned. The method simply + * returns the one that contains the first node (if it exists). + * + * @return some strongly connected component + */ + private Graph findStronglyConnectedComponent() { if (nodes.isEmpty()) return this; @@ -267,71 +344,98 @@ public class Graph { } /** - * Add a Node - * @param node + * Add a Node, and update its neighbours to include it as a neighbour. + * @param node the Node to add */ 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); + node.getNeighbourhood().stream() + .filter(nodes::contains) + .filter(n -> !n.getNeighbourhood().contains(node)) + .forEach(n -> n.getNeighbourhood().add(node)); + restorePoints.peek().remove(node); } /** - * Get a Node - * @param i - * @return + * Get a Node by its index. Note: some internal methods may reorder the list; only use this directly after adding + * nodes. + * @param i the index in the list + * @return the Node */ public Node getNode(int i) { return this.nodes.get(i); } /** - * Remove a node - * @param node + * Remove a node, and remove its reference from its neighbours that are still in the graph + * + * @see #removeNodes(Collection) + * + * @param node the Node */ 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); + node.getNeighbourhood().stream() + .filter(nodes::contains) + .forEach(n -> n.getNeighbourhood().remove(node)); + restorePoints.peek().add(node); } /** * Remove a list of nodes, and update all references - * @param ns + * + * @see #removeNode(Node) + * + * @param ns the Nodes to remove */ private void removeNodes(Collection<Node> ns) { nodes.removeAll(ns); for (Node n : nodes) n.getNeighbourhood().removeAll(ns); - removedStack.peek().addAll(ns); + restorePoints.peek().addAll(ns); } + /** + * Create a restore point to return back to after removing some Nodes. + * + * @see #restore() + * @see #restorePoints + */ private void restorePoint() { - removedStack.push(new ArrayList<>()); + restorePoints.push(new ArrayList<>()); } + /** + * Go back to the last restore point, re-adding all Nodes that were removed since then. + * + * @see #restorePoint() + * @see #restorePoints + */ private void restore() { - List<Node> removed = removedStack.pop(); + List<Node> removed = restorePoints.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); + node.getNeighbourhood().stream() + .filter(nodes::contains) + .filter(n -> !n.getNeighbourhood().contains(node)) + .forEach(n -> n.getNeighbourhood().add(node)); } removed.clear(); } + /** + * The size of the graph is the number of Nodes. + * @return the number of Nodes. + */ public int size() { return nodes.size(); } + /** + * Represent the Graph as a String + * @return a String representation of the Graph + */ public String toString() { StringBuilder sb = new StringBuilder("Graph:"); for (Node n : nodes) { diff --git a/Practical1/src/nl/camilstaps/cs/graphs/Node.java b/Practical1/src/nl/camilstaps/cs/graphs/Node.java index 4edc666..b9d078e 100644 --- a/Practical1/src/nl/camilstaps/cs/graphs/Node.java +++ b/Practical1/src/nl/camilstaps/cs/graphs/Node.java @@ -2,6 +2,7 @@ package nl.camilstaps.cs.graphs; import java.util.ArrayList; import java.util.List; +import java.util.stream.Collectors; /** * A Node is a simple point in a graph, with references to its neighbours. It holds an integer 'content' which can act @@ -17,14 +18,23 @@ public class Node implements Comparable<Node> { this.content = content; } + /** + * @return the number of neighbours + */ public int getDegree() { return neighbours.size(); } + /** + * @return the neighbours + */ public List<Node> getNeighbourhood() { return neighbours; } + /** + * @return the neighbours with the Node itself + */ public List<Node> getInclusiveNeighbourhood() { List<Node> nb = new ArrayList<>(); nb.add(this); @@ -32,16 +42,22 @@ public class Node implements Comparable<Node> { return nb; } + /** + * @return the neighbours of the neighbours, without this Node itself + */ 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); + n.getNeighbourhood().stream().filter(n2 -> !nb.contains(n2)).forEach(nb::add); nb.remove(this); return nb; } + /** + * Node a dominates a Node b if the inclusive neighbourhood of a is a subset of the inclusive neighbourhood of b. + * @param b the Node to compare to + * @return true iff this Node dominates Node b + */ public boolean dominates(Node b) { for (Node nb : getInclusiveNeighbourhood()) if (!b.getInclusiveNeighbourhood().contains(nb)) @@ -49,34 +65,47 @@ public class Node implements Comparable<Node> { return true; } + /** + * @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) { return neighbourhoodIntersection(b).isEmpty(); } + /** + * @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) { - List<Node> intersection = new ArrayList<>(); - for (Node n : neighbours) - if (b.getNeighbourhood().contains(n)) - intersection.add(n); - return intersection; + return neighbours.stream().filter(n -> b.getNeighbourhood().contains(n)).collect(Collectors.toList()); } + /** + * @return a String representation of the Node + */ public String toString() { return "<" + content + ">"; } /** * Nodes are equal if their identifiers are equal - * @param another - * @return + * @param b the Node to compare to + * @return true iff this Node is equivalent to Node b */ - public boolean equals(Object another) { - return !(another == null || another.getClass() != this.getClass()) && - content == (((Node) another).content); + public boolean equals(Object b) { + return !(b == null || b.getClass() != this.getClass()) && + content == (((Node) b).content); } + /** + * This method allows sorting of Nodes by their degrees. + * @param b the Node to compare to + * @return 1 if d(this) > d(b), -1 if d(this) < d(b), 0 otherwise + */ @Override - public int compareTo(Node node) { - return node == null ? 1 : Integer.compare(neighbours.size(), node.neighbours.size()); + @SuppressWarnings("NullableProblems") + public int compareTo(Node b) { + return Integer.compare(neighbours.size(), b.neighbours.size()); } } diff --git a/Practical1/tester/test.sh b/Practical1/tester/test.sh index 068d6ea..83fdccb 100755 --- a/Practical1/tester/test.sh +++ b/Practical1/tester/test.sh @@ -4,8 +4,7 @@ java="/usr/lib/jvm/java-8-openjdk-amd64/bin/java" failed=0 cd "$(dirname $0)/../out/production/Practical1" -for tc in ../../../tester/samples/*.in -do +for tc in ../../../tester/samples/*.in; do answer=$(cat ${tc/in/out}) header=$(head -n1 "$tc" | tr -d '\n') echo -n "Running $(basename $tc) $(printf '%-12s' "($answer ")$(printf '%-12s' "/ $header)") ... " @@ -13,20 +12,20 @@ do result=$(eval "cat '$tc' | /usr/lib/jvm/java-8-openjdk-amd64/bin/java nl.camilstaps.cs.GarbageCollectionHelper") time_end=$(($(date +%s%N)/1000000)) time=`expr $time_end - $time_start` - if [ $result != $answer ] - then + if [ $result != $answer ]; then echo "failure ($time ms)." failed=$(($failed+1)) else echo "success ($time ms)." fi done -cd - +cd - >/dev/null -if [ $failed -eq 0 ] -then - echo "All tests passed" +if [ $failed -eq 0 ]; then + echo "All tests passed." +elif [ $failed -eq 1 ]; then + echo "1 test failed." else - echo "$failed tests failed" + echo "$failed tests failed." fi |