Implement A Hashing and Graphs ADT In Java Assignment Solution

Instructions

Objective

Write a java assignment program to implement hash and graphs ADT.

Requirements and Specifications

Source Code

package edu.uwm.cs351.util; import java.util.AbstractSet; import java.util.Arrays; import java.util.Collections; import java.util.ConcurrentModificationException; import java.util.HashMap; import java.util.HashSet; import java.util.Iterator; import java.util.Map; import java.util.NoSuchElementException; import java.util.Set; import java.util.TreeMap; import java.util.TreeSet; import java.util.function.Consumer; import junit.framework.TestCase; /** * An undirected graph structure. * The vertices may be from any class (but must not be null). * Adding an edge implicitly adds the vertices if needed. * * @param T type of the vertices */ public class HashGraph implements Graph { private Map> edges; private int edgesVersion; // updated when number of edges changes private int verticesVersion; // updated when number of vertices changes private int size; private static Consumer reporter = (s) -> System.out.println("Invariant error: " + s); private boolean report(String s) { reporter.accept(s); return false; } private boolean wellFormed() { // Invariant // 1. Edges map cannot be null // 2. Every entry in edges map has a non-null set value // 3. No vertex has an edge to itself // 4. Every edge is represented twice in edges map // e.g. If edge (a-b) exists then it must also exist as (b-a) // 5. size contains the number of unique edges in the graph // NB: edge (a-b) and edge (b-a) represent a single edge. // 1. Edges map cannot be null if (edges == null) { return report("Edges map is null"); } // 2. Every entry in edges map has a non-null set value for (Set s : edges.values()) { if (s == null) { return report("Entry in edges map has null value"); } } // 3. No vertex has an edge to itself for (T v : edges.keySet()) { if (v != null && edges.get(v) != null && edges.get(v).contains(v)) { return report("Vertex has an edge to itself"); } } // 4. Every edge is represented twice in edges map // e.g. If edge (a-b) exists then it must also exist as (b-a) Set> uniqueEdges = new HashSet<>(); for (T a : edges.keySet()) { for (T b : edges.get(a)) { if (b == null || edges.get(b) == null || !(edges.get(b).contains(a))) { return report("Every edge is not represented twice in edges map"); } Edge edge = new Edge<>(a, b); uniqueEdges.add(edge); } } // 5. size contains the number of unique edges in the graph // NB: edge (a-b) and edge (b-a) represent a single edge. if (uniqueEdges.size() != this.size) { return report("Size is not equal to number of edges in graph"); } return true; } /** * Create a new empty graph. */ public HashGraph() { this.size = 0; this.edgesVersion = 0; this.verticesVersion = 0; this.edges = new HashMap<>(); } //Don't remove - used for invariant tests private HashGraph(boolean ignored) { } @Override public int order() { return this.verticesVersion; } @Override public int size() { return this.size; } @Override public boolean addVertex(T x) { if (x == null) { throw new IllegalArgumentException(); } assert wellFormed() : "invariant broken at start of addVertex(" + x + ")"; boolean result = false; if (!containsVertex(x)) { this.edges.put(x, new HashSet<>()); this.verticesVersion++; result = true; } assert wellFormed() : "invariant broken at end of addVertex(" + x + ")"; return result; } @Override public boolean containsVertex(T x) { assert wellFormed() : "Invariant broken at start of containsVertex(" + x + ");"; return this.edges.containsKey(x); } /** * Optional helper method so that code can be shared between * {@link #removeVertex(Object)} and {@link MyVertexIterator#remove()}. * This method cleans up any edges referring to this node, and updates size accordingly. * * @param a vertex that was removed * @param formerNeighbors vertices formerly reachable in one step from the removed vertex */ private void removeVertexHelper(T a, Set formerNeighbors) { for (T x : formerNeighbors) { edges.get(x).remove(a); size--; } } @Override public boolean removeVertex(T a) { if (a == null) { throw new IllegalArgumentException(); } assert wellFormed() : "invariant broken at start of removeVertex(" + a + ")"; boolean result = false; if (containsVertex(a)) { removeVertexHelper(a, edges.get(a)); this.edges.remove(a); this.verticesVersion--; result = true; } assert wellFormed() : "invariant broken at end of removeVertex(" + a + ")"; return result; } @Override public boolean addEdge(T a, T b) { if (a == null || b == null || a.equals(b)) { throw new IllegalArgumentException(); } assert wellFormed() : "invariant broken at start of addEdge(" + a + "," + b + ")"; boolean result = false; if (!containsEdge(a, b)) { addVertex(a); addVertex(b); this.edges.get(a).add(b); this.edges.get(b).add(a); this.edgesVersion++; this.size++; result = true; } assert wellFormed() : "invariant broken at end of addEdge(" + a + "," + b + ")"; return result; } @Override public boolean removeEdge(T a, T b) { assert wellFormed() : "invariant broken at start of removeEdge(" + a + "," + b + ")"; boolean result = false; if (containsEdge(a, b)) { this.edges.get(a).remove(b); this.edges.get(b).remove(a); this.edgesVersion--; this.size--; result = true; } assert wellFormed() : "invariant broken at end of removeEdge(" + a + "," + b + ")"; return result; } @Override public boolean containsEdge(T a, T b) { assert wellFormed() : "invariant broken at start of containsEdge(" + a + "," + b + ")"; if (a == null || b == null) { return false; } if (!containsVertex(a)) { return false; } return edges.get(a).contains(b); } @Override public Set getConnected(T a) { assert wellFormed() : "invariant broken at start of getConnected(" + a + ")"; // NB: You may find the java.util.Collections class helpful for // the various unmodifiable collection wrappers. if (a == null) { return null; } if (!containsVertex(a)) { return null; } return Collections.unmodifiableSet(edges.get(a)); } private Set vertexSet; @Override public Set vertexSet() { if (vertexSet == null) { vertexSet = new MyVertexSet(); } return vertexSet; } private class MyVertexSet extends AbstractSet { @Override public int size() { assert wellFormed() : "invariant broken at start of size()"; return edges.size(); } @Override public boolean add(T x) { assert wellFormed() : "invariant broken at start of add(" + x + ")"; return addVertex(x); } @Override public boolean contains(Object o) { assert wellFormed() : "invariant broken at start of contains(" + o + ")"; return edges.containsKey(o); } @Override public boolean remove(Object o) { assert wellFormed() : "invariant broken at start of contains(" + o + ")"; @SuppressWarnings("unchecked") T v = (T) o; return removeVertex(v); } public Iterator iterator() { assert wellFormed() : "invariant broken at start of iterator()"; return new MyVertexIterator(); } private class MyVertexIterator implements Iterator { private Iterator iterator = edges.keySet().iterator(); private T current; private int myVersion = verticesVersion; // Unfortunately, remove() cannot call // removeVertex() (optional exercise: Why not?). // If an edge is added while iterating over vertices, the // vertex iterator shouldn't throw a CME (unless adding the edge // necessitated adding a vertex as well). protected void checkVersion() { if (verticesVersion != myVersion) { throw new ConcurrentModificationException("stale"); } } @Override public boolean hasNext() { checkVersion(); return iterator.hasNext(); } @Override public T next() { checkVersion(); current = iterator.next(); return current; } @Override public void remove() { checkVersion(); if (current == null) { throw new IllegalStateException(); } removeVertexHelper(current, edges.get(current)); iterator.remove(); verticesVersion--; myVersion--; current = null; } } } private Set> edgeSet; @Override public Set> edgeSet() { if (edgeSet == null) { edgeSet = new MyEdgeSet(); } return edgeSet; } private class MyEdgeSet extends AbstractSet> { public int size() { return HashGraph.this.size(); } @Override public boolean add(Edge e) { return addEdge(e.a, e.b); } @Override public boolean contains(Object o) { assert wellFormed() : "invariant broken at start of contains(" + o + ")"; // First check that we actually have an edge object // (The ? means we don't care what the type is.) if (!(o instanceof Edge)) { return false; } Edge e = (Edge) o; // make use of the fact that Map.get handles any type Set s = edges.get(e.a); return s != null && s.contains(e.b); } @Override @SuppressWarnings("unchecked") public boolean remove(Object o) { assert wellFormed() : "invariant broken at start of remove(" + o + ")"; if (!contains(o)) { return false; } Edge edge = (Edge) o; return removeEdge(edge.a, edge.b); } public Iterator> iterator() { assert wellFormed() : "invariant broken at start of iterator()"; return new MyEdgeIterator(); } private class MyEdgeIterator implements Iterator> { private Iterator>> outer = edges.entrySet().iterator(); private Iterator inner = Collections.emptyIterator(); private Set seen = new HashSet(); // vertices previously handled private int myVerticesVersion = verticesVersion; private int myVersion = edgesVersion; private int remaining = size; // number of edges still to return private T a, b; // latest vertices connected by an edge returned by next() // DESIGN: // We have an outer iterator that goes though the vertices // in the graph at the time the iterator was created, // and then an inner iterator that goes through // adjacent vertices in the set in the entry. // // The outer iterator can go stale if the number of vertices // changes, even if the number of edges does *not* change. // When that happens, we re-initialize the outer iterator, // which might then repeat vertices we've already seen. // So we keep a set of vertices that have already been seen. // // And we don't want to return the same edge twice, // which could easily happen (once in each direction). So the // seen set has another use, we only return an edge whose second // vertex has already been seen. // // We also remember the last edge returned by next, which // helps for remove(), to handle the dual edge entry. // (If we're removing a -> b, we have to also remove b -> a.) private boolean wellFormed() { if (!HashGraph.this.wellFormed()) { return false; } if (myVersion == edgesVersion) { if (outer == null) { return report("iterator outer is null"); } if (inner == null) { return report("iterator inner is null"); } if (remaining < 0 || remaining > size) { return report("remaining bad: " + remaining); } } return true; } private void checkVersion() { if (myVersion != edgesVersion) { throw new ConcurrentModificationException("versions mismatch"); } if (myVerticesVersion != verticesVersion) { // update the outer iterator outer = edges.entrySet().iterator(); myVerticesVersion = verticesVersion; } } MyEdgeIterator() { assert wellFormed() : "invariant broken at the iterator constructor"; } public boolean hasNext() { checkVersion(); return remaining > 0; } public Edge next() { assert wellFormed() : "invariant broken at the start of next()"; if (!hasNext()) { throw new NoSuchElementException(); } boolean found = false; while (true) { if (a != null) { while (inner.hasNext()) { T curr = inner.next(); if (seen.contains(curr)) { b = curr; found = true; remaining--; break; } } if (found) { break; } seen.add(a); } do { Map.Entry> entry = outer.next(); a = entry.getKey(); inner = entry.getValue().iterator(); } while (seen.contains(a)); } assert wellFormed() : "invariant broken at end of next()"; return new Edge(a, b); } public void remove() { checkVersion(); assert wellFormed() : "invariant broken at the start of remove()"; if (a == null) { throw new IllegalStateException(); } inner.remove(); edges.get(b).remove(a); size--; myVersion--; edgesVersion--; a = null; outer = edges.entrySet().iterator(); // NB: don't call removeEdge or you will get a CME in remove tests. assert wellFormed() : "invariant broken at the end of remove()"; } } } public static class TestInvariant extends TestCase { private static String lastMessage; private static Consumer saveMessage = (s) -> lastMessage = s; private static Consumer errorMessage = (s) -> System.err.println("Erroneously reported problem: " + (lastMessage = s)); private HashGraph self; @Override protected void setUp() { self = new HashGraph<>(false); } protected void assertWellFormed(boolean expected) { reporter = expected ? errorMessage : saveMessage; lastMessage = null; assertEquals(expected, self.wellFormed()); reporter = saveMessage; if (expected == false) { assertTrue("Didn't report problem", lastMessage != null && lastMessage.trim().length() > 0); } } public void testA() { self.edges = new TreeMap<>(); assertWellFormed(true); } public void testB() { self.edges = null; assertWellFormed(false); } public void testC() { self.edges = new HashMap<>(); self.edges.put(1, new TreeSet<>()); assertWellFormed(true); } public void testD() { self.edges = new HashMap<>(); self.edges.put(1, null); assertWellFormed(false); } public void testE() { self.edges = new HashMap<>(); self.size = 1; assertWellFormed(false); } public void testF() { self.edges = new HashMap<>(); self.edges.put(1, new TreeSet<>()); self.size = 1; assertWellFormed(false); } public void testG() { self.edges = new HashMap<>(); self.edges.put(1, new TreeSet<>(Collections.singleton(1))); self.size = 1; assertWellFormed(false); } public void testH() { self.edges = new HashMap<>(); self.edges.put(1, new HashSet<>(Collections.singleton(2))); self.size = 1; assertWellFormed(false); } public void testI() { self.edges = new HashMap<>(); self.edges.put(1, new TreeSet<>(Collections.singleton(2))); self.edges.put(2, new HashSet<>(Collections.singleton(1))); self.size = 1; assertWellFormed(true); } public void testJ() { testI(); self.size = 2; assertWellFormed(false); self.size = 0; assertWellFormed(false); } public void testK() { testI(); self.edges.put(0, Collections.emptySet()); self.edges.put(3, new HashSet<>()); assertWellFormed(true); } public void testL() { self.edges = new HashMap<>(); self.edges.put(1, new HashSet<>(Collections.singleton(2))); self.edges.put(2, new HashSet<>(Collections.singleton(3))); self.size = 1; assertWellFormed(false); self.edges.put(3, Collections.emptySet()); assertWellFormed(false); self.size = 2; assertWellFormed(false); } public void testM() { self.edges = new HashMap<>(); self.edges.put(1, new TreeSet<>(Collections.singleton(2))); self.edges.put(2, new TreeSet<>(Arrays.asList(1, 2))); self.size = 1; assertWellFormed(false); self.size = 2; assertWellFormed(false); } public void testN() { self.edges = new TreeMap<>(); self.edges.put(1, new TreeSet<>(Collections.singleton(2))); self.edges.put(2, new HashSet<>(Collections.singleton(1))); self.edges.put(3, null); self.size = 1; assertWellFormed(false); self.size = 2; assertWellFormed(false); } public void testO() { self.edges = new TreeMap<>(); self.edges.put(1, new TreeSet<>(Arrays.asList(2, 3))); self.edges.put(2, new HashSet<>(Arrays.asList(1))); self.edges.put(3, new TreeSet<>(Arrays.asList(1))); self.size = 2; assertWellFormed(true); self.size = 3; assertWellFormed(false); self.size = 2; self.edges.get(3).clear(); self.edges.put(3, null); assertWellFormed(false); } } }