MapEdge.java

package roadgraph;

import geography.GeographicPoint;

public class MapEdge {
	
	private GeographicPoint start, end;
	private String roadName, roadType;
	private double distance;
	
	/**
	 * Create a new Map edge
	 * @param start - this is the starting location
	 * @param end - this is the ending location
	 * @param roadName - this is the name of the road
	 * @param roadType - this is the type of the road
	 * @param distance - this is the length of the edge
	 */
	public MapEdge(GeographicPoint start, GeographicPoint end, String roadName, String roadType, double distance) {
		this.start = start;
		this.end = end;
		this.roadName = roadName;
		this.roadType = roadType;
		this.distance = distance;
	}
	
	/**
	 * Get the geographic location of start point of the edge
	 * @return the start location
	 */
	public GeographicPoint getStart() {
		return start;
	}

	/**
	 * Get the geographic location of end point of the edge
	 * @return the end location
	 */
	public GeographicPoint getEnd() {
		return end;
	}

	/**
	 * Get the name of the road of the edge
	 * @return the road name
	 */
	public String getRoadName() {
		return roadName;
	}
	
	/**
	 * Get the type of the road of the edge
	 * @return the road type
	 */
	public String getRoadType() {
		return roadType;
	}

	/**
	 * Get the length of the edge
	 * @return the distance
	 */
	public double getDistance() {
		return distance;
	}
	
	/**
	 * Return a String representation for this edge.
	 */
	@Override
	public String toString()
	{
		String toReturn = "[EDGE between ";
		toReturn += "\n\t" + start;
		toReturn += "\n\t" + end;
		toReturn += "\nRoad name: " + roadName + " Road type: " + roadType +
				" Segment length: " + String.format("%.3g", distance) + "km";
		
		return toReturn;
	}

}

MapGraph.java

/**
 * @author UCSD MOOC development team and YOU
 * 
 * A class which reprsents a graph of geographic locations
 * Nodes in the graph are intersections between 
 *
 */
package roadgraph;


import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.HashMap;
import java.util.List;
import java.util.Set;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.function.Consumer;

import geography.GeographicPoint;
import util.GraphLoader;

/**
 * @author UCSD MOOC development team and YOU
 * 
 * A class which represents a graph of geographic locations
 * Nodes in the graph are intersections between 
 *
 */
public class MapGraph {
	private Map<GeographicPoint, MapVertex> vertices;
	private int numEdges;
	/** 
	 * Create a new empty MapGraph 
	 */
	public MapGraph()
	{
		vertices = new HashMap<>();
		numEdges = 0;
	}
	
	/**
	 * Get the number of vertices (road intersections) in the graph
	 * @return The number of vertices in the graph.
	 */
	public int getNumVertices()
	{
		return vertices.keySet().size();
	}
	
	/**
	 * Return the intersections, which are the vertices in this graph.
	 * @return The vertices in this graph as GeographicPoints
	 */
	public Set<GeographicPoint> getVertices()
	{
		return new HashSet<>(vertices.keySet()); // so that internal keySet is not exposed
	}
	
	/**
	 * Get the number of road segments in the graph
	 * @return The number of edges in the graph.
	 */
	public int getNumEdges()
	{
		return numEdges;
	}

	
	
	/** Add a node corresponding to an intersection at a Geographic Point
	 * If the location is already in the graph or null, this method does 
	 * not change the graph.
	 * @param location  The location of the intersection
	 * @return true if a node was added, false if it was not (the node
	 * was already in the graph, or the parameter is null).
	 */
	public boolean addVertex(GeographicPoint location)
	{
		if (location == null || vertices.containsKey(location))
			return false;
		vertices.put(location, new MapVertex(location));
		return true;
	}
	
	/**
	 * Adds a directed edge to the graph from pt1 to pt2.  
	 * Precondition: Both GeographicPoints have already been added to the graph
	 * @param from The starting point of the edge
	 * @param to The ending point of the edge
	 * @param roadName The name of the road
	 * @param roadType The type of the road
	 * @param length The length of the road, in km
	 * @throws IllegalArgumentException If the points have not already been
	 *   added as nodes to the graph, if any of the arguments is null,
	 *   or if the length is less than 0.
	 */
	public void addEdge(GeographicPoint from, GeographicPoint to, String roadName,
			String roadType, double length) throws IllegalArgumentException {
		
		if(length < 0 || !vertices.containsKey(from) || !vertices.containsKey(to))
			throw new IllegalArgumentException();
		
		vertices.get(from).addEdge(to, roadName, roadType, length);
		numEdges++;
	}
	

	/** Find the path from start to goal using breadth first search
	 * 
	 * @param start The starting location
	 * @param goal The goal location
	 * @return The list of intersections that form the shortest (unweighted)
	 *   path from start to goal (including both start and goal).
	 */
	public List<GeographicPoint> bfs(GeographicPoint start, GeographicPoint goal) {
		// Dummy variable for calling the search algorithms
        Consumer<GeographicPoint> temp = (x) -> {};
        return bfs(start, goal, temp);
	}
	
	/** Find the path from start to goal using breadth first search
	 * 
	 * @param start The starting location
	 * @param goal The goal location
	 * @param nodeSearched A hook for visualization.
	 * @return The list of intersections that form the shortest (unweighted)
	 *   path from start to goal (including both start and goal).
	 */
	public List<GeographicPoint> bfs(GeographicPoint start, 
			 					     GeographicPoint goal, Consumer<GeographicPoint> nodeSearched){
		Queue<MapVertex> queue = new LinkedList<>();
		return findPath(start, goal, nodeSearched, queue, 'B');
	}
	
	/** Find whether path from start to goal exists
	 * 
	 * @param start The starting location
	 * @param goal The goal location
	 * @param nodeSearched A hook for visualization
	 * @param queue LinkedList for BFS, PriorityQueue for Djikstra's and A*
	 * @param mode 'D' for Dijkstra 'A' for A* and 'B' for BFS
	 * @return The list of intersections that form the shortest
	 *   path from start to goal (including both start and goal).
	 */
	private List<GeographicPoint> findPath(GeographicPoint start, GeographicPoint goal, Consumer<GeographicPoint> nodeSearched, 
											Queue<MapVertex> queue, char mode) {
		
		//Creation
		Set<MapVertex> visited = new HashSet<>();
		Map<MapVertex, MapVertex> parentMap = new HashMap<>();
		MapVertex startVertex = vertices.get(start);
		MapVertex goalVertex = vertices.get(goal);
		
		//Initialization
		initializeFindTools(startVertex, queue, visited, mode);
		
		while(!queue.isEmpty()) {
			MapVertex currentVertex = queue.remove();
			
			if(mode == 'B' || !visited.contains(currentVertex)) { // this check is irrelevant for BFS and necessary for A*/Dijkstra's
				
				nodeSearched.accept(currentVertex.getLocation());
				visited.add(currentVertex);
				
				if(currentVertex.equals(goalVertex)) // path found
					return constructPath(parentMap, startVertex, goalVertex);
					
				for(MapEdge edge: currentVertex.getEdges()) {
					MapVertex nextVertex = vertices.get(edge.getEnd());
					if(!visited.contains(nextVertex) && (mode == 'B' || isUpdateDist(currentVertex, nextVertex, goalVertex, edge.getDistance(), mode))) {
						updateFindTools(currentVertex, nextVertex, queue, visited, parentMap, mode);
					}
				}
			}
		}
		
		return null; // no path found
	}
	/** Helper method to initialize queue and visited
	 * 
	 * @param startVertex The starting vertex
	 * @param queue LinkedList for BFS, PriorityQueue for Djikstra's and A*
	 * @param visited Set of visited nodes
	 * @param mode 'D' for Dijkstra 'A' for A* and 'B' for BFS
	 */
	private void initializeFindTools(MapVertex startVertex, Queue<MapVertex> queue, Set<MapVertex> visited, char mode) {
		startVertex.setActualDist(0); // for Djikstra's
		startVertex.setPredictedDist(0); // for A*
		if(mode == 'B')
			visited.add(startVertex);
		queue.add(startVertex);
	}
	
	/** Helper method to update queue, visited and parentMap
	 * 
	 * @param startVertex The starting vertex
	 * @param nextVertex The neighboring vertex of startVertex
	 * @param queue LinkedList for BFS, PriorityQueue for Djikstra's and A*
	 * @param visited Set of visited nodes
	 * @param parentMap The map linking a vertex to its parent
	 * @param mode 'D' for Dijkstra 'A' for A* and 'B' for BFS
	 */
	private void updateFindTools(MapVertex currentVertex, MapVertex nextVertex, Queue<MapVertex> queue, Set<MapVertex> visited, Map<MapVertex, MapVertex> parentMap, char mode) {
		queue.add(nextVertex);
		parentMap.put(nextVertex, currentVertex);
		if(mode == 'B')
			visited.add(nextVertex);
	}
	
	/** Construct path from start to goal using parentMap
	 * 
	 * @param parentMap The map mapping vertex to its parent
	 * @param start The starting vertex
	 * @param goal The goal vertex
	 * @return The list of intersections that form the shortest
	 *   path from start to goal (including both start and goal).
	 */
	private List<GeographicPoint> constructPath(Map<MapVertex, MapVertex> parentMap,
												MapVertex start, MapVertex goal){
		
		LinkedList<GeographicPoint> path = new LinkedList<>(); // LinkedList enables efficiently adding at head
		MapVertex cur = goal;
		while(cur != start) {
			path.addFirst(cur.getLocation());
			cur = parentMap.get(cur);
		}
		path.addFirst(start.getLocation());
		return path;
	}
	

	/** Find the path from start to goal using Dijkstra's algorithm
	 * 
	 * @param start The starting location
	 * @param goal The goal location
	 * @return The list of intersections that form the shortest path from 
	 *   start to goal (including both start and goal).
	 */
	public List<GeographicPoint> dijkstra(GeographicPoint start, GeographicPoint goal) {
		// Dummy variable for calling the search algorithms
		// You do not need to change this method.
        Consumer<GeographicPoint> temp = (x) -> {};
        return dijkstra(start, goal, temp);
	}
	
	/** Find the path from start to goal using Dijkstra's algorithm
	 * 
	 * @param start The starting location
	 * @param goal The goal location
	 * @param nodeSearched A hook for visualization.  See assignment instructions for how to use it.
	 * @return The list of intersections that form the shortest path from 
	 *   start to goal (including both start and goal).
	 */
	public List<GeographicPoint> dijkstra(GeographicPoint start, 
										  GeographicPoint goal, Consumer<GeographicPoint> nodeSearched)
	{
		// Note: actualDists are already initialized to infinity when graph is initialized
		Queue<MapVertex> queue = new PriorityQueue<MapVertex>((a,b) -> Double.compare(a.getActualDist(), b.getActualDist()));
		return findPath(start, goal, nodeSearched, queue, 'D');
	}

	/** Find whether distance of vertex should be updated, and update it if it should
	 * 
	 * @param start The starting vertex
	 * @param next The neighboring vertex of start
	 * @param goal The goal vertex
	 * @param edgeDistance The distance between start and next
	 * @param mode 'D' for Dijkstra and 'A' for A*
	 * @return true if distance is updated
	 */
	private boolean isUpdateDist(MapVertex current, MapVertex next, MapVertex goal, double edgeDistance, char mode) {
		if(mode == 'D') {
			double distFromStart = current.getActualDist() + edgeDistance;
			if (distFromStart < next.getActualDist()) {
				next.setActualDist(distFromStart);
				return true;
			}
		}
		else if (mode == 'A') {
			double distFromStart = current.getActualDist() + edgeDistance;
			double distToGoal = distFromStart + next.getLocation().distance(goal.getLocation());
			if (distToGoal < next.getPredictedDist()) {
				next.setActualDist(distFromStart);
				next.setPredictedDist(distToGoal);
				return true;
			}
		}
		return false;
	}

	/** Find the path from start to goal using A-Star search
	 * 
	 * @param start The starting location
	 * @param goal The goal location
	 * @return The list of intersections that form the shortest path from 
	 *   start to goal (including both start and goal).
	 */
	public List<GeographicPoint> aStarSearch(GeographicPoint start, GeographicPoint goal) {
		// Dummy variable for calling the search algorithms
        Consumer<GeographicPoint> temp = (x) -> {};
        return aStarSearch(start, goal, temp);
	}
	
	/** Find the path from start to goal using A-Star search
	 * 
	 * @param start The starting location
	 * @param goal The goal location
	 * @param nodeSearched A hook for visualization.  See assignment instructions for how to use it.
	 * @return The list of intersections that form the shortest path from 
	 *   start to goal (including both start and goal).
	 */
	public List<GeographicPoint> aStarSearch(GeographicPoint start, 
											 GeographicPoint goal, Consumer<GeographicPoint> nodeSearched)
	{
		// Note: actualDists and predictedDists are already initialized to infinity when graph is initialized
		Queue<MapVertex> queue = new PriorityQueue<MapVertex>((a,b) -> Double.compare(a.getPredictedDist(), b.getPredictedDist()));
		return findPath(start, goal, nodeSearched, queue, 'A');
	}

	
	
	public static void main(String[] args)
	{
		
		System.out.print("Making a new map...");
		MapGraph firstMap = new MapGraph();
		System.out.print("DONE. \nLoading the map...");
		GraphLoader.loadRoadMap("data/testdata/simpletest.map", firstMap);
		System.out.println("DONE.");
		GeographicPoint testStart = new GeographicPoint(7.0, 3.0);
		GeographicPoint testEnd = new GeographicPoint(4.0, -1.0);
		System.out.println(firstMap.bfs(testStart, testEnd));
		System.out.println(firstMap.getNumEdges());
		System.out.println(firstMap.getNumVertices());
		System.out.println(firstMap.getVertices());
		//List<GeographicPoint> x = firstMap.dijkstra(testStart, testEnd);
		//System.out.println(x);
		List<GeographicPoint> x = firstMap.aStarSearch(testStart, testEnd);
		System.out.println(x);
		
		
		
		/*
		MapGraph testMap = new MapGraph();
		GraphLoader.loadRoadMap("data/maps/utc.map", testMap);
		
		// A very simple test using real data
		GeographicPoint testStart = new GeographicPoint(32.8674388, -117.2190213);
		GeographicPoint testEnd = new GeographicPoint(32.8697828, -117.2244506);
		
		System.out.println("Test 3 using utc: Dijkstra should be 37 and AStar should be 10");
		testMap.dijkstra(testStart,testEnd);
		*/
		
		/*
		MapGraph testMap = new MapGraph();
		GraphLoader.loadRoadMap("data/maps/utc.map", testMap);
		
		// A very simple test using real data
		GeographicPoint testStart = new GeographicPoint(32.869423, -117.220917);
		GeographicPoint testEnd = new GeographicPoint(32.869255, -117.216927);
		System.out.println("Test 2 using utc: Dijkstra should be 13 and AStar should be 5");
		List<GeographicPoint> testroute2 = testMap.aStarSearch(testStart,testEnd);
		*/
		/*
		// A slightly more complex test using real data
		testStart = new GeographicPoint(32.8674388, -117.2190213);
		testEnd = new GeographicPoint(32.8697828, -117.2244506);
		System.out.println("Test 3 using utc: Dijkstra should be 37 and AStar should be 10");
		
		testMap = new MapGraph();
		GraphLoader.loadRoadMap("data/maps/utc.map", testMap);
		testroute = testMap.dijkstra(testStart,testEnd);
		
		testMap = new MapGraph();
		GraphLoader.loadRoadMap("data/maps/utc.map", testMap);
		testroute2 = testMap.aStarSearch(testStart,testEnd);
		*/
		/*
		MapGraph testMap = new MapGraph();
		GraphLoader.loadRoadMap("data/maps/utc.map", testMap);
		testStart = new GeographicPoint(32.8674388, -117.2190213);
		testEnd = new GeographicPoint(32.8697828, -117.2244506);
		System.out.println("Test 3 using utc: Dijkstra should be 37 and AStar should be 10");
		testMap.dijkstra(testStart,testEnd);
		testMap.aStarSearch(testStart,testEnd);
		*/
		/* Use this code in Week 3 End of Week Quiz */
		/*MapGraph theMap = new MapGraph();
		System.out.print("DONE. \nLoading the map...");
		GraphLoader.loadRoadMap("data/maps/utc.map", theMap);
		System.out.println("DONE.");

		GeographicPoint start = new GeographicPoint(32.8648772, -117.2254046);
		GeographicPoint end = new GeographicPoint(32.8660691, -117.217393);
		
		
		List<GeographicPoint> route = theMap.dijkstra(start,end);
		List<GeographicPoint> route2 = theMap.aStarSearch(start,end);
		
		// You can use this method for testing.  
		
		
		/* Here are some test cases you should try before you attempt 
		 * the Week 3 End of Week Quiz, EVEN IF you score 100% on the 
		 * programming assignment.
		 */
		/*
		MapGraph simpleTestMap = new MapGraph();
		GraphLoader.loadRoadMap("data/testdata/simpletest.map", simpleTestMap);
		
		GeographicPoint testStart = new GeographicPoint(1.0, 1.0);
		GeographicPoint testEnd = new GeographicPoint(8.0, -1.0);
		
		System.out.println("Test 1 using simpletest: Dijkstra should be 9 and AStar should be 5");
		List<GeographicPoint> testroute = simpleTestMap.dijkstra(testStart,testEnd);
		List<GeographicPoint> testroute2 = simpleTestMap.aStarSearch(testStart,testEnd);
		
		
		MapGraph testMap = new MapGraph();
		GraphLoader.loadRoadMap("data/maps/utc.map", testMap);
		
		// A very simple test using real data
		testStart = new GeographicPoint(32.869423, -117.220917);
		testEnd = new GeographicPoint(32.869255, -117.216927);
		System.out.println("Test 2 using utc: Dijkstra should be 13 and AStar should be 5");
		testroute = testMap.dijkstra(testStart,testEnd);
		testroute2 = testMap.aStarSearch(testStart,testEnd);
		
		
		// A slightly more complex test using real data
		testStart = new GeographicPoint(32.8674388, -117.2190213);
		testEnd = new GeographicPoint(32.8697828, -117.2244506);
		System.out.println("Test 3 using utc: Dijkstra should be 37 and AStar should be 10");
		testroute = testMap.dijkstra(testStart,testEnd);
		testroute2 = testMap.aStarSearch(testStart,testEnd);
		*/
		
		
		/* Use this code in Week 3 End of Week Quiz */
		/*MapGraph theMap = new MapGraph();
		System.out.print("DONE. \nLoading the map...");
		GraphLoader.loadRoadMap("data/maps/utc.map", theMap);
		System.out.println("DONE.");

		GeographicPoint start = new GeographicPoint(32.8648772, -117.2254046);
		GeographicPoint end = new GeographicPoint(32.8660691, -117.217393);
		
		
		List<GeographicPoint> route = theMap.dijkstra(start,end);
		List<GeographicPoint> route2 = theMap.aStarSearch(start,end);

		*/
		
	}
	
}

MapVertex.java

package roadgraph;

import java.util.List;
import java.util.ArrayList;
import geography.GeographicPoint;

/**
 * @author ME
 *
 */
public class MapVertex {
	private GeographicPoint location;
	private List<MapEdge> edges;
	private double actualDist; // actual distance from starting point to current vertex
	private double predictedDist; // predicted distance from starting point to goal vertex

	/**
	 * Create a new Map vertex
	 * @param location - this is the location of the vertex
	 */
	public MapVertex(GeographicPoint location) {
		this.location = location;
		edges = new ArrayList<>();
		actualDist = Double.MAX_VALUE;
		predictedDist = Double.MAX_VALUE;
	}

	/**
	 * Get the geographic location of the vertex
	 * @return the vertex location
	 */
	public GeographicPoint getLocation() {
		return location;
	}

	/**
	 * Get the edges originating from the vertex
	 * @return the adjacency list of edges of the vertex
	 */
	public List<MapEdge> getEdges() {
		return new ArrayList<>(edges);
	}
	
	/**
	 * Add an edge to the vertex
	 * @param to - End point of edge
	 * @param roadName - Name of the road
	 * @param roadType - Type of the road
	 * @param length - Length of the edge
	 */
	public void addEdge(GeographicPoint to, String roadName,
			String roadType, double length){
		
		MapEdge edge = new MapEdge(this.location, to, roadName, roadType, length);
		edges.add(edge);
	}

	@Override
	public int hashCode() {
		final int prime = 31;
		int result = 1;
		result = prime * result + ((location == null) ? 0 : location.hashCode());
		return result;
	}

	@Override
	public boolean equals(Object obj) {
		if (this == obj)
			return true;
		if (!(obj instanceof MapVertex))
			return false;
		MapVertex other = (MapVertex) obj;
		if (location == null) {
			if (other.location != null)
				return false;
		} else if (!location.equals(other.location))
			return false;
		return true;
	}
	
	/** ToString to print out a MapNode object
	 *  @return the string representation of a MapNode
	 */
	@Override
	public String toString()
	{
		/*
		String toReturn = "[NODE at location (" + location + ")";
		toReturn += " intersects streets: ";
		for (MapEdge e: edges) {
			toReturn += e.getRoadName() + ", ";
		}
		toReturn += "]";
		return toReturn;
		*/
		String toReturn = "[NODE at location (" + location + ") ";
		toReturn += actualDist + " " + predictedDist;

		return toReturn;
	}
	
	// For debugging, output roadNames as a String.
	public String roadNamesAsString()
	{
		String toReturn = "(";
		for (MapEdge e: edges) {
			toReturn += e.getRoadName() + ", ";
		}
		toReturn += ")";
		return toReturn;
	}

	/**
	 * @return the actualDist
	 */
	public double getActualDist() {
		return actualDist;
	}

	/**
	 * @param actualDist the actualDist to set
	 */
	public void setActualDist(double actualDist) {
		this.actualDist = actualDist;
	}

	/**
	 * @return the predictedDist
	 */
	public double getPredictedDist() {
		return predictedDist;
	}

	/**
	 * @param predictedDist the predictedDist to set
	 */
	public void setPredictedDist(double predictedDist) {
		this.predictedDist = predictedDist;
	}
	
}