ScheduleDijkstra.java

/* 
 * Copyright 2010 Aalto University, ComNet
 * Released under GPLv3. See LICENSE.txt for details. 
 */

package routing.schedule;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Set;

/**
 * Dijkstra's shortest path implementation for schedule data
 */
/* TODO: combine this with movement.map.DijkstraPathFinder? */
public class ScheduleDijkstra {
	/** Value for infinite distance  */
	private static final Double INFINITY = Double.MAX_VALUE;
	/** Initial size of the priority queue */
	private static final int PQ_INIT_SIZE = 11;

	/** Map of the times when one could be at certain node */
	private TimeMap times;
	/** Set of already visited nodes (where the shortest path is known) */
	private Set<Integer> visited;
	/** Priority queue of unvisited nodes discovered so far */
	private Queue<Integer> unvisited;
	/** Map of previous schedule on the shortest path(s) */
	private Map<Integer, ScheduleEntry> prevHops;
	/** Oracle that know all schedules */
	private ScheduleOracle oracle;
	
	/**
	 * Constructor.
	 * @param oracle The schedule oracle
	 * all nodes are OK
	 */
	public ScheduleDijkstra(ScheduleOracle oracle) {
		this.oracle = oracle;
	}

	/**
	 * Initializes a new search with a source node
	 * @param node The path's source node
	 * @param time The time when the path starts
	 */
	private void initWith(Integer node, double time) {	
		this.unvisited = new PriorityQueue<Integer>(PQ_INIT_SIZE, 
				new DurationComparator());
		this.visited = new HashSet<Integer>();
		this.prevHops = new HashMap<Integer, ScheduleEntry>();
		this.times = new TimeMap();
		
		this.times.put(node, time);
		this.unvisited.add(node);
	}
	
	/**
	 * Finds and returns the fastest path between two destinations
	 * @param from The source of the path
	 * @param to The destination of the path
	 * @param time The time when the path starts
	 * @return a shortest path between the source and destination nodes in
	 * a list of Integers or an empty list if such path is not available
	 */
	public List<ScheduleEntry> getShortestPath(Integer from, Integer to, 
			double time){
		List<ScheduleEntry> path = new ArrayList<ScheduleEntry>();		
		assert time >= 0.0 : "Can't use negative start time";
		
		if (from.compareTo(to) == 0) { 
			return path;
		}
		
		initWith(from, time);
		Integer node = null;
		
		while ((node = unvisited.poll()) != null) {
			if (node.equals(to)) {
				break; 
			}
			
			visited.add(node); 
			relax(node); 
		}		

		if (node != null) { // found a path
			ScheduleEntry prev = prevHops.get(to); 
			while (prev.getFrom() != from) { 
				path.add(0, prev);
				prev = prevHops.get(prev.getFrom());
			}
			
			path.add(0, prev);
		}
		
		return path;
	}
	
	/**
	 * Relaxes the neighbors of a node (updates the shortest distances).
	 * @param node The node whose neighbors are relaxed
	 */
	private void relax(Integer node) {
		double timeNow = times.get(node);
		int to;
		double timeTo;
		
		for (ScheduleEntry se : oracle.getConnected(node, timeNow)) {
			to = se.getTo();
			if (visited.contains(to)) {
				continue; // skip visited nodes
			}
			
			timeTo = se.getTime() +  se.getDuration();
			
			if (timeTo < times.get(to)) {
				prevHops.put(to, se);
				setTime(to, timeTo);
			}
		}
	}
	
	/**
	 * Sets the time when at a node
	 * @param n The node whose time is set
	 * @param time The time when at given node
	 */
	private void setTime(Integer n, double time) {
		unvisited.remove(n);
		times.put(n, time); 
		unvisited.add(n);
	}
	
	/**
	 * Comparator that compares two nodes by their journey duration
	 */
	private class DurationComparator implements Comparator<Integer> {
		
		/**
		 * Compares two nodes by their time to get there 
		 * @return -1, 0 or 1 if node1's time is smaller, equal to, or
		 * bigger than node2's
		 */
		public int compare(Integer node1, Integer node2) {
			double time1 = times.get(node1);
			double time2 = times.get(node2);
			
			if (time1 > time2) {
				return 1;
			}
			else if (time1 < time2) {
				return -1;
			}
			else {
				return 0;
			}
		}
	}
	
	private class TimeMap {
		private HashMap<Integer, Double> map;
		
		/**
		 * Constructor. Creates an empty map
		 */
		public TimeMap() {
			this.map = new HashMap<Integer, Double>(); 
		}
		
		/**
		 * Returns the currently known smallest time one has a path for to the
		 * given node. If no time value is found, returns 
		 * {@link ScheduleDijkstra#INFINITY} as the value.
		 * @param node The node whose time is requested
		 * @return The time when one could be at that node
		 */
		public double get(Integer node) {
			Double value = map.get(node);
			if (value != null) {
				return value;
			}
			else {
				return INFINITY;
			}
		}
		
		/**
		 * Puts a new time value for a node
		 * @param node The node
		 * @param time Time at that node
		 */
		public void put(Integer node, double time) {
			map.put(node, time);
		}
		
		/**
		 * Returns a string representation of the map's contents
		 * @return a string representation of the map's contents
		 */
		public String toString() {
			return map.toString();
		}
	}
}