CS-2510 Assignment 8

Due: November 17th20th @ 10:00 pm

Purpose:

To practice working with Graphs, Hashes, and HashMaps.

Make sure to read over all parts of a problem before starting it.



Programming Problem 1: (Graphs.java)

Building on the work in class with Graph Traversals, we are going to add some more features to our graph algorithms.

Here we will modify the FromTo method to return a List<Vertex> rather than a boolean. You will find that using our ConsLists that we started with will actually be easiest for this process.
  1. First you should write an implementation of our Parameterized Lists (or grab it from a previous time you wrote it).
  2. Now you will need to modify the next storage. Instead of just holding a Vertex, it should now additionally hold a List representing the path to get to this vertex. In order to store both of these, you should create a Pair<X,Y> class, which can hold 2 arbitrary objects.
  3. Now, when you get the next element to process, you will also get a List representing the path to this point. Modify the code that adds new elements to our next list such that you appropriately update the path to each Vertex you add.
  4. Note that to do this efficiently, you should add to the front of your list, which means the list you create will actually be in reverse order. So once you have found the destination vertex, you should reverse the list, and return it. How you reverse it is up to you.
  5. Add the ability to detect and avoid cycles to your functions. (Hint: use a HashSet for efficient storage and lookup) Then create a graph where your algorithms would run into a cycle and show that you can still produce a valid output.
  6. Make sure all of this works for both BFS and DFS traversals.



Programming Problem 2: (Intersection.java)

Hopefully we were able to discuss the idea of states, stepping through states, and so-called state-machines. We'll need this to develop protocols for games and other communications.

  1. Design classes to represent stop lights. Make sure you have a Light class, and represent the colors individually (interface Color, classes Red, Yellow, and Green).
  2. Design a method draw for your classes that draws a stop light. If the light is red, then the top light should be "solid" and the others should be "outline". Similarly for yellow and green.
  3. Design a void method step that changes the state of a stoplight to the next one. You should design a helper method to give you the next Color from the current one.

  4. Design an Intersection class that extends VoidWorld that demonstrates your Light classes. Set the tickRate to once per second (override the method). Create 2 lights, and have them alternate properly. I.e. Initially one light is red and the other green, then the green turns to yellow then to red, and the other light turns to green. Rinse and repeat.

    Note that for this, you will need a notion of where to place your lights such that both show in the Scene. You may need to modify your draw function from before to specify a center or corner point from which to draw the light into your scene.