//Need to Find the strongly connected component and the shortest path

import java.util.ArrayList;

import java.util.HashMap;

import java.util.HashSet;

import java.util.Iterator;

import java.util.List;

import java.util.Map;

import java.util.NoSuchElementException;

import java.util.Set;

public class AdjacencyListGraph extends Graph {

Map keyToVertex;

private class Vertex {

T key;

List successors;

List predecessors;

Vertex(T key) {

this.key = key;

this.successors = new ArrayList();

this.predecessors = new ArrayList();

}

}

AdjacencyListGraph(Set keys) {

this.keyToVertex = new HashMap();

for (T key : keys) {

Vertex v = new Vertex(key);

this.keyToVertex.put(key, v);

}

}

@Override

public int size() {

return this.keyToVertex.size();

}

@Override

public int numEdges() {

int count = 0;

for (Vertex v : this.keyToVertex.values()) {

count += v.successors.size();

}

return count;

}

@Override

public boolean addEdge(T from, T to) {

if (!this.keyToVertex.containsKey(from)) {

throw new NoSuchElementException("Could not find vertex with key " + from.toString());

}

if (!this.keyToVertex.containsKey(to)) {

throw new NoSuchElementException("Could not find vertex with key " + to.toString());

}

Vertex fromV = this.keyToVertex.get(from);

Vertex toV = this.keyToVertex.get(to);

List fromSuccs = fromV.successors;

List toPreds = toV.predecessors;

if (fromSuccs.contains(toV)) {

return false;

}

fromSuccs.add(toV);

toPreds.add(fromV);

return true;

}

@Override

public boolean hasVertex(T key) {

return this.keyToVertex.containsKey(key);

}

@Override

public boolean hasEdge(T from, T to) throws NoSuchElementException {

if (!this.keyToVertex.containsKey(from)) {

throw new NoSuchElementException("Could not find vertex with key " + from.toString());

}

if (!this.keyToVertex.containsKey(to)) {

throw new NoSuchElementException("Could not find vertex with key " + to.toString());

}

Vertex fromV = this.keyToVertex.get(from);

Vertex toV = this.keyToVertex.get(to);

List fromSuccs = fromV.successors;

List toPreds = toV.predecessors;

if (fromSuccs.contains(toV)) {

return true;

}

return false;

}

@Override

public boolean removeEdge(T from, T to) throws NoSuchElementException {

if (!this.keyToVertex.containsKey(from)) {

throw new NoSuchElementException("Could not find vertex with key " + from.toString());

}

if (!this.keyToVertex.containsKey(to)) {

throw new NoSuchElementException("Could not find vertex with key " + to.toString());

}

Vertex fromV = this.keyToVertex.get(from);

Vertex toV = this.keyToVertex.get(to);

if (!this.hasEdge(from, to)) {

return false;

}

List fromSuccs = fromV.successors;

List toPreds = toV.predecessors;

fromSuccs.remove(toV);

toPreds.remove(fromV);

if (!fromSuccs.contains(toV)) {

return true;

}

return false;

}

@Override

public int outDegree(T key) {

return this.keyToVertex.get(key).successors.size();

}

@Override

public int inDegree(T key) {

return this.keyToVertex.get(key).predecessors.size();

}

@Override

public Set vertexSet() {

Set vertexSet = new HashSet();

for (T v : this.keyToVertex.keySet()) {

vertexSet.add(v);

}

return vertexSet;

}

@Override

public List successorList(T key) {

List successorList = new ArrayList();

for (Vertex v : this.keyToVertex.get(key).successors) {

successorList.add(v.key);

}

return successorList;

}

@Override

public List predecessorList(T key) {

List predecessorList = new ArrayList();

for (Vertex v : this.keyToVertex.get(key).predecessors) {

predecessorList.add(v.key);

}

return predecessorList;

}

@Override

public Iterator successorIterator(T key) {

return new theIterator(this.successorList(key));

}

@Override

public Iterator predecessorIterator(T key) {

return new theIterator(this.predecessorList(key));

}

private class theIterator implements Iterator {

List target;

int index = 0;

public theIterator(List theList) {

this.target = theList;

}

@Override

public boolean hasNext() {

return this.index < this.target.size();

}

@Override

public T next() {

if (hasNext()) {

this.index += 1;

return this.target.get(this.index - 1);

}

return null;

}

}

@Override

public Set stronglyConnectedComponent(T key) {

this.keyToVertex.get(key);

//TODO

return null;

}

@Override

public List shortestPath(T startLabel, T endLabel) {

// TODO

return null;

}

}