Graphs

import static org.junit.Assert.*;

import org.junit.Test;

public class TestGraph {
	GraphAdjList<String,String> emptyGraph = new GraphAdjList<String,String>();
	
	public void setUp() {
		// http://www.air-ticket.us/airports/usa-airport-code.php
		// may be helpful for generating test cases
	}
	
	@Test
	public void TestEmpty(){
		assertTrue(emptyGraph.isEmpty());
		assertEquals(0,emptyGraph.numberVertices());
		assertEquals(0,emptyGraph.numberEdges());
	}
	
	@Test
	public void GetFromEmpty() {
		assertNull(emptyGraph.getValue("MSP"));
	}
	
	@Test
	public void TestOneVertex() {
		emptyGraph.addVertex("MSP", "Minneapolis/St.Paul, MN");
		assertFalse(emptyGraph.isEmpty());
		assertEquals(1,emptyGraph.numberVertices());
		assertEquals(0,emptyGraph.numberEdges());	
		assertEquals("Minneapolis/St.Paul, MN",emptyGraph.getValue("MSP"));
	}
	
	@Test (expected=NullPointerException.class)
	public void addNullKey() {
		emptyGraph.addVertex(null, "Minneapolis/St.Paul, MN");
	}
	
	@Test (expected=NullPointerException.class)
	public void getNullKey() {
		emptyGraph.getValue(null);
	}	
	
	@Test (expected=InvalidKeyException.class)
	public void TestDisallowRepeatedKeys() {
		emptyGraph.addVertex("MSP", "Minneapolis, MN");
		emptyGraph.addVertex("MSP", "St.Paul, MN");
	}
	
	@Test
	public void TestAddEdge() {
		emptyGraph.addVertex("MSP", "Minneapolis/St.Paul, MN");
		emptyGraph.addVertex("MIA", "Miami, FL");
		emptyGraph.addEdge("MSP","MIA",500);
		assertFalse(emptyGraph.isEmpty());
		assertEquals(2,emptyGraph.numberVertices());
		assertEquals(1,emptyGraph.numberEdges());	
		
	}
	
	@Test (expected=NullPointerException.class)
	public void TestAddEdgeNullKey() {
		emptyGraph.addVertex("MSP", "Minneapolis/St.Paul, MN");
		emptyGraph.addVertex("MIA", "Miami, FL");
		emptyGraph.addEdge(null,"MIA",500);
	}	
	
	@Test (expected=InvalidKeyException.class)
	public void TestAddEdgeNoSuchKey() {
		emptyGraph.addVertex("MSP", "Minneapolis/St.Paul, MN");
		emptyGraph.addVertex("MIA", "Miami, FL");
		emptyGraph.addEdge("MSP","NOSUCHKEY",500);
	}	
	
	@Test (expected=NegativeWeightException.class)
	public void TestNegativeWeight() {
		emptyGraph.addVertex("MSP", "Minneapolis/St.Paul, MN");
		emptyGraph.addVertex("MIA", "Miami, FL");
		emptyGraph.addEdge("MSP","MIA",-500);
	}	
	
	@Test
	public void TestGetEdgeWeight() {
		emptyGraph.addVertex("MSP", "Minneapolis/St.Paul, MN");
		emptyGraph.addVertex("MIA", "Miami, FL");
		emptyGraph.addEdge("MSP","MIA",500);
		assertEquals(500,emptyGraph.getEdgeWeight("MSP","MIA")); 
	}
	
	
	@Test
	public void TestMissingEdge() {
		emptyGraph.addVertex("MSP", "Minneapolis/St.Paul, MN");
		emptyGraph.addVertex("MIA", "Miami, FL");
		emptyGraph.addEdge("MSP","MIA",500);
		assertEquals(-1,emptyGraph.getEdgeWeight("MIA","MSP")); 
	}
	
}

import java.util.ArrayList;

/**
 * Graph implementation for CSci 2101 
 * The graph is weighted (edges have int weights).
 * It is implemented using adjacency lists.
 * Repeated edges between vertices are not allowed
 * 
 * @author Elena Machkasova
 *
 * @param <K> - vertex key type (searches on keys are implemented)
 * @param <V> - vertex value type
 */
public class GraphAdjList<K, V> {
	private ArrayList<Vertex> vertices = new ArrayList<Vertex>();
	private int numberEdges;
	
	/**
	 * @return true if the graph has no vertices and no edges,
	 * false otherwise
	 */
	public boolean isEmpty() {
		return vertices.isEmpty();
	}

	/**
	 * 
	 * @return the number of vertices in this graph
	 */
	public int numberVertices() {
		return vertices.size();
	}

	/**
	 * 
	 * @return the number of edges in this graph
	 */
	public int numberEdges() {
		// TODO Auto-generated method stub
		return 0;
	}
	/**
	 * Adds a vertex with a given key and value to a graph.
	 * The vertex is not connected to any vertices
	 *  
	 * @param key - the key of the new vertex
	 * @param value - the value of the new vertex
	 * @throws NullPointerException if the key is null
	 * @throws InvalidKeyException if the key is already used
	 */
	public void addVertex(K key, V value) {
		// TODO Auto-generated method stub
		
	}

	/**
	 * Returns the value associated with this key.
	 * If there are multiple vertices with this key, one of 
	 * the values is returned.
	 * 
	 * @param key - a key to search for
	 * @return - the value associated with this key.
	 * @throws NullPointerException if the key is null
	 */
	public V getValue(K key) {
		// TODO Auto-generated method stub
		return null;
	}

	/**
	 * Adds a directed edge between vertices with the two given keys (the
	 * two keys may be the same) and a given weight. 
	 * 
	 * @param key1 - the key of the starting vertex
	 * @param key2 - the key of the ending vertex
	 * @param weight - the weight of the edge
	 * 
	 * @throws NullPointerException if at least one of the keys is null
	 * @throws InvalidKeyException if at least one of the keys
	 * is not in the graph 
	 * @throws NegativeWeightException if the weight is negative
	 */
	public void addEdge(K key1, K key2, int weight) {
		// TODO Auto-generated method stub
		
	}

	/**
	 * Returns the weight at the edge between key1 and key2,
	 * -1 if the edge is not in the graph
	 * @param key1 - the key of the starting vertex
	 * @param key2 - the key of the ending vertex
	 * @return - the weight at the given edge or -1 if the 
	 * edge is not there.
	 */
	public int getEdgeWeight(K key1, K key2) {
		// TODO Auto-generated method stub
		return -1;
	}
	
	/**
	 * The method returns the graph vertices as key-value pairs
	 * using breadth-first search traversal starting at the 
	 * vertex with a given key. 
	 * @param key - the key of the starting vertex
	 * @return - the array list of vertices that it is 
	 * connected to via a sequence of directed edges, ordered
	 * according to the breadth-first search.
	 */
	public ArrayList<KVPair<K,V>> breadthFirstSearch(K key) {
		ArrayList<KVPair<K,V>> bfs = new ArrayList<KVPair<K,V>>();
		// hint: use a queue
		return bfs;
	}


	/**
	 * The method returns the graph vertices as key-value pairs
	 * using depth-first search traversal starting at the 
	 * vertex with a given key. 
	 * @param key - the key of the starting vertex
	 * @return - the array list of vertices that it is 
	 * connected to via a sequence of directed edges, ordered
	 * according to the depth-first search.
	 */
	public ArrayList<KVPair<K,V>> depthFirstSearch(K key) {
		ArrayList<KVPair<K,V>> dfs = new ArrayList<KVPair<K,V>>();
		// hint: use a stack
		return dfs;
	}
	

	/**
	 * Returns the sequence of keys in the shortest path from one vertex 
	 * to another and the total weight of this path (as an Integer).
	 * @param start - the key of the starting vertex
	 * @param finish - the key of the ending vertex
	 * @return - the sequence of keys in the shortest path from one vertex 
	 * to another and the total weight of this path (as an Integer).
	 */
	public KVPair<ArrayList<K>, Integer> shortestPath(K start, K finish) {
		ArrayList<K> shortestPath = new ArrayList<K>();
		// hint: use any Java Collections Framework structures
		// you find useful
		
		return new KVPair<ArrayList<K>, Integer>(shortestPath,Integer.MAX_VALUE);
	}
	
	private class Vertex {
		public final K key;
		public final V value;
		private ArrayList<Edge> adjList = new
				ArrayList<Edge>();
		
		public Vertex(K key, V value) {
			this.key = key;
			this.value = value;
		}
		
		public void addEdge(Vertex endpoint, int weight) {
			
		}
		
		public int getEdgeWeight(K endpoint) {
			// find endpoint in adjList, return its weight
			
			// if not found, return -1
			return -1;
		}
	}
	
	private class Edge {
		final public Vertex target;
		final public int weight;
		
		public Edge(Vertex target, int weight) {
			this.target = target;
			this.weight = weight;
		}
		
	}
	
}

public class InvalidKeyException extends RuntimeException {

}

public class NegativeWeightException extends RuntimeException {

}

/**
 * A class for storing key-value pairs generated during
 * traversals of a Binary Search Tree
 * mypair.key gives the key, mypair.value gives the value
 * 
 * @author Elena Machkasova
 *
 * @param <K> - key type 
 * @param <V> - value type 
 */

public class KVPair<K, V> {
	final public K key;
	final public V value;
	
	public KVPair(K key, V value) {
		this.key = key;
		this.value = value;
	}
	
	public boolean equals(Object other) {
		if (! (other instanceof KVPair)) return false;
		KVPair<K,V> otherPair = (KVPair<K,V>) other;
		return (key.equals(otherPair.key) && value.equals(otherPair.value));
	}
}

CSci 2101 course web site.