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.

The views and opinions expressed in this page are strictly those of the page author. The contents of this page have not been reviewed or approved by the University of Minnesota.