import java.util.*;
import java.io.*;
import java.lang.*;


public class Graph2<V,E> extends Object{

public ArrayList<Node> nodeList;
public ArrayList<Edge> edgeList;
/* Default Constructor
 *Intializes listV, the list of all the vertices in garph
 */
Graph2(){
	nodeList = new ArrayList<Node>();
	edgeList = new ArrayList<Edge>();


}

//accessor for the nodes list
public ArrayList<Node> getNodeList(){
	return nodeList;
}

//accessor for the edges list
public ArrayList<Edge> getEdgeList(){
	return edgeList;
}

/**
* @return the size of the nodes list in Graph
*/
public int getSizeNodeList(){
	return nodeList.size();
}

/**
* @return the size of the edge list in Graph
*/
public ArrayList<Edge> getSizeEdgeList(){
	return edgeList.size();
}



/**
* @return sizeE The number of edges in Graph21_
*/
public int getSizeE() {
	return sizeE;
}
/**
* add a new vertex with key k, allows no duplicates.
* @param  v Key of the vertex
* @param  e Element of the vertex
* @return true If successful; false otherwise(if duplicates found).
*/


//adds a new node and returns the new node to be added to the list of nodes
public Node addNode(V data){
Node newNode = new Node(data);
nodeList.add(newNode);
return newNode;
}

//deletes a node from the list of nodes
public void deleteNode(Node newNode){
Edge edge;
do{
edge = newNode.edgeReference().get(0);
deleteEdge(edge);
}
while(newNode.edgeReference().isEmpty() == false);
nodeList.remove(newNode);
}

//deletes an edge from the list of edges
public void deleteEdge(Edge edge){
	Node tail = edge.returnTail();
	Node head = edge.returnHead();
	tail.deleteEdgeReference(edge);
	head.deleteEdgeReference(edge);
	edgeList.remove(edge);
}



//accessor for the edge List
public Edge getEdge(int j){
	return edgeList.get(j);
}

//accessor for an edge
public Edge edgeReference(Node head, Node tail){
	return head.edgeTo(tail);
}

//accessor for the nodes List
public Node getNode(int j){
	return nodesList.get(j);

}





/**
* adds an edge, returns an edge, checks for data head and tail
*/
public Edge addEdge(E data, Node head, Node tail) {
		Edge edge = new Edge(data, head, tail);
		tail.addToEdgeList(edge);
		head.addToEdgeList(edge);
		edgeList.add(edge);
		return edge;
	}



//removes the edge with head, tail, and node
public void deleteEdge(Node head, node Tail){
	Edge edge = head.edgeTo(tail);
	deleteEdge(edge);
}


//gets the data from the node and edge and prints graph
public void printGraph(){
	for(Node newNode: nodeList){
		if(newNode.getAdjacentNodes(newNode).isEmpty()){
			System.out.println(newNode.returnData());
		}
	}
	for(Edge edge: edgeList){
		System.out.println(edge.returnData());
	}
}

//Edge class that creates an edge
public class Edge{

//initializes the value of the head
private Node head;

//initializes teh value of the tail
private Node tail;

//data for edge
private E data;

//accesses the head
public Node returnHead(){
	return head;
}

//accesses the tail
public Node returnTail(){
	return tail;
}

//accesses the data of the edge
public E returnData(){
	return data;
}

//constructor that creates an edge
Edge(E data, Node head, Node tail){
	this.tail=tail;
	this.head=head;
	this.data=data;
}

//fixes the data for the edge
public void fixData(E data){
	this.data=data;
}

public boolean equals(Object b){
	if(b.getClass().equals(Edge.class) == false){
		System.err.println("should be an edge");
		System.exit(-1);
	}
	Edge edge = (Edge)b;
	Node tail0 = this.tail;
	Node head0 = this.head;
	Node tail1= edge.tail;
	Node head1 = edge.head;
	if(tail0 == head1 && tail1 == head0){
		return true;
	}
	else if(tail1 == tail0 && head0 == head1){
		return true;
	}
	else{
		return false;
	}

}

//puts a node in the graph
public class Node{

	//list of edges that the nodes are related to
	public ArrayList<Edge> edgeReference;

	// initializes the value of the node
	private V data;

	//accessor for the edge reference
	public ArrayList<Edge> returnEdgeReference(){
		return edgeReference;
	}

	//accessor for the data
	public V returnData(){
		return data;
	}

	//fixes for the data for the node
	public void fixData(){
		this.data = data;
	}

	//adds to the edge list
	public void addToEdgeList(Edge edge){
	edgeReference.add(edge);
	}

	//deletes an edge reference
	public void deleteEdgeReference(Edge edge){
	edgeReference.remove(edge);
	}

	//returns an array list of the adjacent nodes
	public ArrayList<Node> getAdjacentNodes(Node newNode){
		ArrayList<Node> adjacentNodes = new ArrayList<Node>();
		for(Edge edge: edgeReference){
			if(edge.returnHead() == newNode){
				adjacentNodes.add(edge.returnTail());
			}
			else if(edge.returnTail() == newNode){
				adjacentNodes.add(edge.returnHead());
			}
		}
		return adjacentNodes;
	}

	//
	public Edge checkEdge(Node adjacentNode){
		Edge check = new Edge(null, this, adjacentNode);
		for(Edge edge: this.edgeReference){
			if(edge.equals(test)){
				return edge;
			}
		}
		if(this.isAdjacent(adjacentNode) == false){
			return null;
		}
		return null;
	}

	//returns either true or false depending on whether the node is adjacent to the node we are working with
	public boolean isAdjacent(Node newNode){
		ArrayList<Node> adjacentNodes = getAdjacentNodes(this);
		return adjacentNodes.contains(newNode);
	}


}




}
}
/*
public int getEdge(V v1, V v2){
	Node<V,E> source,target;
	source = getNode(v1);
		target = getNode(v2);
		for (Edge<V,E> tmp : source.adj) {
			if (tmp.target.isDuplicate(target)) {
				// return weight if edge found
				return tmp.weight;
			}
		}
		//if no edge is found.
		return -1;
	}
}
*/