CS 242 Fall 2011 : Assignment 2.1
CS 242 Fall 2011 : Assignment 2.1
This page last changed on Sep 26, 2011 by cemeyer2.
The reading due next Monday, September 26th is chapters 6 and 7 from Code Complete.
For Monday, September 26th you will do a tutorial on VIM. Please login to an EWS machine (either in the lab or remotely) and run the command vimtutor. Please walk through this tutorial.
This week, you will be reading in raw data in JSON format and representing it as a graph in memory. You will then provide an interface to query data about the graph and provide a hook to visualize the data.
You are a senior software engineer for a new international airline, CSAir. Before CSAir launches passenger service across the globe, they first need to start selling tickets to passengers. But before that can happen, some software needs to be written to manage the extensive route map. You have been tasked by CEOs Woodley and Kamin to begin work on this software. Specifically, the initial requirements for this new software are:
JSON is most commonly used in web applications, as a lightweight format to transfer data asynchronously between a client and server. For instance, Facebook transmits status updates to your newsfeed using JSON so that new posts appear without having to reload the page. But, JSON is not limited for web applications. Parsers for JSON are available for just about every language out there. See http://www.json.org for parsers for some of the most common programming languages. Some languages even have JSON built into the core API. It would be wise for you to pick a language for this assignment that already has a well developed parser.
You can read more about JSON on the source of all lies.
A graph, at least to computer scientists, is a set of vertices and a set of edges which connect them. Each vertex in a (directed) graph has a set of outgoing edges and a set of incoming edges. There are many ways to represent a graph in memory, it is up to you to determine which representation you would like to use. For your assignment, you will represent each city in CSAir’s route map as a vertex in a graph and each route that CSAir flies as an edge between the two vertices that represent the linked destinations of that route. See the image below for a graphical representation of what a graph might look like:
Also, your graph will need to be augmented to hold extra data about each city and the routes that link them together. You will have to adapt your implementation to handle this extra data. In our case, the graph will be actually be directed. That is, the edges in the graph will have a source and a destination. But, for each route in CSAir’s route network, you will need to add two edges in your graph. One going from city A to city B and another going from city B to city A. The data that these two edges contain with be identical. This is because CSAir flies in both directions on all routes in its network. Imagine if the routes were one way only, eventually it could be possible that no aircraft would be able to get to a city to carry passengers. Trust us, it will be easier to follow this approach for future extensions to this assignment.
This week’s assignment is split into three main components.
You will need to write code that parses the given JSON file and loads it into graph representation in memory.
You need to write a simple user interface that allows the user to:
All of this information should be calculated at query time from your graph and not be hard coded into your source. Your program should be console driven, that is it should start up, prompt the user for input, and be able to perform any combination of valid operations without exiting. Also, be careful to check for invalid input. For instance, what happens when a user queries data about a city that CSAir does not fly to?
To implement this part of the assignment, you must use the command pattern. To accomplish this, you will need to think in a very object-oriented manner. You should be able to make a command object for each of commands we are asking you to implement. The source of all lies has a good overview of how to use the command properly, although the example is in Java. You should be able to adopt it to the language you choose.
The third and final phase of this week’s assignment is for you to visualize CSAir’s route map. To aid you in this task, CEOs Woodley and Kamin have told you about a website, the Great Circle Mapper. To accomplish this task, you do not need to write any code that actually draws the graph, but rather use the Great Circle Mapper to do it for you. This website uses the code associated with each city in CSAir’s route network. To view a sample of a generated route map, do the following:
Notice how when you do this, the Great Circle Mapper automatically generates a route map for you. Try playing around with some of the options to edit/enhance the generated image.
To generate a route map from your graph, you will need to:
You can minimally print this URL out to the console for the user to copy and paste into their web browser, but it would be better if you are able to automatically launch the web browser on the system to that URL.
As usual, we require that you write extensive unit tests for each part of this assignment. We realize that testing a console interface is difficult, so it is acceptable to write unit tests for each of the functions that your library has. When you choose your language for this assignment, make sure you look into what unit testing frameworks are available for that language and use one of them. If your language does not have a testing framework (unlikely), you will need to implement your own test runner and utilities to accomplish this part of the assignment.
For example, if you could use Java with jUnit this week (which you cannot), some asserts you might have:
This is by no means a a comprehensive list of tests that you will need to write, but it should become clear what you need to test as you work on the assignment. Think about covering all the main as well as corner cases.
|Document generated by Confluence on Feb 22, 2012 18:09|