Articles by Thomas

CS331 was a fun class. Data structures are right up my ally. They take a simple concept and expand it to apply to scenarios in neat and interesting ways.  It was eight years ago when I took (and passed) that class…Yikes!

Most of the assignment, actually, 4 out of 5 assignments, were coded and turned in on time.  This was not a small feat.  In college, it was common for me to work a 30 hour week.  Getting assignments done was usually a balancing act of putting one thing on hold while moving on to another (such is life).  Four out of five is not all that bad.  So why did that one problem give me such an issue.  Why has there been a sour note in the melody that was a great collegiate career?  Because I said I would finish it, that’s why.

Java coding has been taking up a lot of my nights lately.  It’s fun again to write code; just like in college.  When thinking up of things to code, the memory of this assignment came to the front of my mind.  It was time.

After reviewing the C++ I had written 8 years ago, it was obvious that it was close to working.  There was just a piece or two missing.  Perhaps that is another reason why this had been stuck in my mind.   The other thing that was obvious is that I name my variables much better now.  Reading my old code was nothing less than a chore.  Writing code that someone else, not myself, can maintain is something that I took for granted then.  Of course, in college, it was cheating to work with someone else on a project .

The rules for the application

• The application will read input from a text file
• The application will use Dikjstra’s algorithm to find the shortest path between all reachable nodes in the graph

Here’s a short refresher on Dijkstra’s Algorithm from Wikipedia:

Let the node at which we are starting be called the initial node. Let the distance of node Y be the distance from the initial node to Y. Dijkstra’s algorithm will assign some initial distance values and will try to improve them step by step.

1. Assign to every node a distance value: set it to zero for our initial node and to infinity for all other nodes.
2. Mark all nodes as unvisited. Set initial node as current.
3. For current node, consider all its unvisited neighbors and calculate their tentative distance. For example, if current node (A) has distance of 6, and an edge connecting it with another node (B) is 2, the distance to B through A will be 6+2=8. If this distance is less than the previously recorded distance, overwrite the distance. All unvisited neighbors are added to an unvisited set.
4. When we are done considering all neighbors of the current node, mark it as visited. A visited node will not be checked ever again; its distance recorded now is final and minimal.
5. The next current node will be the node with the lowest distance in the unvisited set.
6. If all nodes have been visited, finish. Otherwise, set the unvisited node with the smallest distance (from the initial node, considering all nodes in graph) as the next “current node” and continue from step 3.

Design:

• There are two main objects in play, an Edge and a Node.  A Node is a destination and an Edge describes how to get there.
• To accomplish #5 above, a PriorityQueue is used.  It is a sorted Queue.
• There is another requirement that was part of the problem.  There are two types of graphs, one that has bi-directional nodes and one that has directional nodes.  Instead of creating two Edge objects with a source and a destination, I decided to make the Edge object less directional sounding.  It has a leftNode and a rightNode.  That way, in a directional graph, left is before right.  In a bi-directional graph the direction can be considered ambiguous.

Changes if this Were Production Code:

• The nodeId is used all over the place.  In order to make this code apply to more situations, the Id should be a generic type
• Better comments

What I Learned:

• HashMaps are very intuitive.  Give a key, get a value.
• If at first you don’t succeed…..but 8 years later… really?

The Code (Save all files to the same directory):
Save as Main.java

import java.io.BufferedReader;
import java.io.Console;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;

public class Main {

	//These would be in a Value Object if Object orientation was a concern
	Queue<Node> unsettledNodes = new PriorityQueue<Node>();
	Map<Integer,ArrayList<Edge>> edgeMapKeyedOnNodeId = new HashMap<Integer,ArrayList<Edge>>();
	Map<Integer,Node> nodeMap = new HashMap<Integer,Node>();
	String uOrD;

	Integer INFINITE_DISTANCE = Integer.MAX_VALUE;

	public static void main(String... args)
	{
		Integer choice = -1;
		while (choice != 0)
		{
			Console console = System.console();
			String input;
			if (console != null)
			{
				console.printf("Enter in the file number to open 1-3 or 0 to exit\n");
				input = console.readLine();
			}
			else
			{
				input = "3";
			}
			choice = Integer.parseInt(input);

			if(!choice.equals(0))
			{
				Main main = new Main();
				Integer numberOfNodes = main.readFileInput(choice);
				Integer startNodeId =  main.getStartNode(numberOfNodes);
				main.runDijkstra(startNodeId);
				main.printPaths();
			}

			if (console == null)
			{
				choice = 0;
			}
		}
	}

	/**
	 * Reads in the file and populates the graph variables
	 * @param fileNumber the number of the file to load from
	 * @return the number of nodes in the graph
	 */
	private Integer readFileInput(Integer fileNumber)
	{
		Integer numberOfNodes = 0;
		try
		{
			FileReader fr = new FileReader("edge_weights" + fileNumber);
			BufferedReader bfr = new BufferedReader(fr);

			numberOfNodes = Integer.parseInt(bfr.readLine());
			numberOfNodes --; // 0 base it for ease of use
			uOrD = bfr.readLine(); //Directed or Undirected
			String nodeLine;
			ArrayList<Edge> edgeList = null;

			while ((nodeLine = bfr.readLine()) != null)
			{
				Scanner scanner = new Scanner(nodeLine);
				Edge edge = new Edge();
				edge.setVertexLeft(scanner.nextInt());
				edgeList = edgeMapKeyedOnNodeId.get(edge.getVertexLeft());
				if (edgeList == null)
				{
					edgeList = new ArrayList<Edge>();
				}
				edge.setVertexRight(scanner.nextInt());
				edge.setWeight(scanner.nextInt());
				edgeList.add(edge);
				edgeMapKeyedOnNodeId.put(edge.getVertexLeft(), edgeList);
				if (uOrD.equals("U"))
				{
					//Add the same edge to the possible edges from the right vertex
					//The same edge object is put in the left and right maps when in unordered mode
					edgeList = edgeMapKeyedOnNodeId.get(edge.getVertexRight());
					if (edgeList == null)
					{
						edgeList = new ArrayList<Edge>();
					}
					edgeList.add(edge);
					edgeMapKeyedOnNodeId.put(edge.getVertexRight(), edgeList);
				}
			}
			bfr.close();
		}
		catch (FileNotFoundException e) {
			e.printStackTrace();
		} catch (IOException e) {
			e.printStackTrace();
		}

		return numberOfNodes;
	}

	/**
	 * Prompt the user for a start node
	 * @param numberOfNodes the number of nodes in the graph
	 * @return the start node the user entered
	 */
	public Integer getStartNode(Integer numberOfNodes)
	{
		Integer startNode = -1;
		Console console = System.console();

		while (startNode < 0 || startNode > numberOfNodes)
		{
			if (console != null)
			{
				console.printf("Enter a start node 0-" + numberOfNodes + "\n");
				startNode = Integer.parseInt(console.readLine());
			}
			else
			{
				startNode = 0;
			}
		}
		return startNode;
	}

	public void runDijkstra(Integer startNodeId)
	{
		Node node = new Node();
		node.setNodeId(startNodeId);
		node.setWeight(0);
		nodeMap.put(node.getNodeId(),node);	

		Integer totalComparisons = 0;
		while (node != null)
		{
			if (edgeMapKeyedOnNodeId.get(node.getNodeId()) != null)
			{
				for(Edge edge : edgeMapKeyedOnNodeId.get(node.getNodeId()))
				{
					Node nextDestination;
					Integer nextDestinationId = null;
					//If unordered the id of the next destination may be the right or the left vertex
					if (uOrD.equals("U"))
					{
						nextDestinationId = edge.getOppositeVertex(node.getNodeId());
					}
					else
					{
						//If ordered, the destination is always the right vertex
						nextDestinationId = edge.getVertexRight();
					}

					if (nodeMap.get(nextDestinationId) == null)
					{
						nextDestination = new Node();
						nextDestination.setNodeId(nextDestinationId);
						nextDestination.setWeight(INFINITE_DISTANCE);
					}
					else
					{
						nextDestination = nodeMap.get(nextDestinationId);
					}

					System.out.println("Calculating distance From " + node.getNodeId() + " To: " + nextDestination.getNodeId() + " Traversed: " + nextDestination.getTraversed());
					System.out.println("Current Node Distance: " + node.getWeight() + " Edge Weight: " + edge.getWeight() + " Against " + nextDestination.getWeight());

					if(!nextDestination.traversed)
					{
						totalComparisons ++;
						if(nextDestination.getWeight() > node.getWeight() + edge.weight)
						{
							System.out.println("Found a shorter path to " + nextDestination.getNodeId());

							nextDestination.setWeight(edge.weight + node.getWeight());
							nextDestination.setPredecessor(node);
							nodeMap.put(nextDestination.getNodeId(),nextDestination);
							unsettledNodes.offer(nextDestination);
						}
					}
				}
			}
			node.traversed = true;
			node = unsettledNodes.poll();
		}

		System.out.println("Total distance comparisons: " + totalComparisons);
	}

	/**
	 * Print out all of the paths to all of the possible destinations
	 */
	public void printPaths()
	{
		for(int i = 0; i<= nodeMap.size(); i++)
		{
			if (nodeMap.get(i) != null)
			{
				List<Node> shortestPath = getShortestPathTo(nodeMap.get(i));
				System.out.println("Shortest path to node index " + i);
				for (Node point : shortestPath)
				{
					System.out.println(point);
				}
			}
		}
	}

	/**
	 * Returns a list containing the nodes that are in the shortest path to the destination
	 * @param destinationNode
	 * @return
	 */
	public List<Node> getShortestPathTo(Node destinationNode)
	{
		List<Node> path = new ArrayList<Node>();
		for (Node lastNode = destinationNode; lastNode.getPredecessor() != null; lastNode = lastNode.getPredecessor())
		{
			path.add(lastNode);
		}

		Collections.reverse(path);
		return path;
	}

	/**
	 * This is the representation of an edge.  Note that is does not imply direction.
	 *
	 */
	class Edge
	{
		Integer vertexLeft;
		Integer vertexRight;
		Integer weight;
		public Integer getVertexLeft() {
			return vertexLeft;
		}
		public void setVertexLeft(Integer vertexLeft) {
			this.vertexLeft = vertexLeft;
		}
		public Integer getVertexRight() {
			return vertexRight;
		}
		public void setVertexRight(Integer vertexRight) {
			this.vertexRight = vertexRight;
		}
		public Integer getWeight() {
			return weight;
		}
		public void setWeight(Integer weight) {
			this.weight = weight;
		}
		@Override
		public String toString()
		{
			String stringed = "Left: " + vertexLeft + " Right: " + vertexRight + " Weight: " + weight;
			return stringed;
		}

		public Integer getOppositeVertex (Integer vertex)
		{
			Integer oppositeVertex = null;
			if (vertex.equals(vertexLeft))
			{
				oppositeVertex = vertexRight;
			}
			else
			{
				oppositeVertex = vertexLeft;
			}
			return oppositeVertex;
		}
	}

	/**
	 * This is a representation of a node on the graph
	 */
	class Node implements Comparable<Node>
	{
		Integer nodeId;
		Boolean traversed = false;
		Integer distanceFromStartNode = Integer.MAX_VALUE;
		Node predecessor;

		public Node getPredecessor() {
			return predecessor;
		}
		public void setPredecessor(Node predecessor) {
			this.predecessor = predecessor;
		}
		public Integer getNodeId() {
			return nodeId;
		}
		public void setNodeId(Integer vertexStart) {
			this.nodeId = vertexStart;
		}
		public Boolean getTraversed() {
			return traversed;
		}
		public void setTraversed(Boolean traversed) {
			this.traversed = traversed;
		}
		public Integer getWeight() {
			return distanceFromStartNode;
		}
		public void setWeight(Integer weight) {
			this.distanceFromStartNode = weight;
		}
		@Override
		public int compareTo(Node o) {
			return this.getWeight().compareTo(o.distanceFromStartNode);
		}
		@Override
		public String toString()
		{
			return ("Node Id:" + nodeId + " Weight: " + distanceFromStartNode);
		}
	}
}

Save as edge_weights1

6
U
0 1 800
0 2 2985
0 3 310
0 4 200
1 2 410
1 3 612
2 3 1421
3 4 400
1 5 100
5 4 100


Save as edge_weights2

5
D
1 0 800
2 0 2985
0 2 2985
0 3 310
4 0 200
1 2 410
2 1 410
3 1 612
1 3 612
2 3 1421
3 2 1421
3 4 400


Save as edge_weights3

10
U
1 0 3
2 1 17
2 3 2
8 9 1
0 7 2
8 0 13
7 8 10
7 6 5
6 8 4
5 6 3
4 5 15
4 9 12
3 9 9
2 9 6
4 3 3


Run (in the same directory as all of the files):

javac Main.java
java -cp . Main