# 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).

*

* @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);

}

}

// 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

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

* 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)) {

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

assert wellFormed() : "invariant broken at start of add(" + 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

}

@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;

}

}

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

}

}

}