Instructions
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);
}
}
}