June 2011

You are currently browsing the monthly archive for June 2011.

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

Tags:

It has been a while since running became a hobby. About a year now. Along the way, I’ve been setting up goals for myself to meet or exceed. This particular one was the most ambitious this far. On May 14, 2011, I accomplished this goal.

The decision to go for this goal was due to a compromise. A 5k was seeming too short and a marathon too long. A 25k seemed like a good compromise for a newbie runner like myself. I work with who have run the race before and gave me positive reviews. I would like to echo them and say that if you’re considering the race, it is quite a rewarding experience.

The under two hours part of the goal was more of a personal decision. If I’m doing this, I’m doing it good. There is also special recognition for those who are able to beat the 2 hour mark. If I run next year, I get a bib that acknowledges the achievement. I also knew what shape I was in. A goal of 2 hours would mean that a lot of work would be required; it was going to be tough.

Like most things, the preparation was 90% of the race. On the Riverbank Run’s website there is a training schedule that I tried to follow. Because of my lofty goals, I decided to follow the expert running schedule. At the peak of training, I was running for 45-50 miles a week.

The time commitment was larger than expected. Most of my Saturday was spent recovering from a 12-15 mile run. This gets especially rough when your wife decided to throw a surprise birthday party involving 70 people and indoor rock climbing. 🙂 The time it takes doesn’t just count time spent on the road. There is time to stretch, time to dress, time to clean, and time to recover. Looking back at it, I’m glad that I opted for a distance shorter than a marathon.

On raceday, I was buzzing. The weather was perfect for a long run. Out of the gate, the wind was at my back. The first 8 miles were fast. Probably a little too fast. Around mile 11, we had turned back, the wind was against us, my times began to slow down. Along the side of the road, there were people, lots of them towards the last two miles. There were people from the community, cheerleader squads, and military service members. I, of course, didn’t take water from the service members, but gave them some applause as I ran by. They had already given enough.

It was due to the people who were cheering and the volunteers that I kept pushing. There was some slack in my goal time, but why not do better? I finished strong, going uphill, with people cheering all over.

*Splits*
Mile: Pace in Minutes per Mile
1: 7.11 — Watch lost my position during this time. This distance isn’t totally accurate
2: 7:20
3: 7:21
4: 7:26
5: 7:15 — Passed the 7:30 pace guy here
6: 7:21
7: 7:17
8: 7:21
9: 7:36 — Switched back and lost the wind. Also a bit more hilly
10: 7:41
11: 7:35
12: 7:46
13: 7:35
14: 7:37
15: 7:42
15.57 7:30

Being healthy helps me to enjoy my life. I would recommend that everyone who has the ability, set up some goals and get out on the road. Life is too short to sit! There are lots of running clubs out there. The ones that I ran with were awesome and encouraging. Find one in your area and get to it.

Tags: