dijkstra.java

DTNSim2 is a simulator for Delay-Tolerant Networks (DTNs) written in Java. It is based on Sushant Ja

package simulator;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Iterator;
import java.util.PriorityQueue;

/**
 * Performs shortest path routing on a time-varying multigraph. The graph object
 * is queried for all the information about the graph. Three types are required:
 * NodeType is the type used for nodes in the graph, ArcType is used for arcs in
 * the graph, and ContextType is used to have weights in the graph depend on
 * some external property (such as message length).
 */
public class Dijkstra<NodeType, ArcType, ContextType>
{
	private NodeType sourceNode;

	/** Stores the previous hop for each node. */
	private HashMap<NodeType, ArcType> predMatrix;

	/** The minimum cost to reach each node. */
	private HashMap<NodeType, Double> costMatrix = new HashMap<NodeType, Double>();

	/** The time the message will arrive at each node. */
	private HashMap<NodeType, Double> arrivalTimes = new HashMap<NodeType, Double>();

	/** The minimum number of hops to reach each current node. */
	private HashMap<NodeType, Integer> hopCount;

	private Graph<NodeType, ArcType, ContextType> graph = null;

	// this stores the reference to an object in view of which the graph G
	// weights will be computed
	private ContextType forObj;

	public ContextType context()
	{
		return forObj;
	}

	private PriorityQueue<NodeType> priQ = new PriorityQueue<NodeType>(11, new RouteComparator());

	private double startTime;

	public double getStartTime()
	{
		return startTime;
	}

	public String toString()
	{
		return "DIJKSTRA for " + sourceNode + ": PredM: " + predMatrix + "; CostM: " + costMatrix + "; HopC: "
				+ hopCount;
	}

	/**
	 * Returns the route from the source node to endPoint. The first link leaves
	 * from the source node, and the last link arrives at endPoint.
	 */
	public ArrayList<ArcType> routeTo(NodeType endPoint)
	{
		computeShortestPath(endPoint);

		int hops = getHopCount(endPoint);

		if (hops == Integer.MAX_VALUE)
			return null;

		// Create a new array to store the path
		ArrayList<ArcType> retval = new ArrayList<ArcType>(hops);

		// Fill it with nulls
		while (retval.size() < hops)
		{
			retval.add(null);
		}

		ArcType previousLink = predMatrix.get(endPoint);

		while (previousLink != null)
		{
			assert hops > 0;
			hops -= 1;
			retval.set(hops, previousLink);

			previousLink = predMatrix.get(graph.getSource(previousLink));
		}

		return retval;
	}

	/** Returns the cost to get from the source to dest. */
	public double getCost(NodeType dest)
	{
		Double f = costMatrix.get(dest);

		if (f == null)
			return Double.POSITIVE_INFINITY;

		return f;
	}

	private int getHopCount(NodeType dest)
	{
		Integer i = hopCount.get(dest);

		if (i == null)
			i = Integer.MAX_VALUE;

		return i;
	}

	private class RouteComparator implements Comparator<NodeType>
	{
		/** Compare the best paths to nodeA and nodeB. */
		public int compare(NodeType nodeA, NodeType nodeB)
		{
			double costA = getCost(nodeA);
			double costB = getCost(nodeB);

			if (costA < costB)
			{
				assert compare(nodeB, nodeA) > 0;
				return -1;
			}
			else if (costA > costB)
			{
				return 1;
			}
			else
			{
				// If the costs are equal, compare based on hop count
				assert costA == costB;

				int hopDiff = getHopCount(nodeA) - getHopCount(nodeB);

				if (hopDiff != 0)
					return hopDiff;

				assert hopDiff == 0;

				// If the two have the same cost, and the same number of hops,
				// then compare the two based on their ids. We
				// cannot use hashCodes because we need to
				// ensure repeatability.
				int idDiff = graph.compareNodes(nodeA, nodeB);

				assert idDiff != 0 || nodeA == nodeB;

				return idDiff;
			}
		}
	}

	public Dijkstra(Graph<NodeType, ArcType, ContextType> g, NodeType sNode, double sTime, ContextType fObject)
	{
		this.startTime = sTime;
		this.sourceNode = sNode;
		this.forObj = fObject;
		this.graph = g;

		assert g != null;

		predMatrix = new HashMap<NodeType, ArcType>();
		hopCount = new HashMap<NodeType, Integer>();

		// The initial cost at the start node is zero
		costMatrix.put(sourceNode, 0.0);

		// The initial arrival time is sTime
		arrivalTimes.put(sourceNode, sTime);

		// The hop count at the source is zero
		hopCount.put(sourceNode, new Integer(0));

		priQ.add(sNode);

		assert priQ.size() == 0 || priQ.peek() == sNode;
	}

	private void relax(ArcType link)
	{
		NodeType dest = graph.getDest(link);
		NodeType source = graph.getSource(link);

		// Compute the arrival time if we take this link
		double arrival = arrivalTimes.get(source);
		// We must have an arrival time recorded
		assert arrival < Double.POSITIVE_INFINITY;

		double pathCost = getCost(source);
		// We must have a cost recorded
		assert pathCost < Double.POSITIVE_INFINITY;

		pathCost += graph.getWeight(link, arrival, forObj);
		if (pathCost == Double.POSITIVE_INFINITY)
		{
			// There is no path available
			return;
		}

		// Compute the number of hops if we take this link
		int hops = getHopCount(source) + 1;
		// Don't handle overflow
		if (hops < 0)
			throw new RuntimeException("Integer overflow: Path is way way way too long");

		// If this path is better than the last computed best path, take it
		// It is better if the cost is less, or the cost is equal and the number
		// of hops is less
		if (pathCost < getCost(dest) || (pathCost == getCost(dest) && hops < getHopCount(dest)))
		{
			// Remove the item before changing its cost, which changes the sort
			// order. It is possible, that 'dest' is not in priQ yet.
			priQ.remove(dest);

			predMatrix.put(dest, link);
			costMatrix.put(dest, pathCost);
			double nextHopArrival = graph.getArrivalTime(link, arrival, forObj);
			assert nextHopArrival >= arrival;
			arrivalTimes.put(dest, nextHopArrival);
			hopCount.put(dest, hops);

			// Add the item back to the queue, in its new order
			priQ.add(dest);
		}
	}

	private void computeShortestPath(NodeType destination)
	{
		// If the destination is at the front of the queue, we have found
		// the shortest path to it: quit processing the queue
		while (priQ.size() > 0 && priQ.peek() != destination)
		{
			NodeType u = priQ.poll();

			for (Iterator<? extends ArcType> e = graph.getArcsOut(u); e.hasNext();)
			{
				ArcType link = e.next();
				assert u == graph.getSource(link);

				relax(link);
			}
		}
	}

	/**
	 * Graph which knows all about the network. Methods defined below just
	 * returns information obtained from certain objects (Nodes, Arcs), but one
	 * can extend it and return something completely different, based on some
	 * other topology (maybe incomplete?)
	 */
	public interface Graph<NodeType, ArcType, ContextType>
	{
		/**
		 * Returns an Iterator over all the arcs that leave leave 'fromNode'
		 * Node.
		 */
		public Iterator<? extends ArcType> getArcsOut(NodeType fromNode);

		/**
		 * Compares two nodes, the same way as a Comparator does. This is used
		 * to deterministically select a route when two paths have the same
		 * cost. This ensures that multiple simulator runs return the same
		 * results.
		 */
		public int compareNodes(NodeType a, NodeType b);

		/**
		 * Returns the cost for the context object to traverse the arc starting
		 * at time. It must be greater than or equal to zero.
		 */
		public double getWeight(ArcType arc, double time, ContextType context);

		/**
		 * Returns the time that the message will arrive at the other end of the
		 * arc. The same time will be passed back in to getWeight to route the
		 * next hop. This must return a value greater-than or equal-to time.
		 */
		public double getArrivalTime(ArcType arc, double time, ContextType context);

		/** Returns the source node for arc. */
		public NodeType getSource(ArcType arc);

		/** Returns the destination node for arc. */
		public NodeType getDest(ArcType arc);
	}
}